Aritmetica modulare/Prime proprietà e applicazioni: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
fermat+eulero |
fattoriali |
||
Riga 62:
Questo teorema è in realtà un caso particolare di una proposizione molto più generale, che riguarda ogni gruppo: se ''a'' è un elemento di un gruppo ''G'' di ordine ''n'' (ovvero con ''n'' elementi) allora <math>a^n=e</math>, dove ''e'' è l'elemento neutro del gruppo. (Ricordiamo che l'insieme degli elementi invertibili di <math>\mathbb{Z}_n</math> è un gruppo di ordine <math>\phi(n)</math> rispetto alla moltiplicazione.) La dimostrazione di questo teorema più generale può essere ottenuta ricalcando la prova qui presentata.
== Fattoriali ==
Un altro teorema importante e di facile dimostrazione è il teorema di Wilson, che riguarda il rapporto tra i fattoriali e i numeri primi. (Il fattoriale di ''n'', indicato come ''n''!, è il prodotto <math>1\cdot 2\cdot 3\cdots n</math>.) Afferma che
:<math>(n-1)!\equiv -1 \mod n</math>
se e solo se ''n'' è primo.
Se ''n'' non è primo, allora tutti i fattori di ''n'' sono minori di ''n'', e quindi sono fattori di (''n'' -1)!, ovvero <math>(n-1)!\equiv 0\mod n</math>. Di conseguenza ''n'' non può verificare la proprietà precedente.
Sia ora ''n'' primo, ''n'' >2 (''n'' =2 verifica banalmente il teorema), e consideriamo le coppie di inversi. Se le moltiplichiamo tutte tra loro abbiamo 1; poiché ''n'' è primo, inoltre, tutti gli elementi di <math>\mathbb{Z}_n</math>, eccetto lo 0, hanno un inverso. Moltiplicandoli tutti tra loro, possiamo dunque raggruppare tutti gli elementi il cui inverso è diverso da sé stesso e semplificare le coppie. Gli elementi che coincidono con il proprio inverso devono verificare
:<math>x^2\equiv 1\mod n</math>
cioè
:<math>(x^2-1)=(x+1)(x-1)=kn</math>
per qualche ''k''. Questo equivale a dire che ''x'' +1 o ''x'' -1 dividono ''n'', cioè ''x'' è congruo a 1 o ''n'' -1 modulo ''n''. Quindi
:<math>(n-1)!\equiv 1\cdot (n-1)\mod n\equiv -1 \mod n</math>
come volevasi dimostrare.
Usando il teorema di Wilson è facile dimostrare la seguente proprietà dei coefficienti binomiali:
:<math>\binom{p-1}{a}\equiv (-1)^a\mod p</math>
per ogni ''p'' primo. Infatti, osserviamo innanzitutto che, per definizione,
:<math>\binom{p-1}{a}=\frac{(p-1)!}{a!(p-1-a)!}</math>
Inoltre
:<math>(p-1-a)!=\frac{(p-1)!}{(p-a)(p-a+1)\cdots(p-1)}\equiv \frac{-1}{(-a)(-a+1)\cdots (-2)(-1)}\mod n</math>
dove si è usata la frazione per denotare la divisione, ovvero la moltiplicazione per l'inverso, possibile in quanto nessuna delle quantità coinvolte è divisibile per ''p''. Raccogliendo -1 da ogni fattore del prodotto <math>(-a)(-a+1)\cdots (-2)(-1)</math> otteniamo
<math>(p-1-a)!\equiv\frac{-1}{(-1)^a a!}</math>
e ritornando al coefficiente binomiale
:<math>\binom{p-1}{a}=\frac{(p-1)!}{a!(p-1-a)!}\equiv\frac{-1}{a!\frac{-1}{(-1)^a a!}}\mod n\equiv (-1)^a\mod n</math>
[[categoria:Aritmetica modulare]]
| |||