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

1. Aug 24, 2009

### Fisicks

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. Aug 24, 2009

### Liwuinan

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)

3. Aug 24, 2009

### Fisicks

Re: prove...

i followed your proof up to the congruence part, im new to this, and thats very simple and clever, i like it.

4. Aug 25, 2009

### pzona

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

5. Aug 25, 2009

### Liwuinan

Re: prove...

thank you guys for a nice welcome to this forum! :)