$(x \equiv k^2 \mod 3) \iff x \equiv 1 \mod 3 $

177 Views Asked by At

Is it true that if 3 does not divide $x$,

$$x\equiv k^2\mod 3 \iff x\equiv 1 \mod 3$$

If the above statement is correct , There are two parts to prove

$$x\equiv k^2\mod 3 \implies x\not\equiv 0 \mod 3$$ $$x\equiv k^2\mod 3 \implies x\not\equiv 2 \mod 3$$

How to prove them ?

1

There are 1 best solutions below

0
On BEST ANSWER

A cleaner way of stating this would be, that the only squares modulo 3 are 0 and 1. We can prove this, by squaring each of the three residues modulo 3:

\begin{align*} 0^2 &\equiv 0\pmod{3} \\ 1^2 &\equiv 1\pmod{3} \\ 2^2 \equiv 4 &\equiv 1\pmod{3} \end{align*}

You can see from this analysis that the only possible values for $k^2$ are $0,1\pmod{3}$, which is what you wanted to show.