Aritmetica modulare/Congruenze lineari: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
congruenze semplici |
Nessun oggetto della modifica |
||
Riga 22:
:<math>x_k=\overline{x}+kN</math>
sono ancora soluzioni delle congruenza per ogni valore intero di ''k'' (in particolare, <math>x_0=\overline{x}</math>). Per ''k'' < ''d'', inoltre, questi valori sono minori di ''n'', e quindi sono incongruenti modulo ''n''. Questi sono tutti e soli i valori minori di ''n'' che, modulo ''N'', sono congrui a <math>\overline{x}</math>. Se ''y'', modulo ''n'', è diverso da tutti gli <math>x_i</math>, allora non è una soluzione della congruenza perché non vi sono altre soluzioni modulo ''N'': quindi la congruenza originale ammette esattamente ''d'' soluzioni modulo ''n''.
== Sistemi di congruenze lineari ==
Una volta risolte congruenze in un unico modulo, è possibile passare a risolvere ''sistemi'' di congruenze lineari: la situazione di partenza è un sistema del tipo
:<math>\begin{cases} x\equiv a_1\mod n_1\\ x\equiv a_2\mod n_2 \\ \vdots \\ x\equiv a_k\mod n_k\end{cases}</math>
dove MCD(''n<sub>i</sub>,n<sub>j</sub>'')=1 per ogni <math>i\neq j</math>.
Ci si può sempre ridurre a questo caso a partire da un sistema in cui ogni equazione è del tipo
:<math>a_ix\equiv b_i\mod n_i</math>
nel caso in cui in quest'ultima esistono soluzioni, risolvendo la congruenza lineare come nel paragrafo precedente, eventualmente modificando il modulo.
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)^k n_j}}{n_i}</math>, ovvero il prodotto di tutti gli <math>n_j</math> eccetto <math>n_i</math>: questo è ovviamente divisibile per tutti gli <math>n_j</math>, eccetto <math>n_i</math>, con cui è coprimo perché è il prodotto di fattori coprimi con <math>n_i</math>. Di conseguenza ogni <math>N_i</math> ha un inverso modulo <math>n_i</math>; sia <math>N_i^*</math>. Consideriamo il numero
:<math>\overline{x}=a_1N_1^*+a_2N_2^*+\cdots+a_kN_k^*</math>
Modulo <math>n_i</math> (per ogni ''i''), si cancellano tutti i termini meno <math>a_iN_iN_i^*</math>. Quindi
:<math>\overline{x}\equiv a_iN_iN_i^*\mod n_i\equiv a_i\mod n_i</math>
perché il prodotto <math>N_iN_i^*</math> è per definizione, congruo a 1 modulo <math>n_i</math>. Quindi il numero <math>\overline{x}</math> è una soluzione del sistema.
Abbiamo quindi ''N'' soluzioni diverse, una per ogni sequenza degli ''a''. Consideriamo un'altra soluzione <math>\overline{y}</math> del sistema. La differenza <math>\overline{x}-\overline{y}</math> è congrua a 0 per ogni <math>n_i</math>, cioè è divisibile per ogni <math>n_i</math>, e quindi è divisibile per il loro prodotto ''N''. Quindi la soluzione è unica modulo ''N''.
== Isomorfismi ==
{| align="right" border=1 width="20%"
|+ Modulo 45 visto come modulo 9 per modulo 5
|-
|rowspan=2 colspan=2|
!colspan=5 align="center"| mod 5
|-
! 0 || 1 || 2 || 3 || 4
|-
!rowspan=9| mod 9
!0
| 0 || 36 || 27 || 18 || 9
|-
!1
| 10 || 1 || 37 || 28 || 19
|-
!2
| 20 || 11 || 2 || 38 || 29
|-
!3
| 30 || 21 || 12 || 3 || 39
|-
!4
| 40 || 31 || 22 || 13 || 4
|-
!5
| 5 || 41 || 32 || 23 || 14
|-
!6
| 15 || 6 || 42 || 33 || 24
|-
!7
| 25 || 16 || 7 || 43 || 34
|-
!8
| 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 s ipuò vedere facilmente, rispetta le operazioni. In linguaggio algebrico, questo equivale a dire che c'è un ''isomorfismo'' tra il prodotto cartesiano l'insieme <math>\mathbb{Z}_N</math>.
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
:<math>x^5-6x^4+3x^3-5x+4\equiv 0 \mod 15</math>
è possibile risolvere invece le due congruenze
:<math>2x^5-6x^4+3x^3-5x+5\equiv 0 \mod 3\Longrightarrow 2x^5-2x+2\equiv 0\mod 3</math>
:<math>2x^5-6x^4+3x^3-5x+5\equiv 0 \mod 5\Longrightarrow 2x^5-x^4+3x^3\equiv 0\mod 5</math>
Ora <math>x^5</math> assume, per il piccolo teorema di Fermat, gli stessi valori di ''x''; quindi la congruenza modulo 3 è impossibile, e così è quella originaria.
Questo sistema è utile per trovare il numero di soluzioni di un'equazione a partire dal numero di soluzioni della stessa equazione in moduli più piccoli: se ad esempio
:<math>f(x)\equiv 0\mod n</math>
è spezzata in
:<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''.
[[categoria:Aritmetica modulare]]
| |||