If n is an integer that is NOT a multiple of 3, then n^2 = 1 mod 3
I did ...
to the contrary, if n is a multiple of 3 then n = 0 mod 3
then n^2 is also a multiple of 3 -> n^2 = 0 mod3 reaching a contradition
---> <---- therefore n^2 = 1mod 3 when n is not a multiple of 3. QED.
Is this correct?
Try one of these:
We show that if n is an integer that is NOT a multiple of 3, then n^2 = 1 mod 3.
Proof:
Assume n is not a multiple of 3, then we have two cases, n = 3k + 1 for some integer k, or n = 3m + 2 for some integer m.
case 1: n = 3k + 1
if n = 3k + 1, then n^2 - 1 = (3k + 1)^2 - 1 = 9k^2 + 6k + 1 - 1 = 9k^2 + 6k = 3(3k^2 + 2k).
since 3k^2 + 2k is an integer, 3 | n^2 - 1. this means n^2 = 1 mod 3 ...note, 3 | n^2 - 1 means "3 divides n^2 - 1"
case 2: n = 3m + 2
if n = 3m + 2, then n^2 - 1 = (3m + 2)^2 - 1 = 9m^2 + 12m + 4 - 1 = 3(3m^2 + 4m + 1)
since 3m^2 + 4m + 1 is an integer, 3 | n^2 - 1. this means n^2 = 1 mod 3
so we see in both cases where n is not a multiple of 3, n^2 = 1 mod 3
QED
Alternate proof:
Assume n is not a multiple of 3, then n = 1 mod 3 or n = 2 mod 3.
case 1: n = 1 mod 3
if n = 1 mod 3, then n^2 = 1^2 mod 3, so n^2 = 1 mod 3
case 2: n = 2 mod 3
if n = 2 mod 3, then n^2 = 2^2 mod 3, so n^2 = 4 mod 3, which is the same as saying n^2 = 1 mod 3 (do you know why?)
so in both cases where n is not a multiple of 3, we have n^2 = 1 mod 3
QED
I'm sure that the first proof is valid, for the second, it depends on whether or not you can square both sides of a congruence modulus, which i think you can, but i'm not sure, i rarely work in modulus, i usually translate to algebra and manipulate and then translate back, similar to what i did in the first