Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that 12 | n^2-1 if g.c.d. (n,6)= 1.

  1. Aug 24, 2009 #1
    Prove that 12 | n^2-1 if g.c.d. (n,6)= 1.

    I'm pretty sure i already proved this using fermats little theorem, 3 | n^2-1 and 2| n-1, and since n^2-1 is always greater than or equal to 24, (cept for n=1 in which case any number dividies into 0) therefore since 12=2*2*3, 12 | n^2-1

    This isn't really atheistically pleasing, can anyone do this a different way?
    Last edited: Aug 24, 2009
  2. jcsd
  3. Aug 24, 2009 #2
    Re: prove...

    hi there

    n^2-1 = (n-1)(n+1)
    gcd(n,6)=1 implies n is odd, so n-1 is even and n+1 is even, thus 4|(n-1)(n+1)
    gcd(n,6)=1 implies: either n=1 mod 3 (in which case n-1 = 0 mod 3)
    or n=2 mod 3 (in which case n+1 = 0 mod 3),
    in both cases 3|(n-1)(n+1)
    From 4|(n-1)(n+1) and 3|(n-1)(n+1) we conclude that 12|(n-1)(n+1)
  4. Aug 24, 2009 #3
    Re: prove...

    i followed your proof up to the congruence part, im new to this, and thats very simple and clever, i like it.
  5. Aug 25, 2009 #4
    Re: prove...

    I don't have my own proof for this, but what Liwuinan said is right (as far as I can tell anyway). I loved the elegance of it. Simple and sweet, just like a proof should be
  6. Aug 25, 2009 #5
    Re: prove...

    thank you guys for a nice welcome to this forum! :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook