Piccolo Teorema di Fermat

[Gio111]

Che cos'è? In una soluzione ho letto questo nome ma non so che cosa dice...

[iTz_CaBe_95]

Uno di questi due(non so esattamente quale):
a^p congruo ad a (mod p)
a^(p-1) congruo ad 1 (mod p)

[Gio111]

Non sono la stessa cosa?

[tex]a^p \equiv a \pmod p[/tex] non si ottiene da [tex]a^{p-1} \equiv 1 \pmod p[/tex] moltiplicando a ad ambo i membri?

però con a = 5 e p = 5 non funziona...

p deve essere per caso primo?

[iTz_CaBe_95]

Si, scusa. Cmq qui tutto: http://it.wikipedia.org/wiki/Piccolo_teorema_di_Fermat
Cmq non ho ancora capito come si usa il latex...

[Francutio]

[tex]a^p \equiv a \pmod p[/tex]

Questo vale sempre, l'altra forma solo quando a e p sono coprimi. In generale con le divisioni nelle congruenze bisogna andarci con i piedi di piombo...

[Drago]

Innanzitutto $p$ deve essere primo.
In questo caso vale $a^p\equiv a\pmod p$ per ogni $a$ intero.
Se invece $(a,p)=1$ (ovvero $a$ e $p$ sono coprimi, ovvero $p\nmid a$) allora vale anche $a^{p-1}\equiv1\pmod p$. (Segue dalla versione generale "dividendo" per $a$)

Infine, dato un $n$ intero positivo qualunque e un $a$ coprimo a questo, vale $\displaystyle a^{\varphi(n)}\equiv1\pmod n$ (Teorema di Eulero o Eulero-Fermat)

[ngshya]

Cmq non ho ancora capito come si usa il latex...

http://forum.olimato.org/come-scrivere- ... m-t16.html
Spero che ti possa essere d'aiuto.

[afullo]

Innanzitutto $p$ deve essere primo.
In questo caso vale $a^p\equiv a\pmod p$ per ogni $a$ intero.
Se invece $(a,p)=1$ (ovvero $a$ e $p$ sono coprimi, ovvero $p\nmid a$) allora vale anche $a^{p-1}\equiv1\pmod p$. (Segue dalla versione generale "dividendo" per $a$)

Infine, dato un $n$ intero positivo qualunque e un $a$ coprimo a questo, vale $\displaystyle a^{\varphi(n)}\equiv1\pmod n$ (Teorema di Eulero o Eulero-Fermat)

dove si può "dividere" per $a$ in quanto, se $a$ e $p$ sono primi tra loro, allora $a$ ammette inverso in $\mathbb{Z}_p$, e dunque è possibile moltiplicare per esso. in caso contrario $a$ sarebbe zero-divisore e non ammetterebbe inverso, ergo non si potrebbe fare.

[Lasker]

Conosco questo teorema, ma mi ha sempre incuriosito il "test di primalità di Fermat".
Vorrei sapere in che cosa consiste e se è utilizzabile in una gara per sapere se un numero è primo o no.

[ngshya]

Secondo me, in una gara, più che sapere i vari test di primalità, è più utile sapere le scomposizioni degli anni vicini...