Lemma di Thue

Il lemma di Thue, chiamato così dal matematico norvegese Axel Thue, è un lemma della teoria dei numeri che afferma che, per ogni numero primo p e per ogni intero $a\equiv ̸0modp$, la congruenza

$ax\equiv ymodp$

(dove $\equiv$ indica l'operazione modulo).

ammette una soluzione $(x_0,y_0)$ tale che $0<|x_0|<\sqrt{p},0<|y_0|<\sqrt{p}$.

Può essere usato per dimostrare il teorema di Fermat sulle somme di due quadrati.

Dimostrazione

Consideriamo i numeri ax - y (modulo p) tali che

$0\le x\le [\sqrt{p}],0\le y\le [\sqrt{p}]$

dove [a] indica la funzione parte intera di a (ovvero il più grande intero non maggiore di a). Questi valori sono in numero di $([\sqrt{p}]+1{)}^2>(\sqrt{p}-1+1{)}^2=p$. Quindi esistono due coppie $(x_1,y_1)$ e $(x_2,y_2)$ tali che $a{x}_1-y_1\equiv a{x}_2-y_{2}modp$; inoltre $x_1\ne x_2$, perché altrimenti si avrebbe

$\{\begin{array}{c}a{x}_1-y_1\equiv cmodp\\ a{x}_1-y_2\equiv cmodp\end{array}$

e quindi $y_1\equiv y_2$ e le coppie non sarebbero distinte. Consideriamo l'espressione

$a(x_1-x_2)-(y_1-y_2)=(a{x}_1-y_1)-(a{x}_2-y_2)$

Questa è palesemente congrua a 0 modulo n. $x_1-x_2$ è la differenza tra due quantità minori di $[\sqrt{p}]$, e quindi è essa stessa minore di $|\sqrt{p}|$. Allo stesso modo $y_1-y_2<\sqrt{p}$. Quindi ponendo

$x_0=x_1-x_2,y_0=y_1-y_2$

si ha la coppia desiderata.

Bibliografia

• David M. Burton, Elementary Number Theory, McGraw-Hill, 2007, ISBN 9780073051888