If a^2 is divisible by 3, then a is divisible by 3

1. Oct 2, 2011

Heute

1. The problem statement, all variables and given/known data

Assume a is a natural number and that a^2 is divisible by 3 (that is, there exists natural number n so that 3n = a^2)

2. Relevant equations

3. The attempt at a solution

I thought about doing this one by contradiction. Suppose a is not divisible by 3. Then a/3 can be written as

a/3 = b/c

where b and c are natural numbers with no common factors. From there I square both sides to get

(a^2)/9 = b^2/c^2

My plan was to then show that this implies (a^2)/3 is NOT a natural number, a contradiction, which would imply no such b and c exist. I'm not certain if this is the right angle, however, since I had a hard time justifying that 3(b^2)/c^2 is not a natural number.

2. Oct 2, 2011

lineintegral1

Another way to go about it is to show that the contrapositive is true. You are saying that if $a^2$ is divisible by 3, then so is a. The contrapositive is that if a is not divisible by 3, then $a^2$ isn't either. If a is not divisible by 3, how can it be written? Can you think of a way to write any natural number that is not divisible by 3 in a general way?

If you are having a hard time with this, think about how you can write any even number. How about any odd number? Does a similar concept apply to 3?

3. Oct 2, 2011

Heute

Suppose 3 does not divide a. Then a can be written as 3n-1 or 3n-2 for some natural number n.

Case 1: a = 3n-1.
Then a^2 = 9n^2-6n+1 which is not divisible by 3 since (3n^2-2n+1/3) is the sum of two natural numbers and a fraction, which is not a natural number.

Case 2: a = 3n-2.
Then a^2 = 9n^2-12n+4 which is not divisible by three by similar reasoning.

But we know a^2 is divisible by three so we have a contradiction. Therefore, a must also be divisible by 3.

4. Oct 3, 2011

Dick

That works. It's easier you know 3 is prime and just think about prime factorizations, but that still works.