N is an integer that is not divisible by 3. Prove that N^2 is of the form 3p + 1
Check the final answer first, then review the worked steps.
Check the final answer first, then review the worked steps.
N \equiv 1, 2 \pmod{3} \implies N^2 \equiv 1, 4 \equiv 1 \pmod{3} \implies N^2 = 3p + 1
If $N$ is not divisible by 3, then $N \equiv 1 \pmod{3}$ or $N \equiv 2 \pmod{3}$. Squaring both cases yields $N^2 \equiv 1^2 = 1 \pmod{3}$ or $N^2 \equiv 2^2 = 4 \equiv 1 \pmod{3}$, so $N^2 = 3p + 1$.