5
$\begingroup$

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:

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

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

  3. $ (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?

$\endgroup$
  • 2
    $\begingroup$ Excellent choice of tags! :) $\endgroup$ – punctured dusk Nov 13 '15 at 23:50
0
$\begingroup$

$$22^2+1=97\times 5$$

Use the idendity $$(2a+b)^2+(a-2b)^2=5a^2+5b^2$$

The numbers $a,b$ obvioulsy solve the equation $a^2+b^2=97$ , if $$2a+b=22\ ,\ a-2b=1$$

Solving this system gives $a=9\ ,\ b=4$

$\endgroup$
  • 1
    $\begingroup$ Does this follow the decent, or is it a trick to get to the answer quicker? Where does the identity come from? If instead of 5 I had 4, how would I come up with it? $\endgroup$ – pushkin Nov 14 '15 at 0:55
0
$\begingroup$

We need to know that if $q$ is prime and $q\equiv 3\pmod 4$ then $q|(x^2+y^2)\to (q|x\land q|y)$. Now for prime $p\equiv 1\pmod 4$ we have $c p=a^2+b^2$ where $p/2>a>0<b<p/2$. This implies $0<c<p$. We ask for the smallest possible positive $c$. We show that if $c>1$ then $c$ is not the minimum. First,if $q$ is prime and $q|c$, where $q\equiv 3\pmod 4$, then $q|c\to q|(a^2+b^2) \to (q|a\land q|b) \to q^2|c\to (c/q^2)p=(a/q)^2+(b/q)^2$; and $0<c/q^2<c$ so $c$ is not the minimum. Second, suppose that every prime $r$ such that $r<p$ and $r\not \equiv 3\pmod 4$ is the sum of two squares. (This is the Inductive Hypothesis.) Then if the prime $r$ divides $c$ and $r\not \equiv 3\pmod 4$ then $r=(s^2+t^2) $ for some positive integers $s,t,$....Recall that $r$ also divides $a^2+b^2$. Let $s\equiv i t\pmod r$ and $a\equiv j b\pmod r$ where $i^2\equiv j^2\equiv -1\pmod r$ and $j\equiv \pm i\pmod r. $ In the case $j\equiv i\pmod r$ we have, with $c'=c/r,$ $$ p c' r^2=p c r=c'(a^2+b^2)(s^2+t^2)=c'((a s +b t)^2+(a t-b s)^2).$$ Now $(a s +b t)\equiv j i b t+b t\equiv i^2 b t+ b t\equiv 0\pmod r$ and similarly $a t-b s\equiv 0\pmod r$. Therefore for some $u,v$ we have $$0\ne (r u)^2+(r v)^2=(a s+b t)^2+(a t-b s)^2=p c' r^2$$ from which $$0\ne p c'=u^2+v^2$$ Since $0<c'<c$, we see that $c$ is not minimum.....In the case $j\equiv -i\pmod r$ we use the equality $(a^2+b^2)(s^2+t^2)=(a s-b t)^2+(a t+b s)^2.$

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.