<s>[INST] About the equivalence relation on $\mathbb{Z}\times\mathbb{Z}\,$ s.t. $(a,b)\sim(c,d)\,$ if $\,2^{a^2+d^2}\equiv 2^{b^2+c^2} (\text{mod} \, 5)$ Let $\sim$ be an equivalence relation on $\mathbb{Z}\times\mathbb{Z}\,\,\,\,\,$ s.t. $\,\,\,\,\,\forall \,\,\,(a,b), (c,d)\in\mathbb{Z}\times\mathbb{Z}$:
$(a,b)\sim(c,d)\,\,\,\,\,$ if $\,\,\,\,\,\,\,2^{a^2+d^2}\equiv 2^{b^2+c^2} (\text{mod} \,\, 5)$
Show that if $f: \mathbb{Z}\times\mathbb{Z} \to \mathbb{Z_4}\,\,\,$ is defined by $\,\,\,f((a,b))=(a^2-b^2)+4\mathbb{Z},\,\,\,\, \forall \,\,\,\,(a,b)\in\mathbb{Z}\times\mathbb{Z}$ we have: $\,\,\,\,\,\,\sim \,\,\,\,= \,\,\,\,\sim_f$ $\,\,\,\,\,\,\,\,$-$\,\,\,\,$This point is quite easy using the definitions and the Fermat's little theorem.
The second point, which gives me hard times, is: determine $Im(f)$ and $\frac{\mathbb{Z}\times\mathbb{Z}}{\sim}$,$\,\,\,$ any suggestion?
 [/INST] Since $\gcd(2,5)=1$ and $2^4 \equiv 1 \pmod{5}$, we have
$$2^{a^2+d^2} \equiv 2^{b^2+c^2} \pmod{5} \implies a^2+d^2 \equiv b^2+c^2 \pmod{4}\implies a^2-b^2 \equiv c^2-d^2 \pmod{4}.$$
Actually all these implications are reversible. So
$$2^{a^2+d^2} \equiv 2^{b^2+c^2} \pmod{5} \iff a^2-b^2 \equiv c^2-d^2 \pmod{4}.$$
This shows that the equivalence relation $\sim$ and the one generated by $f$ are the same.
For the image of $f$: consider the following:
\begin{align*}
f(0,0) & \equiv 0 \pmod{4}\\
f(1,0) & \equiv 1 \pmod{4}\\
f(0,1) & \equiv 3 \pmod{4}.
\end{align*}
Claim: Range of $f$ is $\{[0]_4,[1]_4,[3]_4\}$, i.e. $[2]_4 \not\in \text{Range}_f$.
If $a^2-b^2 \equiv 2 \pmod{4}$, then $a^2 \equiv b^2+2 \pmod{4}$. But $b^2+2 \equiv 2,3 \pmod{4}$. However, $\mod 4$, the only squares are $0,1$. Thus this is not possible.
Since the equivalence relation $\sim$ and the one generated by $f$ are the same, therefore the quotient set $\Bbb{Z} \times \Bbb{Z}/\sim$ will be (in a sense) isomorphic to the range of $f$. So
$$\Bbb{Z} \times \Bbb{Z}/\sim =\{[(0,0)], [(1,0)],[(0,1)]\}$$
</s>