Show that the equation $x^2 + y^2 = p$ has a rational solution if and only if it has an integer solution Let $p$ be an odd prime. 
Show that the equation $x^2 + y^2 = p$ has a rational solution (i.e., with $x,y \in \mathbb{Q}$) if and only if it has an integer solution (with $x,y \in \mathbb{Z}$), i.e., if and only if $p \equiv 1 \pmod 4$.
Not sure how to begin. Is the converse not obvious, since an integer is a rational number?
 A: If the equation $x^2 + y^2 = p$ has a rational solution, then $x^2 + y^2 = pz^2$ has an integer solution, and so does $x^2 \equiv -1 \bmod p$. This implies that $x^4 \equiv 1 \bmod p$ has a solution and so there is an element of order $4$ in $U(p)$. By Lagrange's theorem, $4$ divides $p-1$. As it is well known, this implies that $x^2 + y^2 = p$ has an integer solution.
A: Perhaps the following can clear up some doubts in lhf's answer:
Suppose there are $\;a,b,c,d\in\Bbb Z\;$ such that with reduced fractions we have
$$\frac{a^2}{b^2}+\frac{c^2}{d^2}=p\iff (ad)^2+(bc)^2=p(bd)^2$$
Let $\;q\;$ be a prime dividing $\;b\;$ , then from $\;b^2\left(pd^2-c^2\right)=(ad)^2\;$ we get that $\; q\mid(ad)^2\implies q\mid ad\;$ . Since $\;\frac ab\;$ is a reduced fraction we get that $\;q\mid d\;$, and by symmetry of the argument we get that any prime dividing $\;d\;$ also divides $\;b\;$ and from here that $\;b=\pm d\;$ , and if we decide that $\;a,b,c,d\in\Bbb N\;$ then in fact $\;b=d\;$, so we have the equality
$$a^2+c^2=pb^2\implies \left(\frac ac\right)^2=-1+\left(\frac bc\right)^2p$$
so putting $\;x:=\frac ac\;$ , the above means $\;x^2=-1\pmod p\;$ , and this means the cyclic group $\;\Bbb F_p^*\;$ has an element of order four , so
$$4\mid|\Bbb F_p^*|=p-1\iff p=1\pmod4$$.
