Piccolo teorema di Fermat
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
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
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.
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.
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$
Mi sono accorto solo ora della cavolata che ho scritto. Ho sbagliato a scrivere l'esercizio.. che invece sarebbe:
$3^x -= 5 mod7$
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$
$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$
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?
$3^-1 -= 5 mod7$
Come mai il -1 all'esponente?
Da Bezout vedi che:
$3*5 \equiv 1 (7)$
Ed allora:
$3^(-1) \equiv 5 (7)$
$3*5 \equiv 1 (7)$
Ed allora:
$3^(-1) \equiv 5 (7)$