Aritmetica modulare/Prime proprietà e applicazioni

Wikibooks, manuali e libri di testo liberi.

In questo modulo saranno presentati i primi usi delle congruenze, e verrà dimostrato il teorema di Fermat e la sua generalizzazione.

Indice

1 Criteri di divisibilità
2 Il teorema di Fermat
3 Il teorema di Eulero
4 Fattoriali

[modifica] 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\cdot10^k+a_{k-1}\cdot10^{k-1}+\cdots+a_1 \cdot10^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 d. Le dimostrazioni si possono ottenere esattamente con i metodi descritti sopra.

[modifica] 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}\equiv1\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.

[modifica] 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. 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, $φ(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_1a_2a_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 $φ(n)$ rispetto alla moltiplicazione.) La dimostrazione di questo teorema più generale può essere ottenuta ricalcando la prova qui presentata.

[modifica] 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 $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) = 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)\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$

Aritmetica modulare/Prime proprietà e applicazioni

Wikibooks, manuali e libri di testo liberi.

Indice

[modifica] Criteri di divisibilità

[modifica] Il teorema di Fermat

[modifica] Il teorema di Eulero

[modifica] Fattoriali

Visite

Strumenti personali

Navigazione

Comunità

Stampa/esporta

Ricerca

strumenti