I teoremi di Fermat ed Euler-Fermat
- HumanTorch
- Messaggi: 281
- Iscritto il: 01 gen 1970, 01:00
- Località: Tricase
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ì
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
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.
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...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 [...]
- HumanTorch
- Messaggi: 281
- Iscritto il: 01 gen 1970, 01:00
- Località: Tricase
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 $
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 $
... ...
HumanTorch, perdonami se ultimamente ti sto col fiato sul collo, maaa... Mi diresti cosa pensi di aver dimostrato [...]?!?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
- Messaggi: 281
- Iscritto il: 01 gen 1970, 01:00
- Località: Tricase
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:Oh, questa mi era sfuggita! Senti, tutti i resti possibili (per dirla a modo tuo) si ottengono sse $ t = p-1 $, semmai...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 [...]
Ultima modifica di HumanTorch il 19 giu 2005, 09:45, modificato 1 volta in totale.
Bene, è proprio quel che volevo sapere!!! Dunque ti rinnovo la domanda, ma questa volta cerca di non divagare...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) $
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...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...
HumanTorch ha scritto:[...] tutti i resti possibili si hanno solo se t=1, mentre nei restanti casi [...]
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*...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 [...]
- HumanTorch
- Messaggi: 281
- Iscritto il: 01 gen 1970, 01:00
- Località: Tricase
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
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
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. E' un'opinione personale, non darle troppo peso! Dunque, maniche in su...
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: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..)
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!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) $.
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.HumanTorch ha scritto:$ {a^t}^n=1^n \bmod p $
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?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 $