Proving: n^2 % 3 = 0 Implies n % 3 = 0

[Dr-NiKoN]

I'm supposed to prove that if:
n^2 % 3 = 0
Then
n % 3 = 0

I'm not sure how to proceed here?

Does it got something to do with setting n^2 to x?
x % 3 = 0
and
\frac{x}{n} % 3 = 0

Not sure how that helps..

The actual problem is to prove that if n^2 / 3 is a whole number, then n/3 is also a whole number. But, I can't figure out any other way to present it.

 

[NateTG]

The actual problem is to prove that if n^2 / 3 is a whole number, then n/3 is also a whole number. But, I can't figure out any other way to present it.

Seems like that was good enough...

Assuming that $n$ is a whole number, we can apply the fundamental theorem of algebra, so $n$ has a unique prime factorization:
$$n=p_1^{a_1}\times p_2^{a_2}...$$
Where all the $p_i$ are primes, and all the $a_i$ are whole numbers. Then $n^2$ has the following prime factorization:
$$n^2=p_1^{2a_1} \times p_2^{2a_2}...$$

Should be pretty easy from there...

 

[HallsofIvy]

Work from the other side. If n is not a multiple of 3 (i.e. if n/3 is not a whole number), then n must be of the form n= 3m+1 or n= 3m+2 for some whole number m.

Now square them: n²= (3m+1)²= 9m²+ 6m+ 1=
3(3m²+ 2m)+ 1. In other words, it is a multiple of 3 plus 1, not a multiple of 3.

if n= 3m+2, then n²= (3m+2)²= 9m²+ 12m+ 4=
3(3m²+ 4m+ 1)+ 1. Again, it is not a multiple of 3.

Okay, if n is not a multiple of 3, then n² cannot be. What does that tell you about the case if n² is a multiple of 3?

 

[matt grime]

Or use the alternative characterizations of the primes:

p divides ab iff p divides either a or b.

Let =3, a=b=n

 

[Dr-NiKoN]

I can't use prime factorization, since that is in a later chapter.

Work from the other side. If n is not a multiple of 3 (i.e. if n/3 is not a whole number), then n must be of the form n= 3m+1 or n= 3m+2 for some whole number m.

Doesn't this give me:
p = n^2 is even
q = n is even
(in logic, don't know the latex for it)
if NOT q then NOT p

How does this prove:
if q then p

I tried working with the implication law, but can't seem to figure out how you get there. Or is this just some common law of logic?

 

[mikeu]

Doesn't this give me:
p = n^2 is even
q = n is even
(in logic, don't know the latex for it)
if NOT q then NOT p

HallsOfIvy's method gives you:
p = n^2 is divisible by 3
q = n is divisible by 3
if NOT q then NOT p

How does this prove:
if q then p

It doesn't, but it proves if p then q... Which is what you originally wanted, no?

 

[Hurkyl]

You could exhaust over the possibilities for n % 3.

 

[HallsofIvy]

"Doesn't this give me:
p = n^2 is even
q = n is even"

Well, no- the "negation" of "n is a multiple of 3" is not "n is even"!

It is a "law of logic" that "if p then q" is equivalent to "if not q then not p". That's called the contrapositive and is a special case of "proof by contradiction".

 

[Dr-NiKoN]

Thanks guys,

this actually helped me to solve a couple of other problems(proving the contrapositive that is). :)