inverso e inverso in modulo

[enigmista]

Devo farvi una semplice e imbarazzante domanda:
cos'è un inverso e come si calcola l'inverso di un numero in modulo:

ad esempio come si calcolare linverso di 15 mod 31

ho trovato un esempio sul libro che mi dice:
l'inverso di 11 mod 120 è semper 11,
visto che 11 * 11 = 121 = 1 mod 120

grazie del gentile aiuto e ciao

[Luca77]

Quindi stai parlando di inverso moltiplicativo. Te lo dico perche' Z_p e' un anello, per cui di operazioni ce ne sono due. Comunque la cosa e' abbastanza empirica: si va per tentativi. Ad esempio, in Z_6 qual e' l'inverso moltiplicativo di 4? Per definzione deve essere un x che sta in Z_6 tale che 4x=1 (mod 6). Se fai i vari casi, ti accorgi che 4 non ha inverso in Z_6. Invece 5 si': infatti 5x=1 (mod 6) ha per soluzione x=5. In Z_6 5 ha come inverso se stesso.

Luca77
http://www.llussardi.it

[lupo grigio]

Riguardo l'esistenza dell'inverso moltiplicativo di un elemento all'insieme degli interi modulo p mi pare di ricordare che esiste un teorema il quale afferma che se p è un numero primo ogni intero modulo p [escluso ovviamente lo 0...] ha l'inverso moltiplicativo.
Nell'esempio proposto da enigmista è p=31 [numero primo...] e quindi l'inverso di 15 deve esistere. Dopo un poco di tentativi si trova che l'inverso di 15 è 29 in quanto 15*29=435=1 mod 31.
Applicandosi un poco non dovrebbe essere difficile verificare se il teorema da me riportato è valido e, se tale è, trovarne una dimostrazione...

cordiali saluti!...

lupo grigio

[Luca77]

Il Teorema citato segue dalla seguente facile proprieta': in Z_p, x ha inverso se e solo se MCD(x,p)=1. Sottolineo il fatto che Z_p diventa un campo, se p e' primo. I campi Z_p sono i primi esempi di campi finiti, che forniscono un'introduzione alla Teoria di Galois.

Luca77
http://www.llussardi.it

[karl]

Volgarizzando un po' quello che dice Luca77,l'esistenza
dell'inverso moltiplicativo x di 15 (mod 31) si puo'
dedurre anche dal fatto che deve essere:
15x-31k=1 con k in Z.
Ora e' noto ( e la dimostrazione e' abbastanza facile)
che tale "diofantina" ha soluzioni <b>sse</b> il termine noto
(=1) e' divisibile per il M.C.D(15,31)=1 ,cosa che e'
ovviamente verificata in questo caso.
karl.

[Thomas]

Manca la risposta al come si calcola... Il metodo classico dovrebbe essere l'algoritmo di Euclide (cioè il metodo per trovare le sol alla diofantea di karl)...ora però nn ho tempo di spiegarlo (e dato che nn sono competente nn sarei chiearo)...ergo...

[Luca77]

Io preferisco la strada empirica, tanto non credo capiti Z_10000000000000000000000000000000 come anello...

Luca77
http://www.llussardi.it