Piccolo teorema di Fermat

SickBoy88
Ciao a tutti!
Qualcuno perfavore potrebbe spiegarmi il piccolo teorema di Fermat?
Perchè ho letto un po' in giro.. ma mi sembra che nessuno arrivi al nocciolo della questione.
Questo esercizio, poi, si risolve con quello?

3x$-=$ 5 mod7

Risposte
Steven11
Ciao, che intendi per "nocciolo della questione"?
Si tratta solo di dire che
$a^p\equiv a \quad \modp$ con $p$ primo.
La dimostrazione è banale se consideri il Teorema di Eulero-Fermat.
O ne trovi una per induzione su wikipedia, se non ricordo male o se non l'hanno levata.

L'esercizio in questione si risolve facilmente considerando che $3x$ puoi scriverlo anche come $10x$, giacché sono due valori congrui modulo 7.
O moltiplicando ambo i membri per $5$, che è l'inverso di $3$ mod7.

Ciao.

SickBoy88
Grazie per la risposta!
Mi sono accorto solo ora della cavolata che ho scritto. Ho sbagliato a scrivere l'esercizio.. che invece sarebbe:
$3^x -= 5 mod7$

Lord K
Osserva che:

$3*5+(-2)*7=1$

Allora

$3^(-1) \equiv5(7)$

e quindi il tuo esercizio ha come soluzione:

$x \equiv -1(6)$

Visto che in ogni caso:

$a^6 \equiv 1 (7)$

quale che sia $a$

SickBoy88
Fino ai coefficienti di bezout ok. Non capisco però come si arriva al passaggio dopo ovvero:
$3^-1 -= 5 mod7$
Come mai il -1 all'esponente?

Lord K
Da Bezout vedi che:

$3*5 \equiv 1 (7)$

Ed allora:

$3^(-1) \equiv 5 (7)$

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.