Minimo esponente classe inversa

[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

[ProPatria]

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...

[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

$ 20^m-= 14 (mod 31) $

che sarebbe
$ a^m-= a^(-1) mod 31$

di conseguenza...

[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...

[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.

[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!!