Question

Let n be an integer. Prove that n^2 is divisible by 3 if and only if n is divisible by 3. (The "if and only if" part means that you have to prove two directions: if n^2 is divisible by 3 then n is divisible by 3 and if n is divisible by 3 then n^2 is divisible by 3.)

Answer 1

The proof has two parts.

1. If n^2 is divisible by 3, then n is divisible by 3.
2. If n is divisible by 3, then n^2 is divisible by 3.

The next two sections will handle each part separately.

====================================

Part 1: If n^2 is divisible by 3, then n is divisible by 3

Apply the contrapositive to get the statement "if n is not divisible by 3, then n^2 is not divisible by 3".

If we can prove the contrapositive is true, then the original conditional is true as well.

Let n be some non-multiple of 3. This would mean either n = 3k+1 or n = 3k+2 for some integer k.

n = 3k+1 gives remainder 1, and n = 3k+2 gives remainder 2.

Let's square both sides of the first equation.

n = 3k+1

n^2 = (3k+1)^2

n^2 = 9k^2 + 6k + 1

n^2 = 3(3k^2+2k)+1

n^2 = 3*(some integer) + 1

We've shown that n = 3k+1, stuff giving remainder 1, leads to n^2 giving the same exact remainder. Therefore, n^2 is also a non-multiple of 3 when we have n = 3k+1.

If n = 3k+2, then,

n^2 = (3k+2)^2

n^2 = 9k^2 + 12k + 4

n^2 = 9k^2 + 12k + 3 + 1

n^2 = 3(3k^2+4k+1)+1

n^2 = 3*(some integer) + 1

We get the same result here as well. Interestingly, we arrive at the same "remainder 1" and cannot reach a remainder 2 with either n = 3k+1 or n = 3k+2.

Examples:

• n = 7 gives remainder 1 when dividing by 3, while n^2 = 49 gives remainder 1.
• n = 8 gives remainder 2, and n^2 = 64 gives remainder 1.

We have proven that if n is not divisible by 3, then n^2 is also not divisible by 3.

This therefore proves the original statement "if n^2 is divisible 3, then n is divisible 3" when using the contrapositive.

====================================

Part 2: if n is divisible by 3, then n^2 is divisible by 3.

For this part we know that n is a multiple of 3.

Let k be some integer, so we have n = 3k

Square both sides and do a bit of rearranging to pull out a 3

n = 3k

n^2 = (3k)^2

n^2 = 9k^2

n^2 = 3(3k^2)

n^2 = 3*(some integer)

This proves that n being a multiple of 3 leads to n^2 also being a multiple of 3. Example: n = 18 and n^2 = 18^2 = 324 are multiples of 3.

A way to check if we have a multiple of 3 is to add the digits: 1+8 = 9 and 3+2+4 = 9, those sums are multiples of 3.

====================================

Both parts have been proven, so the proof is fully concluded.

We've shown that n^2 is divisible by 3 if and only if n is divisible by 3.

Equivalent statements:

• "n^2 is a multiple of 3 if and only if n is a multiple of 3."
• "3 is a factor of n^2 if and only if 3 is a factor of n."