Rispondo qui alla richiesta di alcuni utenti bisognosi...
Teorema (piccolo) di Fermat: per ogni $ p\in\mathfrak{P} $ ed ogni $ a\in\mathbb{Z} $: $ a^p \equiv a \bmod p $.
Dim.: come già altrove è stato dimostrato (click!): $ \displaystyle\binom{p}{k}\equiv 0 \bmod p $, se $ p\in\mathfrak{P} $ e $ k = 1, 2, \ldots, p-1 $. Ergo, in base al teorema binomiale di Newton, e nelle ipotesi del teorema: $ \displaystyle a^p \equiv \sum_{k=0}^{p} \binom{p}{k} (a-1)^k \equiv 1 + (a-1) \equiv a \bmod p $, q.e.d.
Lemma: per ogni $ n\in\mathbb{N}_0 $ ed ogni $ a\in\mathbb{Z} $ che sia coprimo con $ n $, la mappa $ \Phi(\cdot): \mathcal{T}_n \mapsto \mathcal{T}_n: x \mapsto ax \bmod n $ è iniettiva, e quindi biunivoca, essendo $ \mathcal{T}_n := \{k\in\mathbb{N}_0: k \leq n\mbox{ }\wedge\mbox{ }\gcd(n,k) = 1\} $ l'insieme dei totativi di $ n $.
Dim.: siano $ x_1, x_2\in\mathcal{T}_n $. E allora, per costruzione: $ \Phi(x_1) = \Phi(x_2) $ sse $ ax_1 \equiv ax_2 \bmod n $, ovvero sse $ x_1 \equiv x_2 \bmod n $, dal lemma di Euclide, dacché si suppone $ \gcd(a,n) = 1 $. E allora $ x_1 = x_2 $, poiché $ 0 \leq |x_1 - x_2| < n $. Segue la tesi, q.e.d.
Teorema di Euler-Fermat: per ogni $ n\in\mathbb{N}_0 $ ed ogni $ a\in\mathbb{Z} $ che sia coprimo con $ n $: $ a^{\varphi(n)} \equiv 1 \bmod n $, ove $ \varphi(\cdot) $ denota (al solito) la funzione dei totienti di Eulero.
Dim.: per il lemma precedente $ \displaystyle\prod_{x\in\mathcal{T}_n} x \equiv \prod_{x\in\mathcal{T}_n} ax \equiv a^{\varphi(n)} \prod_{x\in\mathcal{T}_n} x $, siccome $ \varphi(n) := |\mathcal{T}_n| $. E del resto $ \displaystyle\gcd\!\left(n, \prod_{x\in\mathcal{T}_n} x\right)\! = 1 $. Pertanto, ancora in virtù del lemma di Euclide: $ a^{\varphi(n)} \equiv 1 \bmod n $, q.e.d.
Oh, l'amore per la complicazione non si è ancora spento nel cuore del nostro prode Hit ...beh, se qualcuno non capisce la sua misterica simbologia, chieda.
Intanto, propongo un'altra dimostrazione del piccolo teorema di Fermat.
Sia p un primo, a un intero, allora $ a^p\equiv a \mod\ p $
Se a=kp per qualche k intero, la tesi è ovvia, in quanto sia a che a^p sono congrui a 0 mod p.
Supponiamo dunque che a non sia multiplo di p; allora, consideriamo i p-1 numeri
$ a, 2\cdot a, 3\cdot a, \ldots, (p-1)\cdot a $
I loro resti nella divisione per p (ovvero le loro classi di resto modulo p) sono tutti distinti e quindi saranno $ 1,2,\ldots, p-1 $ non necessariamente in questo ordine cioè, non è detto che $ a\equiv 1,\ 2a\equiv 2\ldots $, ma sicuramente per ogni numero tra 1 e p-1 esiste uno dei multipli di a sopra scritti che gli è congruo modulo p.
Bene, allora facciamo il prodotto dei multipli di a ed eguagliamolo al prodotto di tutti i naturali tra 1 e p-1:
$ a\cdot(2a)\cdot(3a)\cdot\ldots\cdot((p-1)a)\equiv (p-1)! \mod\ p $
ora, è ovvio che p non divide (p-1)!, quindi possiamo raccogliere e semplificare
$ (p-1)!(a^{p-1}-1)\equiv 0 \mod\ p $
e per la legge di annullamento del prodotto (che possiamo usare poichè il modulo è un primo), abbiamo che
$ a^{p-1}\equiv 1 \mod\ p $
ovvero
$ a^p\equiv a \mod \ p $
QED
Uhm ... sono sempre troppo prolisso quando tento di spiegare qualcosa ...
prendiamo una collana con p perline (p primo), e supponiamo di poterle colorare con n colori (cioè di poter colorare ciascuna perlina con un colore scelto tra gli n).
ora, il numero di colorazioni non monocromatiche della collana è multiplo di p, perchè se ne abbiamo una possiamo ruotare la collana di una perlina alla volta, e ottenere così altre p-1 colorazioni non monocromatiche distinte.
d'altra parte il numero di colorazioni non monocromatiche è proprio $ n^p-n $ (totali - monocromatiche).
olè
domanda: dove è stato usato il fatto che p è primo??
talpuz ha scritto:altra dimostrazione, un po' alternativa:
prendiamo una collana con p perline (p primo), e supponiamo di poterle colorare con n colori (cioè di poter colorare ciascuna perlina con un colore scelto tra gli n).
ora, il numero di colorazioni non monocromatiche della collana è multiplo di p, perchè se ne abbiamo una possiamo ruotare la collana di una perlina alla volta, e ottenere così altre p-1 colorazioni non monocromatiche distinte.
d'altra parte il numero di colorazioni non monocromatiche è proprio $ n^p-n $ (totali - monocromatiche).
olè
domanda: dove è stato usato il fatto che p è primo??
Forse nel fatto che non possono esistere rotazioni che lasciano invaianti rotazioni non monocromatiche? Cioè che non possono esistere colorazioni del tipo RGRG che sarebbero contate due volte...
sì, il punto è quello...
se p non è primo, se ruotiamo di un numero di perline pari ad un suo divisore (diverso da 1 e sè stesso) contiamo alcune colorazioni non monocromatiche più volte
Quand'anche ti fosse sfuggito, e non lo credo possibile, mi limito a farti notare, adorato Evaristo, che la tua dimostrazione del teorema (piccolo) di Fermat altro non è che un adattamento del proof riproposto da questo miserabile (sarei io, esatto!!!) per il teorema di Euler-Fermat. Che infatti, se $ p $ è primo in $ \mathbb{N} $, allora $ \mathcal{T}_p = \{1, 2, \ldots, p-1\} $ e $ \varphi(p) = p-1 $, coff coff... Davvero c'era bisogno di riscriverlo?!?
HiTLeuLeR ha scritto:Teorema (piccolo) di Fermat: per ogni $ p\in\mathfrak{P} $ ed ogni $ a\in\mathbb{Z} $: $ a^p \equiv a \bmod p $.
Dim.: [...] $ \displaystyle\binom{p}{k}\equiv 0 \bmod p $, se $ p\in\mathfrak{P} $ e $ k = 1, 2, \ldots, p-1 $. Ergo, in base al teorema binomiale di Newton, e nelle ipotesi del teorema: $ \displaystyle a^p \equiv \sum_{k=0}^{p} \binom{p}{k} (a-1)^k \equiv 1 + (a-1) \equiv a \bmod p $, q.e.d.
Davvero faccio notare che, a rigore, si dovrebbe trattare separatamente il caso $ a = 1 $ (banale!!!), onde evitare d'incorrere in certe spiacevoli scritture (forse che si parla di $ 0^0 $ ?!?)... Me pedante, quanto sono noioso!!!
Sia t la più piccola potenza di a tale che a^t=1 mod p.
Essendo 1=1 (mod p), e considerando 1=a^0, con p primo, a=r (mod p) e r>0, nelle potenze da 0 a p-2 si dovranno avere tutti i possibili resti modulo p diversi da ovvero 1,2,3,4..p-1 se p-1=t; quindi se a^0\equiv 1, anche a^{p-1}=1 per la "ciclicità dei residui" attorno a t, da cui moltiplicando per a la tesi.
Se r=1 la tesi è comunque valida.
Inoltre dalla dimostrazione di Gauss (che suppongo sia ben conosciuta) si ha che t|(p-1), da cui la tesi
Ultima modifica di HumanTorch il 15 giu 2005, 23:32, modificato 1 volta in totale.
Aggiungerei inoltre che non solo i primi sono tali che a^r=a (mod r): se tale relazione vale per ogni a<r e r non è primo, r è un cosidetto numero di Carmichael
Per questo il teorema di Eulero-Fermat è debole come test di primalità, mentre uno notevole è il (famigerato in questi giorni) teorema di Wilson
HumanTorch ha scritto:Essendo 1=1 (mod p), e considerando 1=a^0, con p primo, a=r (mod p) e r>0, nelle potenze da 0 a p-2 si dovranno avere tutti i possibili resti modulo p diversi da ovvero 1,2,3,4..p-1; quindi [...]
Ma stiamo scherzando o cosa?!? HumanTorch, prima di lasciarti andare a certe affermazioni, dovresti quantomeno avere la decenza di convincere *te stesso* della bontà di quel che vai cianciando... E nel suscitare dalle corde mie più profonde questa voce tremante d'incompiuto orrore, prego voi, popolo d'Orfalese, miei diletti, d'essere sordi - nel di voi interesse - al delirare dissennato di costui!!! Detto in parole povere... Non compratevi il "proof" di HumanTorch: non vale granché!
Detto in parole povere... Non compratevi il "proof" di HumanTorch: non vale granché!
