# express prime as sum of squares, $p = a^2 + b^2$

Espress $2017$ as sum of two squares.

attempt: by Fermat's Theorem on sums of squares, the prime $p = 2017$ is the sum of two squares $2017 = a^2 + b^2$ , $a,b \in \mathbb{Z}$, if and only if $p \equiv 1 mod 4$.

And The irreducible elements in the Gaussian integers $\mathbb{Z[i]}$ are as follows $(a + bi)(a - bi)$ for primes $p\in \mathbb{Z}$ with $p \equiv 1 mod 4$ (both of which have norm $p$).

Then since $2017 \equiv 1 (mod 4)$ Then $2017 = a^2 + b^2$ .

Notice that $\sqrt2017$ is approximately $44.91$. So $a^2, b^2$ will be between values $1,2^2,....,44^2$ .

Then plugging different values from the above squares in $2017 - a^2 = b^2$
we find $2017 - 44^2 = 81 = 9^2$

So $2017 = 44^2 + 9^2$.

However, I found them using that approach. But is there a way to find them without doing this approach?

I dont' know how to use $p = a^2 + b^2 = (a + bi)(a - bi)$ for primes $p\in \mathbb{Z}$ with $p \equiv 1 mod 4$ (both of which have norm $p$).

So $2017 = a^2 + b^2 = (a+ bi)(a - bi)$. I don't' know how I would proceed assuming I would not have found the values . Any feedback or better approach would be appreciated it. Thank you!

• See math.stackexchange.com/questions/5877/… for several algorithms. – lhf Nov 10 '15 at 1:13
• – Servaes Nov 10 '15 at 1:15
• There is an old algorithm due to Legendre, that uses the continued fraction expansion of $\sqrt{p}$. It is unfortunately a little long to describe here. Since then there have been many more. – André Nicolas Nov 10 '15 at 1:21

I think I will throw in an advertisement for quadratic forms. Solve $u^2 \equiv -1 \pmod p.$ This could be by hand for small primes or primes of very special forms, otherwise it is Cornacchia or Tonelli-Shanks. Next we have $(2u)^2 \equiv -4 \pmod {4p},$ or $$(2u)^2 = - 4 + 4 p t,$$ $$(2u)^2 - 4 pt = -4.$$ This is a discriminant; we have the form $\langle p, 2u, t \rangle$ of discriminant $-4.$ The shorthand $\langle p, 2u, t \rangle$ means the (positive) binary quadratic form $$f(x,y) = p x^2 + 2 u xy + t y^2.$$
Since this has discriminant $-4,$ it is equivalent by $SL_2 \mathbb Z$ to the only "reduced" form of that discriminant, namely $x^2 + y^2.$ In detail, given $$G = \left( \begin{array}{cc} p & u \\ u & t \end{array} \right)$$ and $$I = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right)$$ there is a matrix $P$ of determinant $1$ such that $$P^T G P = I.$$ Furthermore, it is very quick to find $P,$ this is usually called Gauss reduction. Next, take $$Q = P^{-1}.$$ We then have $$Q^T Q = G.$$ In particular $$q_{11}^2 + q_{21}^2 = p.$$