Aritmetica modulare/Prime proprietà e applicazioni

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$