da TomSawyer » 15/03/2007, 17:12
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)$.
I watched a snail crawl along the edge of a straight razor. That's my dream. That's my nightmare. Crawling, slithering, along the edge of a straight... razor... and surviving., Walter E. Kurtz