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

[Heute]

Homework Statement

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)

Homework Equations

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.

 

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

 

[Heute]

I think I follow you.

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.

 

[Dick]

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