Aritmetica modulare/Congruenze lineari: differenze tra le versioni

È ovvio che questa congruenza ha ''np'' soluzioni, una per ogni scelta di ''Xx'': il lemma di Thue afferma che esiste una coppia <math>(x_0,y_0)</math> che la verifica tale che <math>|x_0|,|y_0|<\sqrt{p}</math> ed entrambi sono diversi da 0.

dove [''a''] indica la parte intera di ''a'', ovvero il più piccolo intero non maggiore di ''a''. Questi valori sono in numero di <math>([\sqrt{p}]+1)^2>(\sqrt{p}-1+1)^2=p</math>. Quindi esistono due coppie <math>(x_1,y_1)</math> e <math>(x_2,y_2)</math> tali che <math>a_x1ax_1-y_1\equiv ax_2-y_2\mod n</math>; inoltre <math>x_1\neq x_2</math>, perché altrimenti si avrebbe

:<math>\begin{cases}ax_1-y_1\equiv c\mod np\\equiv ax_1-y_2\equiv c\mod p\end{cases}</math>

:<math>y_1\equiv ax_1-c\mod p</math>

:<math>y_2\equiv ax_1-c\mod p</math>