Originally Posted by

**Jhevon**

**Let n be an integer. Prove that if n is not congruent to 0 (mod 3), then n^2 is congruent to 1 (mod 3).**

Proof:

We employ a direct proof. assume n is not congruent to 0 (mod 3), then 3 does not divide (n - 0) = n. therefore, n = 3c + r, where r is the remainder when we divide by 3, thus r = 1 or 2 (note, if r is 0 it means the number was divisible by 3, if r is 3, it means the number is divisible by 3). thus we have 2 cases: (1) n = 3c + 1, and (2) n = 3c + 2

case 1: n = 3c + 1

if n = 3c + 1, then n^2 - 1= (3c + 1)^2 - 1 = 9c^2 + 6c + 1 - 1 = 3(3c^2 + 2c).

since 3c^2 + 2c is an integer, 3|n^2 - 1 and so n^2 is congruent to 1 (mod 3).

case 2: n = 3c + 2

if n = 3c + 2, then n^2 - 1 = (3c + 2)^2 - 1 = 9c^2 + 6c + 4 - 1 = 3(3c^2 + 2c + 1)

since 3c^2 + 2c + 1 is an integer, 3|n^2 - 1, and so n^2 is congruent to 1 (mod 3).

So we see in both cases where n is not congruent to 0 (mod 3), n^2 is congruent to 1 (mod 3).

QED