Minimo esponente classe inversa
Inviato:
26/11/2023, 11:16
da alessioben
Ciao a tutti,
ho questo quesito di algebra.
Sia a=20∈ℤ/31ℤ. Se ritieni che non esista l'inversa della classe a rispondi No, altrimenti determinane il minimo esponente positivo m tale che $ a^m=a^-1 $
Ho calcolato la classe inversa di 20 che mi è risultata essere 14.
Ora però non so come fare per trovare m t.c. $ 20^m-= 14 (mod31) $
Ho anche il dubbio che sia giusta quest'ultima espressione.
Riuscite a darmi un suggerimento? Perché non penso debba trovarlo per tentativi.
Grazie mille
Re: Minimo esponente classe inversa
Inviato:
27/11/2023, 19:58
da ProPatria
alessioben ha scritto:Ciao a tutti,
ho questo quesito di algebra.
Sia a=20∈ℤ/31ℤ. Se ritieni che non esista l'inversa della classe a rispondi No, altrimenti determinane il minimo esponente positivo m tale che $ a^m=a^-1 $
Ho calcolato la classe inversa di 20 che mi è risultata essere 14.
Ora però non so come fare per trovare m t.c. $ 20^m-= 14 (mod31) $
Ho anche il dubbio che sia giusta quest'ultima espressione.
Riuscite a darmi un suggerimento? Perché non penso debba trovarlo per tentativi.
Grazie mille
se non sbaglio è una semplice applicazione del teorema di Eulero...
Re: Minimo esponente classe inversa
Inviato:
27/11/2023, 21:06
da ProPatria
Aggiungo:
Il teorema di fermat-eulero afferma che, dati $a$ e $n$ interi coprimi, vale la relazione:
$a^(phi(n)) -= 1 mod n$
dove $phi(n)$ è la funzione di eulero che vale quanto il numero di interi coprimi con n compresi tra 1 e n.
Tu vuoi trovare $m$ tale che
alessioben ha scritto:$ 20^m-= 14 (mod 31) $
che sarebbe
$ a^m-= a^(-1) mod 31$
di conseguenza...
Re: Minimo esponente classe inversa
Inviato:
29/11/2023, 08:38
da alessioben
Vero.. ma poi come procedo?
Cioè il teorema mi dà la congruenza a 1 e non all'inversa.
Ho provato a moltiplicare a destra e a sinistra per a, per avere la conguenza a 1 sommando quindi di 1 la funzione di eulero, ma non mi risulta giusto...
Re: Minimo esponente classe inversa
Inviato:
29/11/2023, 15:59
da hydro
Il teorema di Eulero ti dice che l'ordine di $20$ divide $\phi(31)=30$, quindi può essere solo $1,2,3,5,10,15,30$. Per decidere quale sia tra questi devi calcolare le corrispondenti potenze di $20$. Per esempio, $20^2=400=30\cdot 13+10=31\cdot 13-3$, ovvero $20^2\equiv -3\mod 31$, quindi l'ordine non è $2$ (ovviamente, perchè l'unico elemento di ordine $2$ è $-1$). Adesso $20^3=20^2\cdot 20\equiv -3\cdot 20=-60\equiv 2 \mod 31$, quindi l'ordine non è neanche $3$. Poi, $20^5=20^2\cdot 20^3\equiv -6\mod 31$, quindi l'ordine non è $5$. E così via, finchè non trovi la risposta giusta.
Re: Minimo esponente classe inversa
Inviato:
30/11/2023, 14:24
da alessioben
Grazie mille!! Ci ho messo un po' a capire perché, per il teorema di Eulero, l'ordine divida la funzione di Eulero. In effetti l'ordine essendo il minimo esponente.. In pratica così facendo riduco i tentativi agli elementi invertibili di n.
Grazie mille!!