By multiplying by a common denominator, we can rewrite the equation in integer numbers $$m^{2}+n^{2}=pk^{2}.$$ Further, by considering triples such that $gcd(m,n,k)=1$ , we can assume that the numbers are pairwise relatively prime, because if two numbers are divisible by a prime number $q$ , then the third number is divisible by $q$ as well (even if the two numbers are $m$ and $n$ , and $q=p$ ).

In particular, there is no more than one even number among $m$ , $n$ and $k$ . If $m$ and $n$ are odd, then we get $$2=pk^{2}(\mod\,4),$$ implying $p=2$ . If one of $m$ and $n$ is even, then we get $$1=pk^{2}(\mod\,4),$$ implying $$p=1(\mod\,4).$$

Therefore, a necessary condition for existence of solutions is that $$p=2\mbox{ or }p=1(\mod\,4).$$ In fact, this is also a sufficient condition. Indeed, if $p=2$ , then $1^{2}+1^{2}=2$ is a solution. Now, suppose $p$ is an odd prime such that $p=1(\mod\,4)$ . Then, since $(\mathbb{Z}_{p}-\{0\},\cdot)$ is cyclic, let $a$ be a generator, so that $$\begin{eqnarray*} a^{p-1} & = & 1(\mod\,p),\\ a^{\tfrac{p-1}{2}} & = & -1(\mod\,p), \end{eqnarray*}$$ and for $s=a^{\tfrac{p-1}{4}}$ , we have $$\begin{eqnarray*} s^{2} & = & -1(\mod\,p). \end{eqnarray*}$$ Then, consider all possible pairs $0\le m,n<\sqrt{p}$ . Among them, there are two pairs $m',n'$ and $m'',n''$ such that $$\begin{eqnarray*} m'-sn' & = & m''-sn''(\mod\,p). \end{eqnarray*}$$ Hence, for $m=m'-m''$ and $n=n'-n''$ , $$\begin{eqnarray*} m-sn & = & 0(\mod\,p), \end{eqnarray*}$$ where $-\sqrt{p}<m,n<\sqrt{p}$ . We conclude that $$\begin{eqnarray*} m & = & sn(\mod\,p),\\ m^{2} & = & -n^{2}(\mod\,p),\\ m^{2}+n^{2} & = & 0(\mod\,p), \end{eqnarray*}$$ and, given that $0\le m^{2},n^{2}<p$ , $$\begin{eqnarray*} m^{2}+n^{2} & = & p. \end{eqnarray*}$$

For example, take $p=17$ . For $a=3$ , we have

$k$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
$3^{k}(\mod\,17)$	$3$	$-8$	$-7$	$-4$	$5$	$-2$	$-6$	$-1$

hence, $3$ is a generator, and $$\begin{eqnarray*} s & = & 3^{4}\\ & = & -4(\mod\,17). \end{eqnarray*}$$ We take all pairs $0\le m,n\le4$ , and calculate $m+4n(\mod\,17)$ .

$m$ \$n$	$0$	$1$	$2$	$3$	$4$
$0$	$0$	$4$	$8$	$-5$	$-1$
$1$	$1$	$5$	$-8$	$-4$	$0$
$2$	$2$	$6$	$-7$	$-3$	$1$
$3$	$3$	$7$	$-6$	$-2$	$2$
$4$	$4$	$8$	$-5$	$-1$	$3$

So, we can take $m$ and $n$ as follows.

$m$	$n$
$1$	$4$
$4$	$-1$

Note, that we showed that $p$ has to be either $2$ or such that $p=1(\mod\,4)$ , but for all such $p$ we showed that, in fact, there is a solution of $x^{2}+y^{2}=p$ in integer numbers, which is much easier to find than if there were no integer solutions. To find all rational solutions, suppose that $$\begin{eqnarray*} m^{2}+n^{2} & = & p. \end{eqnarray*}$$ Then, as in Exercise $2$ , we consider all lines through $(m,n)$ that intersect the circle $x^{2}+y^{2}=p$ , and parametrize the circle accordingly. We have $$\begin{eqnarray*} x=\tfrac{m\lambda^{2}-2n\lambda-m}{1+\lambda^{2}} & \mbox{and} & y=\tfrac{-n\lambda^{2}-2m\lambda+n}{1+\lambda^{2}}. \end{eqnarray*}$$ Therefore, all rational solutions are given by $$\begin{eqnarray*} (x,y) & = & \left(\tfrac{ms^{2}-2nst-mt^{2}}{s^{2}+t^{2}},\tfrac{-ns^{2}-2mst+nt^{2}}{s^{2}+t^{2}}\right), \end{eqnarray*}$$ where $s,t\in\mathbb{Z}$ , $(s,t)\neq(0,0)$ , and we can assume that one of them is positive, and they are relatively prime.