<s>[INST] Fermat's infinite descent for finding the squares that sum to a prime Fermat's theorem on sum of two squares states that an odd prime $p = x^2 + y^2 \iff p \equiv 1 \pmod 4$
Applying the descent procedure I can get to $a^2 + b^2 = pc$ where $c \in \mathbb{Z} \gt 1$
I want $c = 1$, so how do I proceed from here? How do I apply the procedure iteratively?
Example:
$$
p = 97
$$
$$97 \equiv 1 \pmod 4 \implies \left(\frac{-1}{97}\right) = 1 \implies x^2 \equiv -1 \pmod {97}$$ has a solution
$$x^2 + 1 \equiv 0 \pmod {97}$$
$$x^2 + 1 = 97m$$
We find an $x,m$ that solves the equation.
$$x = 75, m = 58$$
Now, we pick an $a,b$ such that $\frac{-m}{2} \leq a,b \leq \frac{m}{2}$
$$a \equiv x \pmod m = 17$$
$$b \equiv y \pmod m = 1$$
Observations:


*

*$ a^2 + b^2 \equiv x^2 + 1 \equiv 0 (\mod m)$

*$ (a^2 + b^2) = mc$

*$ (x^2 + 1) = mp$
Plugging in $a,b,m$ for 2, we get $c = 5$

By this identity, we know that
$(a^2 + b^2)(c^2 + d^2) = (ac + bd)^2 + (ad - bc)^2$
**$(a^2 + b^2)(x^2 + 1^2) = (ax + b)(a - bx) = m^2pc$
Dividing ** by $m^2$, $pc = (\frac{ax+b}{m})^2 + (\frac{a-bx}{m})^2$
Plugging in $a,b,m,p,c$ we get that $22^2 + (-1)^2 = 97*5$
So we have two squares that add up to 5 times our $p$. How do we turn the 5 into a 1? What is the next step in the descent?
 [/INST] This is how we proceed.
We found out that $22^2+(−1)^2=97∗5$
Notice it's a sum of squares - so let's use the equation from before $x^2 + 1 = 97m$. In general, the $1$ might be something else. In this case, since $(-1)^2 = 1$, nothing really changes and we can use the exact same equation.
In the second iteration:
$m = 2$
$x = 22$
$y = 1$ (we can safely remove the negative)
Our $m$ is now $5$. So as before, we need to pick integers $a,b$ such that $a,b \in [-m/2,m/2] \implies a,b \in [-2.5, 2.5]$
$a \equiv x \equiv 2 \pmod 5$
$b \equiv y \equiv 1 \pmod 5$
Apply the Fibonacci identity from before:
** $(a^2 + b^2)(x^2 + y^2) = (ax+by)^2 + (ay-bx)^2 = (2*22+1*1)^2 + (2*1-1*22)^2 = (45)^2 + (-20)^2 = m^2pr = 25*97*c$
Again, solve for $c$. In this case $c = 1$.
Awesome! This is the last iteration.
Divide ** by $m^2$, $p =(\frac{45}{5})^2+(\frac{-20}{5})^2 = (9)^2 + (-4)^2$
So, $a=9, b=4$ solve $a^2 + b^2 = 97$
</s>