Fermat's Two Square Theorem: How do you prove that an odd prime is the sum of two squares iff it is congruent to 1 mod 4? It is a theorem in elementary number theory that if $p$ is a prime and congruent to 1 mod 4, then it is the sum of two squares. Apparently there is a trick involving arithmetic in the gaussian integers that lets you prove this quickly. Can anyone explain it?
 A: Here is another proof without complex numbers.
We start with proving that there exists $z \in \mathbb{N}$ such that $z^2 + 1 \equiv 0 \pmod p$. We do this in the same way as Akhil Mathew.
Let we have $a^2 + b^2 = pm$. Take $x$ and $y$ such that
$x \equiv a \pmod m$ and
$y \equiv b \pmod m$ and
$x, y \in [-m/2, m/2)$.
Consider $u = ax + by$ and $v = ay - bx$. Then $u^2 + v^2 = (a^2 + b^2)(x^2 + y^2)$.
Moreover, $u$ and $v$ are multiples of $m$.
Hence $(u/m)^2 + (v/m)^2 = p (x^2 + y^2)/m$. $(x^2 + y^2)/m$ is an integer because of the definition of $x$ and $y$ and that $a^2 + b^2 = pm$.
Also $(x^2 + y^2)/m$ is less than $m/2$.
Now we change $a$ by $u$ and $b$ by $v$ and continue this process until we get $m=1$.
Notice that this is quite efficient way to find representation of $p$ as a sum of two squares - it takes $O(\log p)$ steps to find it provided we have found $z$ such that $z^2 + 1$ is multiple of $p$.
A: There is an amazing proof of this due to Don Zagier : one-sentence proof.
A: Taken From I.N. Herstein There are 2 results which i am going to use.


*

*Let $p$ be a prime integer and suppose that for some integer $c$ relatively prime to $p$ we can find integers $x$ and $y$ such that $x^{2}+y^{2}=cp$. Then $p$ can be written as the sum of 2 squares.

*If $p$ is a prime of the form $4n+1$, then we can solve the congruence $x^{2} \equiv \ -1 \  (mod)  \ p$.
Now the main result. If $p$ is a prime of the form $4n+1$ then $p$ is the sum of 2 squares.
Proof. By 2 there exists and $x$ such that $x^{2} \equiv -1 \text{mod} \ p$. So $x$ can be chose such that $0 \leq x \leq (p-1)$. We can restrict the size of $p$ even further, namely to satisfy $|x| \leq \frac{p}{2}$. For if $x > p/2$ then, $y=p-x$ satisfies $y^{2} \equiv -1 \text{mod} \ p$ but $|y| \leq p/2$. Thus we may assume that we have an integer $x$ such that $|x| \leq p/2$ and $x^{2}+1$ is a multiple of $p$ say $cp$. Now $cp=x^{2}+1 \leq p^{2}/4 +1 < p^{2}$, hence $c < p$ and hence $(c,p)=1$. Invoking (1) we have $p=a^{2}+b^{2}$.
A: Let $$\Psi(n,m,k)=100n^2+20nm+m^2+4k^2$$
be a prime number for some $(n,m,k)$
Then:
This combination of $(n,m,k)$ must not share any factors. Except $(n,m)$ can share factors as long as: $$\gcd(n,m,k) = 1$$ So:
$$p = (10n+m)^2+(2k)^2$$
For the expression above to be a prime number, a combination of $(x,y)$ must be either even-odd or odd-even. But it already is for the $(n,m,k)$ we have picked.
If we pick n as some natural number, k as some positive natural number and m = 1,3,5,7,9 we fit the definition given above. Now we can expand and see that:
$$p = 100n^2+20nm+m^2+4k^2$$
This means $m^2\equiv1(mod4)$ since all other terms in the equation are already are congurent to $0(mod4)$.
But if you haven't already noticed for the choice for all of the m's we've picked all happen to be congurent to $1(mod4)$ when squared.
This means whether or not p is prime doesn't matter this equation will always produce a result of the form $p=4a+1$
Now this result may not give prime numbers all the time obviously. But our choice of $(n,m,k)$ was already for some, not all. Then one can state that:
If our choice of $(n,m,k)$ produces a prime number then it is a solution.
Except for the case $$1^2+1^2 = 2$$ which is the only case that will refute this, so it can be ignored.
Thus for:
$$p = x^2+y^2$$
if p is prime then:
$$p\equiv 1(mod4)$$
EDIT: The proof above isn't fully satisfactory since I start with $p=x^2+y^2$.  
If we start backwards by assuming:
$$p \equiv 1(mod4)$$
Then 
$$p = 4n+1$$
Now consider the following:
$$p=4n+1=100a^2+20ab+b^2+4c^2$$
If $10+b$ is odd then we don't have anything to worry about. So we have a look at $b^2$ and again $b = 1,3,5,7,9$ so:
$$b^2 \equiv 1(mod4)$$ 
or:
$$b^2 = 4m+1$$
Then we have: 
$$p=4m+100a^2+20a(4m+1)+4c^2+1$$
So we have written $p$ as a sum of two squares:
$$p=(10a+4m+1)^2+(2c)^2$$
since one can say $x= 10a+4m+1$ and $y = 2c$.
So now I have shown that either way around the statement holds.
Infact this is related to Zagier's proof since if we let $y = c$ instead:
$$p=x^2+(2y)^2$$
Thus now we have shown if: 
$$p \equiv 1(mod4)$$ 
then: 
$$p = x^2+y^2$$
So now one can say that a prime number can be written as a sum of two squares iff $p \equiv 1(mod4)$
Also we know this is the only way besides the case $1^2+1^2=2$ to write primes as a sum of two squares because of the first argument where I said the combination of (x,y) must be even-odd or odd-even. And we know we can write ANY prime number of the form $4a+1$ as a sum of two squares because $\Psi(n,m,k)$ for the given limitations on $(n,m,k)$ can produce any odd natural number of the form $4a+1$. And since the set that represents all natural numbers of the form $4a+1$ includes the set of primes that can be written as $4a+1$.
Please let me know if there is any problems with the proof.
A: Let $p$ be a prime congruent to 1 mod 4. Then to write $p = x^2 + y^2$ for $x,y$ integers is the same as writing $p = (x+iy)(x-iy) = N(x+iy)$ for $N$ the norm.  
It is well-known that the ring of Gaussian integers $\mathbb{Z}[i]$ is a principal ideal domain, even a euclidean domain.   Now I claim that $p$ is not prime in $\mathbb{Z}[i]$. To determine how a prime $p$ of $\mathbb{Z}$ splits in $\mathbb{Z}[i]$ is equivalent to determining how the polynomial $X^2+1$ splits modulo $p$.  
First off, $-1$ is a quadratic residue modulo $p$ because $p \equiv 1 \mod 4$.  Consequently, there is $t \in \mathbb{Z}$ with $t^2 \equiv -1 \mod p$, so $X^2+1$ splits modulo $p$, and $p$ does not remain prime in $\mathbb{Z}[i]$.  (Another way of seeing this is to note that
if $p$ remained prime, then we'd have $p \mid (t+i)(t-i)$, which means that $p \mid t+i$ or $t \mid t-i$.)
Anyway, as a result there is a non-unit $x+iy$ of $\mathbb{Z}[i]$ that properly divides $p$.  This means that the norms properly divide as well.  In particular, $N(x+iy) = x^2+y^2$ properly divides $p^2$, so is $p$ or $1$. It cannot be the latter since otherwise $x+iy$ would be a unit.  So $x^2+y^2 = p$.
A: Let $p \equiv 1\ (\text {mod}\ 4)$ and $a = \left (\frac {p-1} {2} \right )!$. Observe that $a^2 \equiv -1\ (\text {mod}\ p)$ by Wilson's theorem. Consider an ideal $I$ of $\Bbb Z[i]$ such that $I = \langle p,i-a \rangle$. Observe that $I \cap \Bbb Z = p \Bbb Z$. Let $R = \Bbb Z[i]/I$. Then $R$ is a commutative ring with identity. Consider the map $f : \Bbb Z \longrightarrow R$ such that $1 \mapsto 1_R$, where $1_R$ is the multiplicative identity in $R$ and extend it to a homomorphism. Observe that $f$ is surjective and $ker (f) = p \Bbb Z$. So by the first isomorphism theorem we have $\Bbb Z/p \Bbb Z \cong R$. Since $\Bbb Z[i]$ is a PID $\exists$ $a+ib \in \Bbb Z[i]$ such that $I = \langle a+ib \rangle$. Observe that $|R| = |\Bbb Z[i]/\langle a+ib \rangle| = a^2+b^2$. So we have $p = |\Bbb Z/p\Bbb Z| = a^2 + b^2,$ as claimed.
A: Perhaps my favorite argument (other than any arguably "correct" arguments, such as the one Akhil has given, or arguments starting from the fact that $x^2 + y^2$ is the unique binary quadratic form of discriminant $-4$ up to equivalence) uses continued fractions.  Suppose that $u^2 \equiv -1 \pmod{p}$, and consider the continued fraction expansion of the rational number $u/p$.  Let $r/s$ be the last convergent to $u/p$ with the property that $s < \sqrt{p}$.  Then, setting $x=s$ and $y = rp-us$, one has $x^2 + y^2 = p$.  
Here's the argument: let $r'/s'$ be the convergent following $r/s$.  Then the basic theory of continued fractions gives the estimate $|r/s - u/p| < 1/ss'$, and the right-hand side is less than $1/s\sqrt{p}$ by hypothesis.  Clearing denominators gives $y < \sqrt{p}$, so that $0 < x^2 + y^2 < 2p$.  On the other hand $x^2 + y^2$ is checked to be divisible by $p$ (by choice of $u$), so must be equal to $p$.
A: I tried this via Wilson's theorem- It seems to work but would be grateful if someone could verify it/offer improvements?
Suppose a prime $p=1  \ \text{mod} 4 $. By Wilson's theorem, $ (p-1)! = -1 (\ \text{mod} p) $. 
But $ p-r = -r (\text{mod} p) $ 
So $ -1= 1 (p-1) 2 (p-1)...( \frac{p-1}{2})( \frac{p-1}{2}  )  = 1 (-1) 2(-2)...( \frac{p-1}{2})( \frac{p-1}{2}  )= (-1)^{ \frac{p-1}{2}}(( \dfrac{p-1}{2})!)^{2} \ ( \text{mod} p) $
$ (-1)^{ \frac{p-1}{2}}= (-1)^{ \frac{4k+1-1}{2}}=1 $ so $ -1 =( \dfrac{p-1}{2})!)^{2} \ ( \text{mod} p) $
In other words $np = 1 + (( \dfrac{p-1}{2})!)^{2} $ iff $p=1  \ \text{mod} 4 $.
Any integer $x^{2} = 0,1 \ \text{mod} 4 $ so we cant find an $x^2, y^2$ such that $x^2+y^2 = 3 \ \text{mod} 4$. As a prime is odd, it is either congruent to 1 or 3 mod 4 so it can only be written as a sum of 2 squares if congruent to 1 mod4.
A: To answer the title: along with the standard Gaussian integers proof of the backwards direction, the forwards direction is simple: (We exclude the case of the only even prime $2 = 1^2 + 1^2$)
An odd prime is congruent to 1 or 3 mod 4, and since 0 and 1 are the only quadratic residues mod 4, we must have the prime congruent to 1 mod 4.
Alternatively: observe $p$ is coprime to $a$ and $b$ since if $p \mid a$ then $p \mid b$ and vice versa, then $p^2 \mid a^2,b^2 \implies p \mid a^2 + b^2 \implies p^2 \mid p$, a contradiction.
From $a^2 + b^2 \equiv 0  \iff a^2 \equiv -b^2  \iff (ab^{-1})^2 \equiv -1 \mod p$, $-1$ is a quadratic residue only if $p \equiv 1 \mod 4$.
A: See Geometrical figure explanation of  Zagier's one-sentence proof:

See details explanation given By mathologer on his you tube video
