Piccolo teorema di Fermat
questo teorema di solito l ho trovato nella forma:
Sia p un numero primo ed $a$ $in$ $ZZ$ . Se p coprimo a, allora $a^(p-1)$ $-=$ $1$ $(mod$ $p)$.
in un testo pero ho trovato:
se $p$ è un numero primo allora esisterà un certo numero $n$ che divide $p-1$ e per cui vale $a^(n)$ $-=$ $1$ $(mod$ $p)$.
Che la seconda porti alla prima mi pare abbastanza evidente.. ma non capisco se questa seconda versione sia vera, potete aiutarmi??
Sia p un numero primo ed $a$ $in$ $ZZ$ . Se p coprimo a, allora $a^(p-1)$ $-=$ $1$ $(mod$ $p)$.
in un testo pero ho trovato:
se $p$ è un numero primo allora esisterà un certo numero $n$ che divide $p-1$ e per cui vale $a^(n)$ $-=$ $1$ $(mod$ $p)$.
Che la seconda porti alla prima mi pare abbastanza evidente.. ma non capisco se questa seconda versione sia vera, potete aiutarmi??
Risposte
pensandoci un po credo che il problema si riduca a dimostrare che n è sempre uguale a p-1, uguagliando cosi le due versioni... solo che non riesco a dimostrarlo..
cerco di riscrivere la seconda versione per vedere se ho capito il testo:
se $p$ è un primo allora $a^n\equiv 1 (mod p)$ per ogni n che divide p-1
se è così è falso basta prendere p=5 e n=2, si vede che n divide p-1 ma $2^2!=1 (mod5)$
potrebbe essere invece per ogni n divisibile per p-1 allora avremmo che $a^n=(a^(p-1))^(n/(p-1))\equiv1^(n/(p-1))\equiv1 (mod p)$ quindi in questo modo mi pare funzion.
spero di non aver travisato il testo
se $p$ è un primo allora $a^n\equiv 1 (mod p)$ per ogni n che divide p-1
se è così è falso basta prendere p=5 e n=2, si vede che n divide p-1 ma $2^2!=1 (mod5)$
potrebbe essere invece per ogni n divisibile per p-1 allora avremmo che $a^n=(a^(p-1))^(n/(p-1))\equiv1^(n/(p-1))\equiv1 (mod p)$ quindi in questo modo mi pare funzion.
spero di non aver travisato il testo
scusa, in effetti ho scritto sbagliato sopra... è così
se $p$ è un numero primo allora esisterà un certo numero $n$ che divide $p-1$ e per cui vale $a^(n)$ $-=$ $1$ $(mod$ $p)$.
così dovrebbe funzionare, il punto è che a tentativi la $n$ cercata di solito è uguale a $p-1$... ma non riesco a dimostrare che sia sempre così
per essere un po piu preciso su quello che sto chiedendo: questa versione l ho ricavata da una traduzione di una lettera di fermat a un suo amico in cui scrive per la prima volta questo teorema, pero nei libri di matematica adesso viene scritta come nella prima versione che ho scritto nel primo messaggio primo post.
se $p$ è un numero primo allora esisterà un certo numero $n$ che divide $p-1$ e per cui vale $a^(n)$ $-=$ $1$ $(mod$ $p)$.
così dovrebbe funzionare, il punto è che a tentativi la $n$ cercata di solito è uguale a $p-1$... ma non riesco a dimostrare che sia sempre così
per essere un po piu preciso su quello che sto chiedendo: questa versione l ho ricavata da una traduzione di una lettera di fermat a un suo amico in cui scrive per la prima volta questo teorema, pero nei libri di matematica adesso viene scritta come nella prima versione che ho scritto nel primo messaggio primo post.
avevo un po' frainteso il senso di tutto mi sa che la prima formulazione era già corretta! mea culpa! ora però ho capito: la seconda affermazione dice che l'ordine di un elemento in $ZZ_p^*$ divide p-1 (hai studiato i gruppi?)
non è necessario dimostrare che quell'n sia sempre p-1 che tra l'altro non dovrebbe essere vero.
le due affermazioni sono equivalenti:
suppongo vera la prima allora è vera anche la seconda basta prendere n=p-1
suppongo vera la seconda allora $a^n=1 (mod p)$ e $p-1=n*k$ per un opportuno k mi basta elevare a destra e a sinistra dell'uguaglianza alla k ed ottendo $a^(nk)=a^(p-1)=1 (mod p)$
dovrebbe andare, se non è chiaro fammi sapere
non è necessario dimostrare che quell'n sia sempre p-1 che tra l'altro non dovrebbe essere vero.
le due affermazioni sono equivalenti:
suppongo vera la prima allora è vera anche la seconda basta prendere n=p-1
suppongo vera la seconda allora $a^n=1 (mod p)$ e $p-1=n*k$ per un opportuno k mi basta elevare a destra e a sinistra dell'uguaglianza alla k ed ottendo $a^(nk)=a^(p-1)=1 (mod p)$
dovrebbe andare, se non è chiaro fammi sapere
tutto chiaro grazie.. solo un particolare:
se n non è sempre uguale a p-1, la prima non dice qualcosa in meno della seconda? perché i testi dovrebbero mutilarla così allora?
se n non è sempre uguale a p-1, la prima non dice qualcosa in meno della seconda? perché i testi dovrebbero mutilarla così allora?
"hunkeler":
tutto chiaro grazie.. solo un particolare:
se n non è sempre uguale a p-1, la prima non dice qualcosa in meno della seconda? perché i testi dovrebbero mutilarla così allora?
questo non so dirlo, magari è più assimilabile nella prima forma
o forse è più semplice la dimostrazione! comunque sono equivalenti quindi dicono la stessa cosa anche se non pare 
Se posso, la prima è un modo (rudimentale) per la verifica della primalità di un numero ed è un caso piuttosto semplice.
Il secondo invece, si rifà ad un risultato generale che sottointende la definizione della funzione $phi$ di Eulero ed alla riformulazione nei termini generali:
$a^(phi(n))\equiv 1 (n)$
Quali che siano $a,n in Z^+$
Il secondo invece, si rifà ad un risultato generale che sottointende la definizione della funzione $phi$ di Eulero ed alla riformulazione nei termini generali:
$a^(phi(n))\equiv 1 (n)$
Quali che siano $a,n in Z^+$
io credo che la seconda assomigli di più alla prima che al teorema di Eulero: infatti quest'ultimo è una generalizzazione del teorema di Fermat con p $in$ R, e quindi non più solo primo come nelle due versioni dell altro teorema;i tre enunciati hanno comunque molto in comune ovviamente...
tra l altro c'è un'imprecisione nella seconda versione... non specifica che p dev essere coprimo a come nella prima, per esempio:
$5$ non divide $10^n - 1$ per nessuna $n$ che divida $4$...
tra l altro c'è un'imprecisione nella seconda versione... non specifica che p dev essere coprimo a come nella prima, per esempio:
$5$ non divide $10^n - 1$ per nessuna $n$ che divida $4$...
"Lord K":
Se posso, la prima è un modo (rudimentale) per la verifica della primalità di un numero ed è un caso piuttosto semplice.
Il secondo invece, si rifà ad un risultato generale che sottointende la definizione della funzione $phi$ di Eulero ed alla riformulazione nei termini generali:
$a^(phi(n))\equiv 1 (n)$
Quali che siano $a,n in Z^+$
Mi mancava $gcd(a,n)=1$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo