# Proof by logic

1. Feb 21, 2005

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

Last edited: Feb 21, 2005
2. Feb 21, 2005

### NateTG

Seems like that was good enough...

Assuming that $n$ is a whole number, we can apply the fundemental 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...

3. Feb 21, 2005

### HallsofIvy

Staff Emeritus
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: n2= (3m+1)2= 9m2+ 6m+ 1=
3(3m2+ 2m)+ 1. In other words, it is a multiple of 3 plus 1, not a multiple of 3.

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

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

4. Feb 21, 2005

### 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

5. Feb 21, 2005

### Dr-NiKoN

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

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?

6. Feb 21, 2005

### mikeu

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

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

7. Feb 21, 2005

### Hurkyl

Staff Emeritus
You could exhaust over the possibilities for n % 3.

8. Feb 22, 2005

### HallsofIvy

Staff Emeritus
"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".

9. Feb 28, 2005

### Dr-NiKoN

Thanks guys,

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