Dimostrazione piccolo teorema di Fermat
Salve ragazzi, volevo suggerirvi una dimostrazione davvero simpatica (non mia purtroppo ) del piccolo teorema di Fermat.
Il teorema afferma che:
\[a^p \equiv a \mod p\]
con p primo.
Che ne dite di dimostrarla tramite un ragionamento di tipo combinatorio?
Quando la ho letta, mi sono detto: mannaggia quel demonio mannaggia
Il teorema afferma che:
\[a^p \equiv a \mod p\]
con p primo.
Che ne dite di dimostrarla tramite un ragionamento di tipo combinatorio?
Quando la ho letta, mi sono detto: mannaggia quel demonio mannaggia
Risposte
Spiegati
Forse è meglio.
Per come ho letto io la dimostrazione, si può schematizzare nei seguenti passi.
(1) Si trovi il numero di stringhe di $p$ perline che si possono formare avendo a disposizione $p$ perline di $a$ colori diversi. Sempre con $p$ primo.
(2) Tra tali stringhe escludere le stringhe formate da perline di un solo colore.
(3) A questo punto colleghiamo gli estremi di ciascuna stringa per ottenere collane.
(3) Dimostrare che se $p$ è primo, le collane possono essere divise in $k$ insiemi di esattamente $p$ elementi.
Praticamente occorre dimostrare che esistono esattamente $p$ collane uguali, cioè collane che sono completamente sovrapponibili.
Da queste considerazioni, si può dedurre che il numero $a^p - a$ è divisibile per $p$
La chiave sta nel punto (3)
Per come ho letto io la dimostrazione, si può schematizzare nei seguenti passi.
(1) Si trovi il numero di stringhe di $p$ perline che si possono formare avendo a disposizione $p$ perline di $a$ colori diversi. Sempre con $p$ primo.
(2) Tra tali stringhe escludere le stringhe formate da perline di un solo colore.
(3) A questo punto colleghiamo gli estremi di ciascuna stringa per ottenere collane.
(3) Dimostrare che se $p$ è primo, le collane possono essere divise in $k$ insiemi di esattamente $p$ elementi.
Praticamente occorre dimostrare che esistono esattamente $p$ collane uguali, cioè collane che sono completamente sovrapponibili.
Da queste considerazioni, si può dedurre che il numero $a^p - a$ è divisibile per $p$
La chiave sta nel punto (3)
scindiamo i casi:
-quando le perline sono tutte dello stesso colore
-quando le perline non sono tutte dello stesso colore
se fosse una stringa (=fila di posti al cinema per esempio
) allora il numero di modi per "riempire" i posti avendo a disposizione \(\displaystyle a \) perline (queste sono perline che vanno al cinema) è \(\displaystyle a \cdot a \cdot a...=a^p \)
quando invece si forma un "anello" (=struttura rotonda), nel secondo caso dobbiamo dividere per p, cioè il numero delle rotazioni in quanto cosi noi contiamo anche le rotazioni della stessa disposizione di perline. Prima di effettuare la divisione togliamo tutte le disposizioni del primo caso che tratteremo a parte, esse sono a, una per colore.
riassumendo il numero di modi per disporre perline colorate è \(\displaystyle \frac{a^p-a}{p}+a \)
sicuramente è intero questo numero (non possiamo avere 3,12 modi di disporre perline), percio essendo anche a intero, abbiamo che \(\displaystyle \frac{a^p-a}{p} \) è intero, quindi \(\displaystyle a^p \equiv a \pmod{p} \)
-quando le perline sono tutte dello stesso colore
-quando le perline non sono tutte dello stesso colore
se fosse una stringa (=fila di posti al cinema per esempio
) allora il numero di modi per "riempire" i posti avendo a disposizione \(\displaystyle a \) perline (queste sono perline che vanno al cinema) è \(\displaystyle a \cdot a \cdot a...=a^p \)quando invece si forma un "anello" (=struttura rotonda), nel secondo caso dobbiamo dividere per p, cioè il numero delle rotazioni in quanto cosi noi contiamo anche le rotazioni della stessa disposizione di perline. Prima di effettuare la divisione togliamo tutte le disposizioni del primo caso che tratteremo a parte, esse sono a, una per colore.
riassumendo il numero di modi per disporre perline colorate è \(\displaystyle \frac{a^p-a}{p}+a \)
sicuramente è intero questo numero (non possiamo avere 3,12 modi di disporre perline), percio essendo anche a intero, abbiamo che \(\displaystyle \frac{a^p-a}{p} \) è intero, quindi \(\displaystyle a^p \equiv a \pmod{p} \)
Visto che non ne parli: se p non fosse primo cosa cambierebbe?
la formula \(\displaystyle \frac{a^n-a}{n}+a \) non funziona per n generico.
per esempio prendendo n=6 potrebbe esserci una colorazione come \(\displaystyle XYXYXY \) che non ha 5 rotazioni equivalenti, ma solo una (\(\displaystyle YXYXYX \) ) percio dividere per n (=6) non ha senso.
in generale quando esiste una colorazione di classe k (cioè quelle da cui è possibile ottenere esattamente k-1 colorazioni diverse ruotando di n) vale che \(\displaystyle k \mid n \). Questo è chiaro, infatti abbiamo che \(\displaystyle k+k+k+k+k+k+k+k..=n \) perche dopo una rotazione di n ci ritroviamo alla situazione iniziale, e se \(\displaystyle k \not \mid n \) abbiamo che il risultato raggiunto dopo una rotazione di n (una rotazione competa) è diverso da quello ottenuto ruotando di k per un certo numero di volte x, non è possibile.
Es. \(\displaystyle YXYXYX \) è di classe 2(k=2), e con 2,4,6 rotazioni otteniamo la stessa stringa, cioè ruotando per 2(=k) un certo numero di volte
percio abbiamo che con \(\displaystyle n \) primo, le uniche classi k possibili sono \(\displaystyle 1 \) e \(\displaystyle p \) siccome \(\displaystyle k \mid p \). Cioè la colorazione di classe 1 ( AAAAAA) e le colorazioni di classe 6 (ABCDEF).
Da cui la formula sopra trovata.
per esempio prendendo n=6 potrebbe esserci una colorazione come \(\displaystyle XYXYXY \) che non ha 5 rotazioni equivalenti, ma solo una (\(\displaystyle YXYXYX \) ) percio dividere per n (=6) non ha senso.
in generale quando esiste una colorazione di classe k (cioè quelle da cui è possibile ottenere esattamente k-1 colorazioni diverse ruotando di n) vale che \(\displaystyle k \mid n \). Questo è chiaro, infatti abbiamo che \(\displaystyle k+k+k+k+k+k+k+k..=n \) perche dopo una rotazione di n ci ritroviamo alla situazione iniziale, e se \(\displaystyle k \not \mid n \) abbiamo che il risultato raggiunto dopo una rotazione di n (una rotazione competa) è diverso da quello ottenuto ruotando di k per un certo numero di volte x, non è possibile.
Es. \(\displaystyle YXYXYX \) è di classe 2(k=2), e con 2,4,6 rotazioni otteniamo la stessa stringa, cioè ruotando per 2(=k) un certo numero di volte
percio abbiamo che con \(\displaystyle n \) primo, le uniche classi k possibili sono \(\displaystyle 1 \) e \(\displaystyle p \) siccome \(\displaystyle k \mid p \). Cioè la colorazione di classe 1 ( AAAAAA) e le colorazioni di classe 6 (ABCDEF).
Da cui la formula sopra trovata.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo