I teoremi di Fermat ed Euler-Fermat

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

I teoremi di Fermat ed Euler-Fermat

Messaggio da HiTLeuLeR » 24 mag 2005, 20:09

Rispondo qui alla richiesta di alcuni utenti bisognosi... :wink:

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.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 24 mag 2005, 20:26

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.

EvaristeG
Site Admin
Messaggi: 4777
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 25 mag 2005, 12:23

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 ...

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz » 25 mag 2005, 13:41

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è :D

domanda: dove è stato usato il fatto che p è primo??

Avatar utente
mattilgale
Messaggi: 372
Iscritto il: 01 gen 1970, 01:00
Località: Lucca
Contatta:

Messaggio da mattilgale » 25 mag 2005, 18:42

ma se a è maggiore di p vale quindi

$ a^p\equiv a-p \mod p $
giusto?
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"

Galileo Galilei

Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo » 25 mag 2005, 20:43

Be' $ a-p\equiv a \mod p $...

Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo » 25 mag 2005, 20:46

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è :D

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...

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz » 25 mag 2005, 21:30

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

bravo sisifo :wink:

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 25 mag 2005, 22:19

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?!? :shock: :mrgreen:

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 25 mag 2005, 22:25

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!!! 8)

EvaristeG
Site Admin
Messaggi: 4777
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 25 mag 2005, 23:16

Hit, ti posso gentilmente far notare che non si capiva un'acca delle tue corbellerie?

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 25 mag 2005, 23:23

EvaristeG ha scritto:[...] beh, se qualcuno non capisce la sua misterica simbologia, chieda.
Mi è permesso farti notare gentilmente che avresti pur potuto accettare il consiglio di quel tale?!? 8)

Avatar utente
HumanTorch
Messaggi: 281
Iscritto il: 01 gen 1970, 01:00
Località: Tricase

Messaggio da HumanTorch » 14 giu 2005, 12:17

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.

Avatar utente
HumanTorch
Messaggi: 281
Iscritto il: 01 gen 1970, 01:00
Località: Tricase

Messaggio da HumanTorch » 14 giu 2005, 18:09

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

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

pietrificato o giù di lì... °_°

Messaggio da HiTLeuLeR » 14 giu 2005, 19:56

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?!? :shock: 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!!! :evil: Detto in parole povere... Non compratevi il "proof" di HumanTorch: non vale granché!

$ 2^0 \equiv 2^3 \equiv 2^6 \equiv 1 \bmod 7; 2^1 \equiv 2^4 \equiv 2 \bmod 7; 2^2 \equiv 2^5 \equiv 4 \bmod 7 $
Ultima modifica di HiTLeuLeR il 16 giu 2005, 20:02, modificato 1 volta in totale.

Rispondi