图厄引理关于线性同余的“小”方案

Thue's lemma is a simple lemma which essentially shows that there exists a small solution to a two-variable linear congruence, with many applications as we will see...

Essentially, it states that for a prime $p$ and a number $a \not \equiv 0$ mod p, we may find $0<x,y < \sqrt{p}$ so that the equivalence $ax \equiv \pm y$ mod $p$ is satisfied for some choice of $\pm$.

The proof is hard to motivate to a newcomer, so I'll try to explain it as clearly as possible- Essentially we want a pigeonhole argument to show a statement.

The main thing to notice is that if you take a number of the form $ax-y$ and another one of the form $ax-y$, their difference may easily be written in the form $ax-y$ as well.

Consider all $x,y$ with $0< x,y < \sqrt{p} + 1$. If we look at all numbers of the form $ax-y$, there are more than $p$ of these, since $p$, a prime is not a square.

Then by Pigeonhole, two of these expressions, say $ax_1-y_1, ax_2-y_2$, must be equivalent mod $p$, so that

$a(x_1-x_2) \equiv (y_1-y_2)$. But now note that since $1 \le x_1,x_2,y_1,y_2 < \sqrt{p}+1$ we have that $0<|x_1-x_2|, |y_1-y_2| < \sqrt{p}$, so $x=x_1-x_2, y=y_1-y_2$ gives us the solution we need.

Now, let's see this lemma at work. One of the most famous applications of Thue is to prove the following (a key ingredient to Fermat's Christmas theorem on sums of two squares):

Theorem: For any prime $p \equiv 1$ mod $4$, there exist $x,y$ with $x^2+y^2=p$.

First, let's note one thing- If we want to apply Thue, the $\pm$ is very annoying, so it makes sense to square the congruence- Then Thue states there is a solution to $a^2x^2 \equiv y^2$ mod $p$ with $0<x,y < \sqrt{p}$.

Now, we can proceed. I'll take for granted the fact that there exists an integer $N$ so that $p|N^2+1$. The proof of this doesn't really belong here since it requires some different number-theoretic argments, but if you want to prove it yourself, my hint is to let $N = \left( \dfrac{p-1}{2} \right) !$ and use Wilson's Theorem cleverly.

Note that $p|(N^2+1)x^2$ so $p|x^2+y^2$ if and only if we have $p| (N^2+1)x^2 - (x^2+y^2) = N^2x^2-y^2$.

That is, this occurs whenever $N^2x^2 \equiv y^2$ mod $p$.

Ah-ha! Then we can let $N=a$ and apply Thue's lemma to show the existence of a solution $x,y$ with $0<x,y < \sqrt{p}$, and this means we're done!

This example demonstrates the power of Thue's lemma, whose proof is very simple, but gives a very nontrivial statement.

Note: If you want a slightly harder challenge, show that all primes $1$ and $3$ mod $8$ may be written in the form $x^2+2y^2$.

$p$ is a prime and $k$ is an integer so that $p$ divides $k^2+5$. Prove that there are integers $x,y$ with $p^2=x^2+5y^2$.

Let $p$ be a prime for which there exists a positive integer $a$ such that $p$ divides $2a^2-1$. Prove that, there exist integers $b$ and $c$ so that, $p=2b^2-c^2$.

If $p$ is a prime of the form $3k+1$, prove there are integers $a,b$ such that $p=a^2+ab+b^2$.

Let $n\in\{-1,-2,-3\}$. If $n$ is a quadratic residue of a prime $p$, then there are integers $a,b$ so that, $a^2-nb^2=p$.

Two Dimensional version.

Let $n\geq2,r=\sqrt{n}$ and $a,b,c,d$ be arbitrary integers. There exist $w,x,y,z$ with at least one of $y,z$ non-zero such that \begin{align*} 0\leq |w|,|x|,|y|,|z|\leq r\newline w\equiv ay+bz\pmod n\newline x\equiv cy+dz\pmod n \end{align*}

Prove the generalization. Let $\alpha$ and $\beta$ are two real numbers so that $\alpha\beta \geq p$. Then for an integer $x$, there are integers $a,b$ with $0<|a|<\alpha$ and $0<|b|<\beta$ so that, \begin{align*} a & \equiv xb\pmod p \end{align*}