Divisibility Question: Proving 12|(n^2-1) for Odd n^2 and Non-Divisibility by 3

[kreil]

Homework Statement

Suppose that $n^2$ is odd and that 3 does not divide $n^2$. Show that $12|(n^2-1)$

Homework Equations

none

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.

 

[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$.

 

[tiny-tim]

Hi kreil!

Suppose that $n^2$ is odd and that 3 does not divide $n^2$. Show that $12|(n^2-1)$

- if 3 does not divide $n^2$, then the remainder of this division must be either 1 or 2

forget n²

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

 

[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)?

 

[tiny-tim]

3 divides into n with r=2 since r=1 implies n is even

No it doesn't …

what about 7? ​

 

[kreil]

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

what does this mean?

 

[tiny-tim]

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

that's better!

now you have the possible remainders for 2 and 3 …

so … ?

 

[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?

 

[tiny-tim]

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?

wot's incorrect logic?

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

 

[kreil]

wot's incorrect logic?

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

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$??

 

[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..

 

[tiny-tim]

Hint: 6

and I'm going to bed :zzz:​

 

[kreil]

i don't understand how to make the next step to saying 6|n rem 1..

i think I'm missing something here

 

[kreil]

for ex if n is 11,

2|11 rem 1

3|11 rem 2

6|11 rem 5...

BUT 6|121 rem 1

 

[kreil]

i am so lost on this now...

 

[tiny-tim]

just got up :zzz: …

what are the possible remainders on dividing by 6?

 

[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.

 

[tiny-tim]

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

uhh? but n² is odd and 3 does not divide n².

 

[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.)

 

[kreil]

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^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 is not divisible by 3, so either n=3r+1 or 3r+2. In either case, what can you show divides 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$

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

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

 

[matt grime]

You have correctly shown that 3 and 4 divide n^2 - 1. So what does that mean? I don't understand what you're attempting to say in your last line, not least because it says that 0=1.

 

[kreil]

thanks!