Aritmetica modulare/Prime proprietà e applicazioni

Template:Aritmetica modulare 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 1 0^{k} + a_{k - 1} \cdot 1 0^{k - 1} + \dots + a_{1} \cdot 1 0^{1} + a_{0}

Ora, $10 \equiv 1 mod 3$ , e quindi $1 0^{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} + \dots + 1 \cdot a_{1} + \cdot a_{0} mod 3 \equiv a_{k} + a_{k - 1} + \dots + 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

1 0^{k} \equiv {\begin{matrix} 1 mod 11 & per k pari \\ - 1 mod 11 & per k dispari \end{matrix}

Di conseguenza

n \equiv a_{0} - a_{1} + a_{2} - \dots + (- 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} + \dots + (\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 + \dots + 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

1 a, 2 a, 3 a, \dots, (p - 1) a

Se due di essi fossero uguali, ad esempio ia e ja, allora si avrebbe

i a \equiv j a mod p ⟹ (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

(1 a) (2 a) (3 a) \dots [(p - 1) a] \equiv 1 \cdot 2 \cdot 3 \dots (p - 1) mod p

ovvero $[1 \cdot 2 \cdot 3 \dots (p - 1)] a^{p - 1} \equiv 1 \cdot 2 \cdot 3 \dots (p - 1) mod p$ A questo punto basta semplificare il prodotto $1 \cdot 2 \cdot 3 \dots (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 $ϕ (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^{ϕ (n)} \equiv 1 mod n

per ogni a coprimo con n. Questo si riduce al piccolo teorema notando che, se p è primo, $ϕ (n) = n - 1$

La dimostrazione è essenzialmente quella del teorema di Fermat: detti $a_{1}, a_{2}, a_{3}, \dots a_{ϕ (n)}$ gli interi coprimi con n, i numeri

a a_{1}, a a_{2}, a a_{3}, \dots a a_{ϕ (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}, \dots a_{ϕ (n)}$ . Moltiplicandoli tutti tra loro si ottiene

(a a_{1}) (a a_{2}) (a a_{3}) \dots (a a_{ϕ (n)}) \equiv a_{1} a_{2} a_{3} \dots a_{ϕ (n)} mod n

a^{ϕ (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 $ℤ_{n}$ è un gruppo di ordine $ϕ (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 \dots 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 $ℤ_{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) = k n

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) \dots (p - 1)} \equiv \frac{- 1}{(- a) (- a + 1) \dots (- 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) \dots (- 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

Template:Avanzamento

Aritmetica modulare/Prime proprietà e applicazioni

Indice

Criteri di divisibilità

Il teorema di Fermat

Il teorema di Eulero

Fattoriali e teorema di Wilson

Menu di navigazione

Aritmetica modulare/Prime proprietà e applicazioni

Criteri di divisibilità

Il teorema di Fermat

Il teorema di Eulero

Fattoriali e teorema di Wilson

Menu di navigazione

Ricerca