Moduli

[NoRe1]

Dopo aver studiato un po' sul mio libro alcune cose sui moduli mi ritrovo questo esercizio

Dimostrare che il più piccolo numero $n$ per cui vale $a^n≡1$ modulo p è divisore del numero p-1 ricordando che per il teorema di Fermat a^(p-1)≡1 modulo p con p primo e non divisore di a...


Ho un po' di idee ma partono tutte al contrario... Proverei con una dimostrazione per assurdo ma non so da dove partire... Consigli? dai su


p.s. riuscite a vedere le formule? io sul mio ipad vedo anche i'dollari'... prima però riuscivo correttamente a visualizzare il forum...

[Zero87]

Se non erro ho una dimostrazione "chiacchierosa" sul fatto che ogni $n$ per cui vale l'espressione è divisibile per $n-1$. In generale è meglio dire "per ogni $m$ per cui vale l'espressione è divisibile per $n-1$" (sennò ci si confonde).

Ora sono abbastanza impegnato per postarla (sembro Fermat), però si basa sulle semplici proprietà delle potenze (ad esempio $(a^b)^c = a^{bc}$) oltre che al piccolo teorema di Fermat.

[NoRe1]

"Zero87":Se non erro ho una dimostrazione "chiacchierosa" sul fatto che ogni $n$ per cui vale l'espressione è divisibile per $n-1$. In generale è meglio dire "per ogni $m$ per cui vale l'espressione è divisibile per $n-1$" (sennò ci si confonde).

Ora sono abbastanza impegnato per postarla (sembro Fermat), però si basa sulle semplici proprietà delle potenze (ad esempio $(a^b)^c = a^{bc}$) oltre che al piccolo teorema di Fermat.

Forse forse ho capito! Mettete la tra spoiler comunque!

aspetteremo altri secoli per la pigrizia di un nuovo Fermat? Lol

[Zero87]

"Zero87":In generale è meglio dire "per ogni $m$ per cui vale l'espressione è divisibile per $n-1$" (sennò ci si confonde).

La frase quotata da me è inutile. Ho scritto una gran cavolata dovuta al fatto che ero/sono piuttosto rimbecillito dal tour de force che sto facendo con l'uni .

"NoRe":[quote="Zero87"]Ora sono abbastanza impegnato per postarla (sembro Fermat), però si basa sulle semplici proprietà delle potenze (ad esempio $(a^b)^c = a^{bc}$) oltre che al piccolo teorema di Fermat.

Forse forse ho capito! Mettete la tra spoiler comunque!

aspetteremo altri secoli per la pigrizia di un nuovo Fermat? Lol[/quote]
Ho riordinato le chiacchiere e mi è venuta fuori una dimostrazione niente male.
Provo a spoilerizzarla: se lo spoiler non funziona - causa aggiornamento - metterò "colore carattere=bianco" in modo che chi vuol vederla deve sottolinearla con il mouse (quindi è una sorta di spoiler ).

Allora...
Chiamo $m$ il più piccolo numero per cui $a^m ≡ 1 (mod p)$
dove $p$ è primo.

Supponiamo per assurdo che non valga $m|(p-1)$
(non so come si fa la sbarra sul simbolo di divisibilità), cioè che $m$ non divida $p-1$.

Da questo si deduce che $p-1 = m\cdot k +r$
con $r\ne 0$ proprio perché $p-1$ non è multiplo di $m$ ($k$ è intero). Inoltre, per definizione di resto, $r
Ora, dalle proprietà delle potenze da me richiamate nel post precedente, ho
$a^(mk) ≡ (a^m)^k ≡ 1^k ≡ 1 (mod p)$.
Inoltre, sapendo che, anche nei moduli, continua a valere
$a^(b+c) = a^b \cdot a^c$
allora
$a^(p-1) ≡ a^(mk+r) ≡ a^{mk}\cdot a^r ≡ 1 \cdot a^r ≡ a^r ≡ 1 (mod p)$
in cui la prima è uguale all'ultima (con i moduli) per il teorema di Fermat da te citato all'inizio.

Giungiamo, però, alla contraddizione perché otteniamo
$a^r ≡ 1 (\text{mod} p)$
che contrasta con l'ipotesi che $m$ è il più piccolo intero per cui vale quella relazione dato che $r$ - da resto - è tale che $r L'unica possibilità è $r=0$ da cui segue che $m$ è un divisore di $p-1$.

c.v.d.

PS. non è pigrizia, è solo che avevo da fare con l'uni e poche pause .

EDIT.
Ho modificato -mila volte perché le formule vanno a finire sempre sopra al testo

[NoRe1]

dovevo solo capire perchè a^r≡1 contrastava con l'ipotesi iniziale... o meglio non mi ero accorto del fatto che era incompatibile con l'ipotesi iniziale!

Mi mancava l'anello fondamentale


Giungiamo, però, alla contraddizione perché otteniamo

$a^r ≡1(modp)$
che contrasta con l'ipotesi che m è il più piccolo intero per cui vale quella relazione dato che
r - da resto - è tale
che $r L'unica possibilità è r=0 da cui segue che
m è un divisore di
$p−1$.

C'ero quasi!
contrasta con l'ipotesi che m è il più piccolo intero !

questo era l'anello mancantE Sto migliorando
Da quando sono qui e ho aperto quel libro, vedo tutto più semplice
Anche per esercizi che faccio a scuola! ho la mente più snella

[Zero87]

"NoRe":Giungiamo, però, alla contraddizione perché otteniamo...[...]

Intendevi lo spoiler al posto del corsivo?

[NoRe1]

No, era per far veder la parte che mi ha illuminato