Show that for $p$ to be odd prime and $p \equiv 3$ mod $4$, then $x^2+y^2 = p$ has no integer solution Show that for $p$ to be odd prime and  $p \equiv 3$ mod $4$, then $x^2+y^2 = p$ has no integer solution. I have no idea how can i apply quadratic reciprocity to the equation  $x^2+y^2 = p$ or should use other method. 
 A: Simplest way is to note that if $x = 2k + m; m = 0,1$ and $y= 2j + n; n=0,1$ then $x^2 + y^2 = 4(k^2 + j^2 + km + jn) + m^2 + n^2 \equiv m^2 + n^2 \equiv 0,1,2 \mod 4 \not \equiv 3\mod 4$
$p$ being prime has nothing to do with it.
... or $x \equiv 0, \pm 1, 2 \mod 4 \implies x^2 \equiv 0,1 \mod 4$ so $x^2 + y^2 \equiv 0,1,2 \mod 4$.
Not sure which is easier.
A: $p$ is odd then $x$ and $y$ have different parity. We can assume without loss of generality that $x$ is odd and $y$ is even.
We set $$x=2X+1$$
$$y=2Y$$
Then $$x^2+y^2=4X^2+4X+1+4Y^2=4(X^2+X+Y^2)+1=p$$
Hence, We only have solutions if only:
$$p\equiv 1\pmod 4$$
A: You don't need quadratic reciprocity. Obviously $xy \neq 0$  mod $p$ if $x^2 + y^2 =p$. Reducing mod $p$, you get $a^2 = -1$ in the finite field $\mathbf F_p$. Since the multiplicative group $\mathbf F_p^{*}$ is cyclic of order $p-1$ and $a$ is of order $4$ in this group, necessarily $p \equiv 1$ mod $4$.
A fancier (but fundamentally equivalent) solution consists in using the decomposition of primes in the Gauss ring $\mathbf Z [i]$. The given equation can be written $(x + iy)(x-iy) = p$, i.e. the prime $p$ is totally decomposed in $\mathbf Z [i]$, which is classically equivalent to $p\equiv 1$ mod $4$.
A: Generalization,
If $k$ be a positive integer satisfying $k \equiv 3 \pmod 4$ then $x^2+y^2=k$ has no integer solutions.
Proof
$k \equiv 3 \pmod 4$ is given and if $x,y$ be integers satisfying $x^2+y^2=k$ then we must have, 
$x^2+y^2\equiv 3 \pmod 4$
But,
Given any integer $j$ we know that $j^2 \equiv 0 \pmod 4$ or $j^2 \equiv 1 \pmod 4$
And hence $x \in \mathbb{Z} , y \in \mathbb{Z}$ implies, $x^2+y^2 \equiv 0+0 = 0 \pmod 4$ or $\equiv 1+0 = 1 \pmod 4$ or $\equiv 1+1 = 2 \pmod 4$or $\equiv 0+1 = 1 \pmod 4$ 
And again, None of the numbers $0,1,2$ is $\equiv 3 \pmod 4$ .
Hence contradiction !!
Thus our assumption was false.
Hence Proved
