# Aritmetica modulare/Prime proprietà e applicazioni

Aritmetica modulare
Copertina Bibliografia Tutti i moduli · Sviluppo
    CopertinaAritmetica modulare/Copertina
* La relazione di congruenzaAritmetica modulare/La relazione di congruenza
* Prime proprietà e applicazioniAritmetica modulare/Prime proprietà e applicazioni
* Congruenze lineariAritmetica modulare/Congruenze lineari
* Polinomi in aritmetica modulareAritmetica modulare/Polinomi in aritmetica modulare
* Radici primitiveAritmetica modulare/Radici primitive
* Congruenze quadraticheAritmetica modulare/Congruenze quadratiche
* Alcune applicazioniAritmetica modulare/Alcune applicazioni
* BibliografiaAritmetica modulare/Bibliografia
* EserciziAritmetica modulare/Esercizi
Modifica il sommario
In questo modulo saranno presentati i primi usi delle congruenze, e verrà dimostrato il teorema di Fermat e la sua generalizzazione.

## Criteri di divisibilità

Attraverso l'uso delle congruenze è semplice dimostrare i noti criteri di divisibilità per 3 e per 11. Essi sono:
* un numero è divisibile per 3 (o per 9) se lo è la somma delle sue cifre;
* un numero è divisibile per 11 se lo è la differenza tra le sue cifre di posto pari e le sue cifre di posto dispari.
Sia infatti n un qualsiasi numero. Scriverlo in base 10 significa scriverlo come
    $n=a_{k}\cdot 10^{k}+a_{k-1}\cdot 10^{k-1}+\cdots +a_{1}\cdot 10^{1}+a_{0}$
Ora, $10\equiv 1\mod 3$, e quindi $10^{k}\equiv 1^{k}\mod 3\equiv 1\mod 3$. La congruenza può essere riscritta come
    $n\equiv 1\cdot a_{k}+1\cdot a_{k-1}+\cdots +1\cdot a_{1}+\cdot a_{0}\mod 3\equiv a_{k}+a_{k-1}+\cdots +a_{1}+a_{0}\mod 3$
Poiché inoltre essere divisibile per 3 equivale ad essere congruo a 0 modulo 3, n è quindi multiplo di 3 se e solo se lo è la somma delle sue cifre; non solo, ma questa caratteristica è un po' più forte, perché n è esattamente congruo alla somma delle sue cifre.
La stessa dimostrazione si applica nel caso della divisibilità per 9; nel caso di 11, invece, bisogna considerare i due casi
    $10^{k}\equiv {\begin{cases}1\mod 11&{\text{per k pari}}\\-1\mod 11&{\text{per k dispari}}\end{cases}}$
Di conseguenza
    $n\equiv a_{0}-a_{1}+a_{2}-\cdots +(-1)^{k}a_{k}\mod 11$
Questi risultati possono essere generalizzati se il numero n è scritto in una base b qualunque. In particolare, per i d tali che $b\equiv 1\mod d$, n è divisibile per d se e solo se lo è la somma delle sue cifre quando è scritto in base b; invece, se $b\equiv -1\mod d$ allora la divisibilità di n è equivalente a quella della differenza tra le somme delle cifre di posto dispari e di posto pari, quando n è scritto in base b. Le dimostrazioni si possono ottenere esattamente con i metodi descritti sopra.

## Il teorema di Fermat

Il teorema di Fermat (spesso chiamato "piccolo" per distinguerlo dall'Ultimo teorema di Fermat) è un risultato fondamentale dell'aritmetica modulare. Afferma che, dato un numero primo p, per ogni a si ha
    $a^{p}\equiv a\mod p$
oppure, equivalentemente, che se a non è divisibile per p allora
    $a^{p-1}\equiv 1\mod p$
L'equivalenza tra le due formulazioni è ovvia, perché l'unico caso in cui la seconda forma non si applica è quando p|a, cioè quando $a\equiv 0\mod p$, che verifica banalmente la prima uguaglianza.
Esistono diverse dimostrazioni del teorema; la prima non fa uso di proprietà dell'aritmetica modulare, ma procede per induzione su a, dimostrando la prima delle due forme:
* se a =0 il teorema è ovvio;
* sia vero il teorema per ogni numero naturale fino ad a. Allora per il teorema del binomio
    $(a+1)^{p}=a^{p}+{\binom {p}{1}}a^{p-1}+{\binom {p}{2}}a^{p-2}+\cdots +{\binom {p}{p-1}}a^{1}+1$
Ogni coefficiente binomiale ${\binom {p}{k}}$ è divisibile per p: infatti
    ${\binom {p}{k}}={\frac {p!}{k!(p-k)!}}$
e il denominatore non può essere diviso da p, perché è un numero primo, mentre p divide il numeratore. Quindi, passando al modulo p, abbiamo
    $(a+1)^{p}\equiv a+0+0+\cdots +1\mod p\equiv a+1\mod p$
stabilendo il risultato per ogni a.
Un'argomentazione molto più trasparente e con molte più potenzialità è quella data da Eulero. Fissiamo a, e consideriamo i numeri
    $1a,2a,3a,\ldots ,(p-1)a$
Se due di essi fossero uguali, ad esempio ia e ja, allora si avrebbe
    $ia\equiv ja\mod p\Longrightarrow (i-j)a\equiv 0\mod p$
e poiché a, non essendo divisibile per p, è coprimo con p, si deve avere i = j. Quindi i valori 1a, 2a, 3a, ... ,(p-1)a sono tutti diversi e non nulli, e quindi corrispondono in qualche ordine ai valori 1, 2, 3, ... p -1. Moltiplicandoli tutti tra loro abbiamo
    $(1a)(2a)(3a)\cdots [(p-1)a]\equiv 1\cdot 2\cdot 3\cdots (p-1)\mod p$
ovvero $[1\cdot 2\cdot 3\cdots (p-1)]a^{p-1}\equiv 1\cdot 2\cdot 3\cdots (p-1)\mod p$ A questo punto basta semplificare il prodotto $1\cdot 2\cdot 3\cdots (p-1)$ per ottenere il teorema.

## Il teorema di Eulero

Una generalizzazione del piccolo teorema è data dal teorema di Eulero, che coinvolge la funzione di Eulero $\phi (n)$ che ricordiamo essere, per ogni n, il numero di interi coprimi con n e minori di n. Il teorema di Eulero afferma che
    $a^{\phi (n)}\equiv 1\mod n$
per ogni a coprimo con n. Questo si riduce al piccolo teorema notando che, se p è primo, $\phi (n)=n-1$
La dimostrazione è essenzialmente quella del teorema di Fermat: detti $a_{1},a_{2},a_{3},\cdots a_{\phi (n)}$ gli interi coprimi con n, i numeri
    $aa_{1},aa_{2},aa_{3},\cdots aa_{\phi (n)}$
sono tutti diversi tra loro e tutti coprimi con n, e quindi sono uguali, in qualche ordine, a $a_{1},a_{2},a_{3},\cdots a_{\phi (n)}$. Moltiplicandoli tutti tra loro si ottiene
    $(aa_{1})(aa_{2})(aa_{3})\cdots (aa_{\phi (n)})\equiv a_{1}a_{2}a_{3}\cdots a_{\phi (n)}\mod n$
    $a^{\phi (n)}\equiv 1\mod n$
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 $a^{n}=e$, dove e è l'elemento neutro del gruppo. (Ricordiamo che l'insieme degli elementi invertibili di $\mathbb {Z} _{n}$ è un gruppo di ordine $\phi (n)$ rispetto alla moltiplicazione.) La dimostrazione di questo teorema più generale può essere ottenuta ricalcando la prova qui presentata.

## Fattoriali e teorema di Wilson

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 $1\cdot 2\cdot 3\cdots n$.) Afferma che
    $(n-1)!\equiv -1\mod n$
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 $(n-1)!\equiv 0\mod n$. 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 $\mathbb {Z} _{n}$, 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
    $x^{2}\equiv 1\mod n$
cioè
    $(x^{2}-1)=(x+1)(x-1)=kn$
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
    $(n-1)!\equiv 1\cdot (n-1)\mod n\equiv -1\mod n$
come volevasi dimostrare.
Usando il teorema di Wilson è facile dimostrare la seguente proprietà dei coefficienti binomiali:
    ${\binom {p-1}{a}}\equiv (-1)^{a}\mod p$
per ogni p primo. Infatti, osserviamo innanzitutto che, per definizione,
    ${\binom {p-1}{a}}={\frac {(p-1)!}{a!(p-1-a)!}}$
Inoltre
    $(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$
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 $(-a)(-a+1)\cdots (-2)(-1)$ otteniamo $(p-1-a)!\equiv {\frac {-1}{(-1)^{a}a!}}$ e ritornando al coefficiente binomiale
    ${\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$