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^2soo 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!