Fermat
come si dimostra il teorema di fermat per cui un numero primo p divide $a^(p-1)$ senza lasciare resto se a, p non hanno divisori in comune.
e la successiva generalizzazione da parte di eulero, con il suo toziente?
grazie a tutti...
e la successiva generalizzazione da parte di eulero, con il suo toziente?
grazie a tutti...
Risposte
Non è proprio così. $a^(p-1)-1$ è divisibile per $p$, se $\gcd(a,p)=1$. Oppure, senza restrizioni, $a^p\equiv a (modp)$.
Ti dimostro il teorema di Euler, quello di Fermat è una semplice conseguenza.
Dimostro che $a^(phi(m))\equiv 1 (modm)$, con $m$ intero positivo e $\gcd(a,m)=1$.
Sia ${r_1,\ldots,r_(phi(m))}$ un insieme ridotto di residui modulo $m$. Abbiamo che $\gcd(ar_i,m)=1$, per $i \in [1,phi(m)]$. Di conseguenza, per ogni $i \in [1,phi(m)]$ esiste $\sigma(i) \in [1,phi(m)]$, tale che
$ar_i\equiv r_(sigma(i)) (modm)$.
Si ha inoltre che $ar_i\equiv ar_j(modm)$, solo se $i=j$, quindi $\sigma$ è una permutazione dell'insieme ${1,\ldots,phi(m)}$ ed anche ${ar_1,\ldots,a_r_(phi(m))}$ è un insieme ridotto di residui modulo $m$. Quindi
$a^(phi(m))r_1r_2\cdots r_(phi(m))\equiv (ar_1)(ar_2)\cdots(ar_(phi(m)))\equiv r_(\sigma(1))\cdots r_(\sigma(phi(m))) \equiv r_1\cdots r_(phi(m))(modm)$.
Dividendo per $r_1\cdots r_(phi(m))$ si ottiene
$a^(phi(m))\equiv 1 (modm)$.
Ti dimostro il teorema di Euler, quello di Fermat è una semplice conseguenza.
Dimostro che $a^(phi(m))\equiv 1 (modm)$, con $m$ intero positivo e $\gcd(a,m)=1$.
Sia ${r_1,\ldots,r_(phi(m))}$ un insieme ridotto di residui modulo $m$. Abbiamo che $\gcd(ar_i,m)=1$, per $i \in [1,phi(m)]$. Di conseguenza, per ogni $i \in [1,phi(m)]$ esiste $\sigma(i) \in [1,phi(m)]$, tale che
$ar_i\equiv r_(sigma(i)) (modm)$.
Si ha inoltre che $ar_i\equiv ar_j(modm)$, solo se $i=j$, quindi $\sigma$ è una permutazione dell'insieme ${1,\ldots,phi(m)}$ ed anche ${ar_1,\ldots,a_r_(phi(m))}$ è un insieme ridotto di residui modulo $m$. Quindi
$a^(phi(m))r_1r_2\cdots r_(phi(m))\equiv (ar_1)(ar_2)\cdots(ar_(phi(m)))\equiv r_(\sigma(1))\cdots r_(\sigma(phi(m))) \equiv r_1\cdots r_(phi(m))(modm)$.
Dividendo per $r_1\cdots r_(phi(m))$ si ottiene
$a^(phi(m))\equiv 1 (modm)$.
gentilissimo, grazie mille|
"Crook":
Di conseguenza, per ogni $i \in [1,phi(m)]$ esiste $\sigma(i) \in [1,phi(m)]$, tale che
$ar_i\equiv r_(sigma(i)) (modm)$.
questa "conseguenza"(
) non mi è chiara, perchè consegue questo, non ho afferato troppo bene...neanche perchè esiste $\sigma(i) \in [1,phi(m)]$...
non afferro il perchè della cosa...
Significa che il resto modulo $m$ di $ar_i$ appartiene ancora all'insieme $R={r_1,\ldots,r_(\phi(m))}$, dato che $\gcd(ar_i,m)=1$. Prova sperimentalmente, se hai problemi ad afferrare questo concetto, è sempre utile.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo