# proof of Thue’s Lemma

Let $p$ be a prime congruent^{} to 1 mod 4.

We prove the uniqueness first: Suppose

${a}^{2}+{b}^{2}=p={c}^{2}+{d}^{2},$ |

where without loss of generality, we can assume $a$ and $c$ even, $b$ and $d$ odd, $c>a$, and thus that $b>d$. Let $c=2x+a$ and $d=b-2y$, and compute

$p={c}^{2}+{d}^{2}=p+4ax+4{x}^{2}-4by+4{y}^{2},$ |

whence $x(a+x)=y(b-y)$. If $(x,y)=d$, cancel the factor of $d$ to get a new equation $X(a+x)=Y(b-y)$ with $(X,Y)=1$, so we can write

$mY=a+x=a+dX$ |

and

$mX=b-y=b-dY$ |

for some positive integer $m$. Then

$p={a}^{2}+{b}^{2}={(mY-dX)}^{2}+{(mX+dY)}^{2}=({m}^{2}+{d}^{2})({X}^{2}+{Y}^{2}),$ |

which contradicts the primality of $p$ since we have both ${m}^{2}+{d}^{2}\ge 2$ and ${X}^{2}+{Y}^{2}\ge 2$. We now proceed to existence.

By Euler’s criterion (or by
Gauss’s lemma), the congruence^{}

$${x}^{2}\equiv -1\phantom{\rule{veryverythickmathspace}{0ex}}(modp)$$ | (1) |

has a solution. By Dirichlet’s approximation theorem, there exist integers $a$ and $b$ such that

$$ | (2) |

$$ |

(2) tells us

$$ |

Write $u=|ax-bp|$. We get

$${u}^{2}+{a}^{2}\equiv {a}^{2}{x}^{2}+{a}^{2}\equiv 0\phantom{\rule{veryverythickmathspace}{0ex}}(modp)$$ |

and

$$ |

whence ${u}^{2}+{a}^{2}=p$, as desired.

To prove Thue’s lemma in another way, we will imitate a part of the proof of Lagrange’s four-square theorem. From (1), we know that the equation

$${x}^{2}+{y}^{2}=mp$$ | (3) |

has a solution $(x,y,m)$ with, we may assume, $$. It is enough to show that if $m>1$, then there exists $(u,v,n)$ such that $$ and

$${u}^{2}+{v}^{2}=np.$$ |

If $m$ is even, then $x$ and $y$ are both even or both odd; therefore,
in the identity^{}

$${\left(\frac{x+y}{2}\right)}^{2}+{\left(\frac{x-y}{2}\right)}^{2}=\frac{{x}^{2}+{y}^{2}}{2}$$ |

both summands are integers, and we can just take $n=m/2$ and conclude.

If $m$ is odd, write $a\equiv x\phantom{\rule{veryverythickmathspace}{0ex}}(modm)$ and $b\equiv y\phantom{\rule{veryverythickmathspace}{0ex}}(modm)$ with $$ and $$. We get

$${a}^{2}+{b}^{2}=nm$$ |

for some $$. But consider the identity

$$({a}^{2}+{b}^{2})({x}^{2}+{y}^{2})={(ax+by)}^{2}+{(ay-bx)}^{2}.$$ |

On the left is $n{m}^{2}p$, and on the right we see

$ax+by\equiv {x}^{2}+{y}^{2}$ | $\equiv $ | $0\phantom{\rule{veryverythickmathspace}{0ex}}(modm)$ | ||

$ay-bx\equiv xy-yx$ | $\equiv $ | $0\phantom{\rule{veryverythickmathspace}{0ex}}(modm).$ |

Thus we can divide the equation

$$n{m}^{2}p={(ax+by)}^{2}+{(ay-bx)}^{2}$$ |

through by ${m}^{2}$, getting an expression
for $np$ as a sum of two squares. The proof is complete^{}.

Remark: The solutions of the congruence (1) are explicitly

$$x\equiv \pm \left(\frac{p-1}{2}\right)!\phantom{\rule{veryverythickmathspace}{0ex}}(modp).$$ |

Title | proof of Thue’s Lemma |
---|---|

Canonical name | ProofOfThuesLemma |

Date of creation | 2013-03-22 13:19:08 |

Last modified on | 2013-03-22 13:19:08 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 10 |

Author | mathcam (2727) |

Entry type | Proof |

Classification | msc 11A41 |