Aritmetica modulare/Congruenze lineari: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
finito capitolo |
||
Riga 35:
Poiché esistono <math>N=n_1n_2\cdots n_k</math> diverse scelte di sequenze <math>(a_1,a_2\ldots,a_k)</math>, è naturale cercare le soluzioni del sistema nel modulo ''N'': dimostreremo che, in questo modulo, la soluzione esiste ed è unica.
Definiamo infatti <math>N_i=\frac{\prod_{j=1
:<math>\overline{x}=a_1N_1^*+a_2N_2^*+\cdots+a_kN_k^*</math>
Riga 81:
| 35 || 26 || 17 || 8 || 44
|}
L'esistenza e l'unicità modulo ''N'' delle soluzioni dei sistemi di congruenze lineari permette di stabilire una corrispondenza biunivoca dal prodotto cartesiano <math>\mathbb{Z}_{n_1}\times\mathbb{Z}_{n_2}\times\cdots\times\mathbb{Z}_{n_k}</math> a <math>\mathbb{Z}_N</math> che, come
Questo può essere sfruttato per risolvere delle congruenze, ad esempio di un polinomio di grado elevato, da un modulo ''n'' qualsiasi a diversi moduli più piccoli. Ad esempio, volendo trovare le soluzioni di
Riga 95:
:<math>\begin{cases} f(x)\equiv 0\mod n_1\\ f(x)\equiv 0\mod n_2 \\ \vdots \\ f(x)\equiv 0\mod n_k\end{cases}</math>
dove i vari moduli sono a due a due coprimi, e <math>\rho(n_i)</math> indica il numero di soluzioni della congruenza modulo <math>n_i</math>, allora <math>\rho(n)=\rho(n_1)\rho(n_2)\cdots\rho(n_k)</math> perché ogni possibile gruppo di soluzioni nei diversi moduli genera una diversa soluzione modulo ''n''.
== Il lemma di Thue ==
Un'altra congruenza lineare interessante, questa volta nella due incognite ''x'' e ''y'', è
:<math>ax\equiv y\mod p</math>
dove ''p'' è un numero primo
È ovvio che questa congruenza ha ''n'' soluzioni, una per ogni scelta di ''X'': 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.
Consideriamo infatti i numeri ''ax'' - ''y'' (modulo ''p'') tali che
:<math>0\leq x\leq[\sqrt{p}],~~0\leq y\leq[\sqrt{p}]</math>
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_x1-y_1\equiv ax_2-y_2\mod n</math>; inoltre <math>x_1\neq x_2</math>, perché altrimenti si avrebbe
:<math>ax_1-y_1\equiv c\mod n\equiv ax_1-y_2</math>
e quindi
:<math>y_1\equiv ax_1-c</math>
e
:<math>y_2\equiv ax_1-c</math>
ovvero <math>y_1=y_2</math> e le coppie non sarebbero distinte. Consideriamo l'espressione
:<math>a(x_1-x_2)-(y_1-y_2)=(ax_1-y_1)-(ax_2-y_2)</math>
Questa è palesemente congrua a 0 modulo ''n''. <math>x_1-x_2</math> è la differenza tra due quantità minori di <math>[\sqrt{p}]</math>, e quindi è essa stessa minore di <math>|\sqrt{p}|</math>. Allo stesso modo <math>y_1-y_2<\sqrt{p}</math>. Quindi ponendo
:<math>x_0=x_1-x_2, ~~y_0=y_1-y_2</math>
si ha la coppia desiderata.
Questo lemma può essere usato per dimostrare il teorema di Fermat sulle somme di due quadrati, che afferma che un primo ''p'' è rappresentabile come somma di due quadrati se e solo se <math>p\equiv 1\mod 4</math>.
[[categoria:Aritmetica modulare]]
| |||