N is an integer that is not divisible by 3. Prove that N^2 is of the form 3p + 1, w...
Check the final answer first, then review the worked steps.
Check the final answer first, then review the worked steps.
If $N \equiv 1 \pmod{3}$, $N^2 = (3k+1)^2 = 9k^2+6k+1 = 3(3k^2+2k)+1 = 3p+1$.
If $N \equiv 2 \pmod{3}$, $N^2 = (3k+2)^2 = 9k^2+12k+4 = 3(3k^2+4k+1)+1 = 3p+1$.
Since $N$ is not divisible by 3, $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}$, thus $N^2 = 3p+1$.