Domanda su inverso moltiplicativo

[manu.sevo]

Si calcoli l’inverso di 237 in Z6743.
questa era la domanda di un mio esame e vorrei sapere se esiste una procedura per calcolare l'inverso di un x (come in questo grande) in un anello z ( ancora più strano e grande di x)

[Studente Anonimo]

Ciao, usando l'algoritmo di Euclide trovi due interi $a$ e $b$ tali che $237a+6743b=1$ (identità di Bezout), ora riduci modulo $6743$ ottenendo $237a$ congruente a $1$ modulo $6743$ quindi l'inverso di $237$ modulo $6743$ è $a$.

[manu.sevo]

scusa non è che potresti farmi vedere tutti i passaggi con i numeri sopra indicati che credo di non aver ben capito grazie mille

[spugna2]

Si tratta di fare una serie di divisioni con resto finché non ottieni $1$:

$6743=28*237+107$
$237=2*107+23$
$107=4*23+15$ (o anche $5*23-8$, per avere un resto più piccolo e concludere più velocemente)
$23=3*8-1$

A questo punto, tramite delle sostituzioni, puoi esprimere $1$ in funzione dei due numeri di partenza:

$1=3*8-23=$
$=3(5*23-107)-23=$
$=14*23-3*107=$
$=14(237-2*107)-3*107=$
$=14*237-31*107=$
$=14*237-31(6743-28*237)=$
$=882*237-31*6743$

Abbiamo quindi $882*237 -=1$ $( mod 6743)$, cioè l'inverso cercato è $882$.