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

Question

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!

Answer 1

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. $$

Answer 2

It would be easy if $\space 2017\space $ were a perfect square but there are no better approaches that i know of except for limiting the search. $$x^2+y^2=2017\implies y=\sqrt{2017-x^2}\\ \implies\bigg\lceil\sqrt{2017-\big(\big\lfloor\sqrt{2017}\;\big\rfloor\big)^2}\space \bigg\rceil=9\le x\le \big\lfloor\sqrt{2017}\;\big\rfloor=44$$ This shows a finite search and any $\space x \space $ that yields an integer $\space y\space $ is a solution.

Of these $\space 36\space $ values to test, the only $y$-integers found are for $\space x=9\space$ and $\space x=44.\quad$ Since $\space x,y\space $ are interchangeable, this means $\quad|x|,|y|\in\big\{9,44\big\}\quad$ with the valid solutions being all combinations for a total of $\space 8\space $ solutions.

Answer 3

Hopefully I didn't make any mistake.

Note that the squares modulo $9$ are $0,1,4,7$.

Now $$2017 = a^2 + b^2 \Rightarrow \\ 1 \equiv a^2+b^2 \pmod{9}$$

This gives that, WLOG we have $$ a^2 = 0 \pmod{9} \\ b^2= 1 \pmod{9} $$ and hence $a=3k$ and $b=9l \pm 1$.

Then, $$ 2017 = 9k^2+ 81l^2 \pm 18l +1 \Rightarrow \\ 224 = k^2+ 9l^2 \pm 2l $$ Finally $$ 224 \geq 9l^2 \pm 2l \geq 9l^2-2l \leq 7l^2 \Rightarrow \\ l \leq 5 $$

A case by case analysis is now very fast.