Problema teoria dei numeri
trovare le soluzioni di x^35 = 1 (mod37). mi era venuta un'idea... provando a caso con wolfram alpha la funzione x^35 mod37
è bigettiva, ciò significa che l'unica soluzione ce l'ho per x=1; ho pensato che la cosa fosse valida per ogni funzione x^k mod n con n e k primi, ma un primo controesempio si ha per k=2 e n=5; quindi come dimostrare che l'unica soluzione è x=1 ? e più in generale, quando una funzione x^k mod n è bigettiva?
ps: scusate per l'ordine un po' confusionario, ma non so usare il latex, anche se effettivamente dovrei iniziare ad impararlo...
è bigettiva, ciò significa che l'unica soluzione ce l'ho per x=1; ho pensato che la cosa fosse valida per ogni funzione x^k mod n con n e k primi, ma un primo controesempio si ha per k=2 e n=5; quindi come dimostrare che l'unica soluzione è x=1 ? e più in generale, quando una funzione x^k mod n è bigettiva?
ps: scusate per l'ordine un po' confusionario, ma non so usare il latex, anche se effettivamente dovrei iniziare ad impararlo...
Risposte
"whitefang":Infatti, non c'ho capito molto! -_-
...scusate per l'ordine un po' confusionario, ma non so usare il latex, anche se effettivamente dovrei iniziare ad impararlo...
Vediamo se ti so spiegare il gioco: considerata la \(\varphi\) di Eulero, hai che \(\varphi(37)=2\) quindi \(35=17\cdot 2+1\) per cui tu vuoi risolvere l'equazione congruenziale \(x^{17\cdot\varphi(37)+1}\equiv1(mod 37)\); per il teorema di Eulero-Fermat hai che per ogni \(\forall x\in\{1;...;36\},\,x^2\equiv1(mod37)\) da cui la soluzione richiesta (modulo miei errori).
Del resto mi sono rifiutato di leggerlo dato che con le prime due parole mi sono iniziati a girare gli occhi.
"j18eos":What?
...hai che \(\varphi(37)=2\) ...
$37$ è un numero primo, dunque $\varphi(37)=36$
La \(\varphi\) di Eulero non la uso mai, ero convinto che contasse i divisori di un numero intero e non i numeri coprimi! 
Comunque hai dato un buon spunto per la risoluzione.
Penso che si possa fare così:
$AA x in {2,...,36}$ si ha che $x^36 -=_(mod 37) 1$,
per il Piccolo Teorema di Fermat (che è un corollario del teorema di Eulero-Fermat).
Quindi si ha sempre che $(x^35*x) -=_(mod 37) 1$
Non può esistere $x in {2,3,...,36}$ tale che $x^35 -=_(mod 37) 1$, altrimenti ...
Penso che si possa fare così:
$AA x in {2,...,36}$ si ha che $x^36 -=_(mod 37) 1$,
per il Piccolo Teorema di Fermat (che è un corollario del teorema di Eulero-Fermat).
Quindi si ha sempre che $(x^35*x) -=_(mod 37) 1$
Non può esistere $x in {2,3,...,36}$ tale che $x^35 -=_(mod 37) 1$, altrimenti ...
grazie mille, adesso tutto mi è chiaro, quelle dispense bastarde non capisco per quale motivo non citano il teorema di eulero-fermat...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo