## You are here

Homeproof of Thue's Lemma

## Primary tabs

# proof of Thue’s Lemma

We prove the uniqueness first: Suppose

$\displaystyle 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

$\displaystyle p=c^{2}+d^{2}=p+4ax+4x^{2}-4by+4y^{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

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

and

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

for some positive integer $m$. Then

$\displaystyle 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}\geq 2$ and $X^{2}+Y^{2}\geq 2$. We now proceed to existence.

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

$x^{2}\equiv-1\;\;(\mathop{{\rm mod}}p)$ | (1) |

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

$\left|a\frac{x}{p}-b\right|\leq\frac{1}{[\sqrt{p}]+1}<\frac{1}{\sqrt{p}}$ | (2) |

$1\leq a\leq[\sqrt{p}]<\sqrt{p}$ |

(2) tells us

$|ax-bp|<\sqrt{p}\;.$ |

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

$u^{2}+a^{2}\equiv a^{2}x^{2}+a^{2}\equiv 0\;\;(\mathop{{\rm mod}}p)$ |

and

$0<u^{2}+a^{2}<2p\;,$ |

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, $1\leq m<p$. It is enough to show that if $m>1$, then there exists $(u,v,n)$ such that $1\leq n<m$ 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\;\;(\mathop{{\rm mod}}m)$ and $b\equiv y\;\;(\mathop{{\rm mod}}m)$ with $|a|<m/2$ and $|b|<m/2$. We get

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

for some $n<m$. But consider the identity

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

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

$\displaystyle ax+by\equiv x^{2}+y^{2}$ | $\displaystyle\equiv$ | $\displaystyle 0\;\;(\mathop{{\rm mod}}m)$ | ||

$\displaystyle ay-bx\equiv xy-yx$ | $\displaystyle\equiv$ | $\displaystyle 0\;\;(\mathop{{\rm mod}}m)\;.$ |

Thus we can divide the equation

$nm^{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)!\;\;(\mathop{{\rm mod}}p)\;.$ |

## Mathematics Subject Classification

11A41*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prove that for any sets A, B, and C, An(BUC)=(AnB)U(AnC) by St_Louis

Apr 20

new image: information-theoretic-distributed-measurement-dds.png by rspuzio

new image: information-theoretic-distributed-measurement-4.2 by rspuzio

new image: information-theoretic-distributed-measurement-4.1 by rspuzio

new image: information-theoretic-distributed-measurement-3.2 by rspuzio

new image: information-theoretic-distributed-measurement-3.1 by rspuzio

new image: information-theoretic-distributed-measurement-2.1 by rspuzio

Apr 19

new collection: On the Information-Theoretic Structure of Distributed Measurements by rspuzio

Apr 15

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia