Il piccolo teorema di Fermat.

Perchè "piccolo"

...beh perchè esiste il grande teorema di Fermat (noto anche come congettura di Fermat (non è più una congettura ormai è il teorema di Wiles), o ultimo teorema di Fermat (FLT : "Fermat's Last Theorem" in inglese)).

L'enunciato del piccolo teorema di Fermat è il seguente:

Teorema: Sia p un numero primo. Per ogni intero n, si ha: n^p = n (mod p).

In altri termini nxnx..xn (p fattori) e n hanno lo stesso resto nella divisione per p, equivalentemente n^p - n è divisibile per p.

Questo è già un teorema un pò difficile (si vede al primo o terzo anno di università), cercheremo qui di darne una dimostrazione in termini elementari, ma se non capite subito, non spaventatevi, è normale.

Anagrammi.

Gli anagrammi della parola: amo sono 3! = 6 (precisamente sono: amo, aom, mao, moa, oma, oam)

Infatti abbiamo già visto che ci sono n! modi di ordinare n oggetti. Quindi se una parola è fatta di n lettere distinte, ogni ordinamento (o permutazione) è un anagramma e ci sono quindi n! anagrammi di questa parola. Se le lettere non sono tutte distinte, questo non è più vero.

Per esempio per la parola: ama  La permutazione che scambia la prima e la terza lettera non dà luogo a un anagramma. Però ogni anagramma di ama fornisce due anagrammi di amo.

Per esempio: maa dà luogo a mao e moa   (queste due possibilità corrispondono agli anagrammi di ao). Ci sono quindi:   3!/2! = 3 anagrammi di ama (sono ama, maa, aam).

Consideriamo la parola lalla.

Ogni anagramma di lalla fornisce 3! anagrammi di lapra (che corrispondono agli anagrammi di lpr cioè alle permutazioni di lpr perchè tutte le lettere sono distinte).

Per esempio lalla dà luogo a: lapra, larpa, palra, parla, rapla, ralpa

Quindi, (il numero di anagrammi di lalla) = (il numero di anagrammi di lapra) / 3!

D'altra parte, come abbiamo visto all'inizio, (il numero di anagrammi di lapra) =

(il numero di anagrammi di lepra)/ 2!

Siccome le lettere di lepra sono tutte distinte: (il numero di anagrammi di lepra) = 5!. Tornando indietro, concludiamo che: (il numero di anagrammi di lalla) = 5! / 3!2! = 10.

In generale se prendiamo una parola, L, di p lettere e se indichiamo con r_a il numero di a che contiene, con r_b il numero di b che contiene, ..., con r_z il numero di z che contiene, allora:

(il numero di anagrammi di L) = p! / (r_a!r_b!...r_z!)

Osservare che 1! = 1, quindi se tutte le lettere sono distinte ritroviamo che ci sono p! anagrammi di L.

Adesso possiamo dimostrare il piccolo teorema di Fermat.

Dimostrazione del teorema.

Abbiamo già visto che si possono costruire n^p parole di p lettere con un alfabeto di n lettere (ci sono 10⁵codici di 5 cifre con i caratteri ("lettere") 0,1,2,..,9).

Tra queste n^p parole , ci sono n (quante sono le lettere) parole formate da lettere tutte uguali (cioè parole con un unico anagramma). Togliamo queste parole. Rimangono n^p- n parole.

Tra queste n^p- n parole, prendiamone una, L. Questa parola ha più di un anagramma. Come abbiamo visto sopra: (il numero di anagrammi di L) = p! / (r_a!r_b!...r_z!).

Il numero p! / (r_a!r_b!...r_z!) è un numero intero (è il numero di anagrammi di L) e se lo scriviamo per esteso è della forma: (1x2x3x...xp) / (1x2x...xr_a)x(1x2x...xr_b)x...x(1x2x...xr_z).

Tutti i numeri r_a, r_b, ...,r_z sono strettamente più piccoli di p (perchè abbiamo tolto le parole formate da lettere tutte uguali). D'altra parte p essendo primo (è qui che interviene l'ipotesi) i suoi unici divisori sono 1 e p. Quindi p non si semplifica. Pertanto A_L = (il numero di anagrammi di L) è della forma pxk_L per un opportuno intero k, cioè A_L è un multiplo di p.

Quindi se togliamo L e tutti i suoi anagrammi, ci rimangono: n^p- n -  A_L = n^p- n - p.k_L   parole. A questo punto i casi sono due: o non rimangono più parole, cioè n^p- n - p.k_L = 0; oppure ne rimangono ancora ( n^p- n - p.k_L > 0).

Nel primo caso abbiamo finito: n^p- n = p.k_L e quindi n^p- n è divisibile per p.

Nel secondo caso, scegliamo una parola, T, tra quelle rimanenti. Ragionando come prima, il numero degli anagrammi di T è della forma: A_T = p.k_T . Quindi se togliamo T e tutti i suoi anagrammi, ci rimangono:  n^p- n -  A_L -  A_T = n^p- n - p.k_L  - p.k_T    parole.

Se non rimangono più parole, abbiamo finito (n^p- n = p.(k_L + k_T) è divisibile per p);  altrimenti andiamo avanti:  prendiamo un'altra parola, R, consideriamo i suoi anagrammi e poi togliamo R e tutti i suoi anagrammi, ecc ... Siccome il numero delle parole è finito arriverà un momento che le avremo tolte tutte, cioè avremo: n^p- n - p.k_L  - p.k_T - ... - p.k_S  = 0, quindi   n^p- n = p.(k_L + k_T + ... +k_S)  e n^p- n è divisibile per p. Il teorema è dimostrato.

                                                            Ritorno alla pagina principale "Congruenze"