# Divisibility question

1. Mar 9, 2009

### kreil

1. The problem statement, all variables and given/known data
Suppose that $n^2$ is odd and that 3 does not divide $n^2$. Show that $12|(n^2-1)$

2. Relevant equations
none

3. The attempt at a solution
Well I know that since $n^2$ is odd, $n^2-1$ is even. I'm not sure what the next step would be.

2. Mar 9, 2009

### kreil

hmm i did some more thinking on this. Please let me know if you think this is correct:

- since $n^2$ is odd, $n^2-1$ is an even number and $2|n^2-1$

- $n^2$ is not prime since it has at least 3 divisors: {1, n, $n^2$}

- if 3 does not divide $n^2$, then the remainder of this division must be either 1 or 2 (a remainder of 3 implies that 3 does divide $n^2$). However, the remainder cannot be 2 or else $n^2$ would be prime, therefore the remainder must be 1.

- this implies 3|$n^2-1$ evenly, since the -1 cancels with the remainder on division with $n^2$.

Since 2|$n^2-1$, 3|$n^2-1$ and $12=2^2 3^1$, it follows that 12|$n^2-1$.

3. Mar 9, 2009

### tiny-tim

Hi kreil!
forget n2

… what is the remainder if you divide n by 2 or 3?

4. Mar 9, 2009

### kreil

n is odd

so 2 divides into n with r=1

3 divides into n with r=2 since r=1 implies n is even and r=0 or 3 implies 3 divides $n^2$

soo does this mean that 3 divides into $n^2$ with remainder $r^2$ (i.e. r=1)?

5. Mar 9, 2009

### tiny-tim

No it doesn't …

6. Mar 9, 2009

### kreil

oops, so 3|n with r=1 or r=2

what does this mean?

7. Mar 9, 2009

### tiny-tim

that's better!

now you have the possible remainders for 2 and 3 …

so … ?

8. Mar 9, 2009

### kreil

so if 3|n with r=1 or r=2, then 3|$n^2$ with r=1 or r=4 and since if r=4 3|4 with r=1, 3|$n^2$ with r=1

is that correct logic?

9. Mar 9, 2009

### tiny-tim

wot's incorrect logic?

anyway, how can 3 divide anything with r = 4??

10. Mar 9, 2009

### kreil

haha, this doesn't tell me very much about whether what i wrote was right or not...

is it true that if 3|n with remainder r, that 3|$n^2$ with remainder $r^2$??

11. Mar 9, 2009

### kreil

i now know that this problem reduces to the problem of showing that 3|$n^2$ with r=1, i just don't understand how to connect division of n by 2 and 3 to this..

12. Mar 9, 2009

### tiny-tim

Hint: 6

and i'm going to bed :zzz:​

13. Mar 9, 2009

### kreil

i dont understand how to make the next step to saying 6|n rem 1..

i think i'm missing something here

14. Mar 9, 2009

### kreil

for ex if n is 11,

2|11 rem 1

3|11 rem 2

6|11 rem 5...

BUT 6|121 rem 1

15. Mar 9, 2009

### kreil

i am so lost on this now...

16. Mar 10, 2009

### tiny-tim

just got up :zzz: …

what are the possible remainders on dividing by 6?

17. Mar 10, 2009

### kreil

because of the condition 0<r<6 for the equation n = 6b + r for some b, r can be 1,2,3,4,5.

18. Mar 10, 2009

### tiny-tim

uhh? but n2 is odd and 3 does not divide n2.

19. Mar 10, 2009

### matt grime

tiny tim is pointing you at the Chinese remainder theorem.

But let's try a different way.

n is odd, so n=2m+1 for some m. Now what divides n^2-1?

n is not divisible by 3, so either n=3r+1 or 3r+2. In either case, what can you show divides n^2-1?

Equivalently, n^2-1 is congruent to what mod what and what? (insert useful things instead of 'what' in that sentence.)

20. Mar 10, 2009

### kreil

$n^2=(2m+1)(2m+1)=4m^2+4m+1 \implies n^2-1=4(m^2+m)$ for some m, and 4|$n^2-1$

$n^2=9r^2+6r+1$

or $n^2=9r^2+6r+4$

so $n^2-1=9r^2+6r=3(3r^2+2r)$

or $n^2-1=9r^2+6r+3=3(3r^2+2r+1)$

and in both cases 3|$n^2-1$

so $$n^2-1=(3r^2+2r)(mod 3)$$ and $$n^2-1=(3r^2+2r+1)(mod 3)$$??