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
HumanTorch
Messaggi: 281
Iscritto il: 01 gen 1970, 01:00
Località: Tricase

Messaggio da HumanTorch » 15 giu 2005, 23:34

Si, si, avevo dimenticato le ipotesi: tutti i resti possibili si hanno solo se t=p-1 (vedi sopra, ora corretto) mentre nei restanti casi la dimostrazione che il maestro Gauss ci presenta è più che esaustiva. Sorry per le obbrobbiosità che ho scritto, ma la fretta fa fare al gatto cieco il lardo al largo o qualcosa così :lol:

Ps Scusate l'insistenza ma che succede? è un giorno che provo a connettermi e visualizza sempre errore.. non sarà il millennium bug col jet lag di Giove?

EDIT: Corretto
Ultima modifica di HumanTorch il 17 giu 2005, 12:36, modificato 1 volta in totale.

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

Messaggio da HiTLeuLeR » 16 giu 2005, 20:06

HumanTorch ha scritto:Si, si, avevo dimenticato le ipotesi: tutti i resti possibili si hanno solo se t=1 (vedi sopra, ora corretto) mentre nei restanti casi la dimostrazione che il maestro Gauss ci presenta è più che esaustiva. Sorry per le obbrobbiosità che ho scritto [...]
Innanzitutto non serve, in simili casi, che ti scusi con nessuno, e men che meno che tu lo faccia con me! In secondo luogo, poi... Se lasci discendere il teorema di Euler-Fermat, o anche soltanto il (piccolo) teorema di Fermat, dalle proprietà dell'ordine moltiplicativo (sarebbe a dire la $ t $ del quote!), com'è che di quest'ultimo dimostri l'esistenza, uh? Senza tirare in ballo ferraglia algebrica di pregiata fattura, chiaramente... 8)

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

Messaggio da HumanTorch » 16 giu 2005, 21:03

In effetti è parecchio lunga (non un esorbito, però...) quindi lancio solo qualche idea principale ochei?

Allora: siano $ \alpha_1 $, $ \alpha_2 $...$ \alpha_t $, i resti delle potenze di $ a $ da $ 1 $ a $ t $; se $ t=p-1 $ siamo a posto; se $ t<p-1 $ allora ci sarà un numero fra $ 1,2,3..p-1 $ che non è compreso nei residui. Sia tale numero $ \theta $; prendiamo un numero $ T $ e moltiplichiamolo per ogni $ \alpha_i $: producendo i residui $ \theta_i $: ovviamente $ \theta_i\neq \theta_j $ $ \forall i,j<t $ ma anche $ \theta_i\neq \alpha_j $, ovvero $ Ta^l $ non è congruente a $ a^f $ poichè, se $ l<f $ dividendo per $ a^l $ si ha un assurdo, non essendo $ T=a^c $, con $ c<t $, mentre nel caso $ l>f $ $ Ta^f(a^{l-f}-1)\equiv 0 $, ma nessuno dei termini è congruo a $ 0 $ o a $ 1 $ per ipotesi.
Quindi gli insiemi contenenti $ \alpha_i $ e $ \theta_i $ hanno la stessa cardinalità: da ciò se è $ t=\frac{p-1}{2} $ la tesi è dimostrata; altrimenti si reitera il processo con altri $ T_i $; essendo $ p $ primo, $ p-1 $ non lo è (ad eccezione della coppia $ (2;3) $), quindi prima o poi (di sicuro prima di $ t_{\frac{p-1}{2}} $) a un multiplo di $ nt=p-1 $

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

... ...

Messaggio da HiTLeuLeR » 17 giu 2005, 09:04

HumanTorch ha scritto:[...] siano $ \alpha_1 $, $ \alpha_2 $...$ \alpha_t $, i resti delle potenze di $ a $ da $ 1 $ a $ t $; se $ t=p-1 $ siamo a posto; se $ t<p-1 $ allora ci sarà un numero fra $ 1,2,3..p-1 $ che non è compreso nei residui. Sia tale numero $ \theta $; prendiamo un numero $ T $ e moltiplichiamolo per ogni $ \alpha_i $: producendo i residui $ \theta_i $: ovviamente $ \theta_i\neq \theta_j $ $ \forall i,j<t $ ma anche $ \theta_i\neq \alpha_j $, ovvero $ Ta^l $ non è congruente a $ a^f $ poichè, se $ l<f $ dividendo per $ a^l $ si ha un assurdo, non essendo $ T=a^c $, con $ c<t $, mentre nel caso $ l>f $ $ Ta^f(a^{l-f}-1)\equiv 0 $, ma nessuno dei termini è congruo a $ 0 $ o a $ 1 $ per ipotesi.
Quindi gli insiemi contenenti $ \alpha_i $ e $ \theta_i $ hanno la stessa cardinalità: da ciò se è $ t=\frac{p-1}{2} $ la tesi è dimostrata; altrimenti si reitera il processo con altri $ T_i $; essendo $ p $ primo, $ p-1 $ non lo è (ad eccezione della coppia $ (2;3) $), quindi prima o poi (di sicuro prima di $ t_{\frac{p-1}{2}} $) a un multiplo di $ nt=p-1 $
HumanTorch, perdonami se ultimamente ti sto col fiato sul collo, maaa... Mi diresti cosa pensi di aver dimostrato [...]?!? :?

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

Messaggio da HiTLeuLeR » 17 giu 2005, 09:14

HumanTorch ha scritto:[...] tutti i resti possibili si hanno solo se t=1, mentre nei restanti casi [...]
Oh, questa mi era sfuggita! Senti, tutti i resti possibili (per dirla a modo tuo) si ottengono sse $ t = p-1 $, semmai... :evil:

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

Messaggio da HumanTorch » 17 giu 2005, 10:23

Allora: la dimostrazione implica $ t $ è senz'altro un divisore di $ p-1 $:: possiamo raggruppare gli interi da $ 1 $ a $ p-1 $ in "classi" che conterranno sempre t elementi tutti diversi fra loro; quindi essendo le classi in numero intero, $ t|p-1 $, ovvero $ p-1\equiv 0 $ $ (mod t) $; per la ciclicità dei resti e dato che $ a^t\equiv 1 $, $ a^{tn}=1^n $ sempre modulo $ p $, $ a^{nt}=a^{p-1}\equiv 1 $ $ (mod p) $
HiTLeuLeR ha scritto:
HumanTorch ha scritto:[...] tutti i resti possibili si hanno solo se t=1, mentre nei restanti casi [...]
Oh, questa mi era sfuggita! Senti, tutti i resti possibili (per dirla a modo tuo) si ottengono sse $ t = p-1 $, semmai... :evil:
...
HumanTorch ha scritto:Sia t la più piccola potenza di a tale che a^t=1 mod p.
[...]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 [...]
Ultima modifica di HumanTorch il 19 giu 2005, 09:45, modificato 1 volta in totale.

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

Messaggio da HiTLeuLeR » 17 giu 2005, 11:33

HumanTorch ha scritto:[...] la dimostrazione implica $ t $ è senz'altro un divisore di $ p-1 $: possiamo raggruppare gli interi da $ 1 $ a $ p-1 $ in "classi" che conterranno sempre t elementi tutti diversi fra loro; quindi essendo le classi in numero intero, $ t|p-1 $, ovvero $ p-1\equiv 0 $ $ (mod t) $; per la ciclicità dei resti e dato che (btw, qui c'è un errore nel tuo LaTeX) $ a^t\equiv 1 $, $ {a^t}^n=1^n $ sempre modulo $ p $, $ a^{nt}=a^{p-1}\equiv 1 $ $ (mod p) $
Bene, è proprio quel che volevo sapere!!! Dunque ti rinnovo la domanda, ma questa volta cerca di non divagare...
HiTLeuLeR ha scritto:Se lasci discendere [...] il (piccolo) teorema di Fermat dalle proprietà dell'ordine moltiplicativo (sarebbe a dire la [tua] $ t $), com'è che di quest'ultimo dimostri l'esistenza, uh? Senza tirare in ballo ferraglia algebrica di pregiata fattura, chiaramente...
Parafrasi del testo: come dimostri ch'esiste un intero minimale $ t > 0 $ tale che, se $ a\in\mathbb{Z} $, $ p\in\mathfrak{P} $ e $ p \nmid a $, allora $ a^t \equiv 1 \bmod p $ ?!? Sono ansioso di sapere, HumanT... 8)

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

Messaggio da HiTLeuLeR » 17 giu 2005, 11:40

HumanTorch ha scritto:[...] tutti i resti possibili si hanno solo se t=1, mentre nei restanti casi [...]
HumanTorch ha scritto:Sia t la più piccola potenza di a tale che a^t=1 mod p.
[...]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 [...]
Bene, questo ci conferma che sei fra quegli invidiabile che possono contraddire se stessi nel volgere di qualche rigo senza rendersene neppur lontamente conto! Del resto, *io* mi ero limitato a segnalarti un "refuso di stampa", ma *tu*...

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

Messaggio da HumanTorch » 17 giu 2005, 12:40

Per assurdo supponiamo che non ci siano $ a,p $ con tali proprietà (ma $ a^0=1 $ ci servirà dopo); siano tali residui $ r_i $, ovviamente tutti diversi da $ 1 $; ad un certo punto, dovendo essere si $ >1 $ ma anche $ <p $, per il principio dei piccioni nei cassetti o pigeonhole che dir si voglia, si avrà un resto $ r_g=r_f $ dove $ r_f $ si è già incontrato nella precedente successione; ma allora il residuo precedente deve essere uguale a quello che precede $ r_f $ e così via (questo perche ottenuti moltiplicando per lo stesso fattore $ a $); quindi si giungerà a un resto $ r_t $ uguale a $ 1 $ ma dato da un esponente diverso da $ 0 $ (che noi chiameremo appunto $ t $) poichè fra $ r_g $ e $ r_f $ ci saranno sicuramente altri residui (non so se mi sono spiegato..)

Per la questione del $ t=1 $, nel primo post ho scritto che si avranno residui pari sempre a $ 1 $, quindi è chiaro che non intendevo ciò che ho scritto (maledetto computer..); comunque chino il capo per i problemi causati :lol:

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

Messaggio da HiTLeuLeR » 19 giu 2005, 08:37

Cerco di commentare la tua dimostrazione, HumanTorch, al solo scopo di renderla più leggibile: non volermene se te lo dico, maaa... scrivi davvero coi piedi. :evil: E' un'opinione personale, non darle troppo peso! Dunque, maniche in su...
HumanTorch ha scritto:Per assurdo supponiamo che non ci siano $ a,p $ con tali proprietà; siano tali residui $ r_i $, ovviamente tutti diversi da $ 1 $; ad un certo punto, dovendo essere si $ >1 $ ma anche $ <p $, per il principio dei piccioni nei cassetti o pigeonhole che dir si voglia, si avrà un resto $ r_g=r_f $ dove $ r_f $ si è già incontrato nella precedente successione; ma allora il residuo precedente deve essere uguale a quello che precede $ r_f $ e così via (questo perche ottenuti moltiplicando per lo stesso fattore $ a $); quindi si giungerà a un resto $ r_t $ uguale a $ 1 $ ma dato da un esponente diverso da $ 0 $ (che noi chiameremo appunto $ t $) poichè fra $ r_g $ e $ r_f $ ci saranno sicuramente altri residui (non so se mi sono spiegato..)
Supponiamo ch'esistano $ p\in\mathfrak{P} $ ed $ a\in\mathbb{Z} $, con $ \gcd(a,p) = 1 $, tali che: $ a^k \not\equiv 1 \bmod p $, per ogni $ k = 1, 2, \ldots, p-1 $. Del resto, siccome $ a $ è coprimo con $ p $, nondimeno $ a^k \not\equiv 0 \bmod p $, qual che sia $ k = 1, 2, \ldots, p-1 $. Detto dunque $ r_k $ il resto della divisione intera di $ a^k $ per $ p $, quando $ k = 1, 2, \ldots, p-1 $, può dedursi dal principio dei cassetti ch'esistono $ f, g = 1, 2, \ldots, p-1 $, con $ f < g $, tali che $ r_f = r_g $. E allora $ a^f \equiv a^g \bmod p $, ovvero $ a^{g-f} \equiv 1 \bmod p $, come consegue dal lemma di Euclide stante che $ \gcd(a^f,p) = 1 $. Ne risulta provata l'esistenza di un intero $ t > 0 $, essendo $ x := g - f $, per cui $ a^x \equiv 1 \bmod p $, di contro l'assunto iniziale. Ne segue che, comunque scelti $ p\in\mathfrak{P} $ ed $ a\in\mathbb{Z} $, con $ \gcd(a,p) = 1 $, l'insieme $ \Omega := \{x\in\mathbb{N}_0: a^x \equiv 1 \bmod p\} $ è non vuoto, e come tale possiede elemento minimo. Si ponga $ t := \min \Omega $ per dedurne con lineare semplicità il seguente risultato notevole:
Se $ p\in\mathfrak{P} $, $ a\in\mathbb{Z} $ e $ p\nmid a $, esiste allora un intero minimale $ t > 0 $ tale che: $ a^t \equiv 1 \bmod p $. Si dice che $ t $ rappresenta l'ordine moltiplicativo di $ p $ alla base $ a $, e si denota fra l'altro con $ \mbox{ord}_p(a) $.
In proposito, consiglio pure di dare un'occhiatina qui. In effetti, la discussione che abbiamo portato avanti in questo thread andrebbe spostata di là, giusto per ragioni d'ordine pubblico!

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

Messaggio da HiTLeuLeR » 19 giu 2005, 08:56

HumanTorch ha scritto:$ {a^t}^n=1^n \bmod p $
Ti avevo già invitato a correggere il tuo LaTeX, ma tu hai fatto orecchie da mercante... Viste le conclusioni cui sei pervenuto, suppongo volessi intendere $ a^{nt} \equiv 1 \bmod p $, e non $ {a^t}^n \equiv 1^n \bmod p $, sebbene le due congruenze siano entrambe vere.

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

Messaggio da HiTLeuLeR » 19 giu 2005, 09:44

HumanTorch ha scritto:[...] siano $ \alpha_1 $, $ \alpha_2 $...$ \alpha_t $, i resti delle potenze di $ a $ da $ 1 $ a $ t $; se $ t=p-1 $ siamo a posto; se $ t<p-1 $ allora ci sarà un numero fra $ 1,2,3..p-1 $ che non è compreso nei residui. Sia tale numero $ \theta $; prendiamo un numero $ T $ e moltiplichiamolo per ogni $ \alpha_i $: producendo i residui $ \theta_i $: ovviamente $ \theta_i\neq \theta_j $ $ \forall i,j<t $ ma anche $ \theta_i\neq \alpha_j $, ovvero $ Ta^l $ non è congruente a $ a^f $ poichè, se $ l<f $ dividendo per $ a^l $ si ha un assurdo, non essendo $ T=a^c $, con $ c<t $, mentre nel caso $ l>f $ $ Ta^f(a^{l-f}-1)\equiv 0 $, ma nessuno dei termini è congruo a $ 0 $ o a $ 1 $ per ipotesi. Quindi gli insiemi contenenti $ \alpha_i $ e $ \theta_i $ hanno la stessa cardinalità: da ciò se è $ t=\frac{p-1}{2} $ la tesi è dimostrata; altrimenti si reitera il processo con altri $ T_i $; essendo $ p $ primo, $ p-1 $ non lo è (ad eccezione della coppia $ (2;3) $), quindi prima o poi (di sicuro prima di $ t_{\frac{p-1}{2}} $) a un multiplo di $ nt=p-1 $
Siccome l'aramaico non lo so ancora parlare, e se è vero - come tu mi garantisci... - che l'intenzione tua era di provare che $ t \mid (p-1) $, beh... perché non dai una cliccatina qui, eh?

Rispondi