Inverso modulo n

[Triptofanoo]

Ciao a tutti. Avrei bisogno di una mano per calcolare l inverso di 78 mod 1009. Ho provato e riprovato ma nn ci riesco.
HELP

[Gi81]

$78*13=1014-=5_(mod1009)$ Sfrutta questo fatto

[Triptofanoo]

Mhh, fino a qui ero arrivato... solo che nn riesco a passare agli step successivi. Ovvero che

$ 207 *78 -= 2 mod 1009 $

$ 608 * 78 -= 1 mod 1009 $

[Gi81]

Qual è l'inverso di $5$ modulo $1009$?

[Triptofanoo]

nn vorrei dire una stupidaggine... ma è 202 mod 1009?

[Gi81]

Esattamente. Quindi $13*202$...

[Triptofanoo]

quindi $ 13*202 - 1009*2 = 608 $

[Triptofanoo]

ma perche per 13?

[Gi81]

Perchè $78*(13*202)-=(78*13)*202-=5*202-=1$ (tutto modulo $1009$)

[Triptofanoo]

ma in poche parole si riduce il 78 mod 1009 a un numero piu piccolo per poter poi calcolare l'inverso di quel numero piu facilemente. E tale inverso è dunque l inverso del numero da cui siamo partiti?

[Gi81]

Precisamente

[Triptofanoo]

uhh ok mi pare di aver capito, grazie mille

[Triptofanoo]

ma ad esempio per trovare l inverso di 144 mod 233 come procederesti?

[Gi81]

Putroppo qui non è immediatissimo. Bisogna sfruttare l'algoritmo di Euclide e l'identità di Bezout:
$144x+233y=1$ , $x,y in ZZ$

1) $233=1*144+89$
2) $144=1*89+55$
3) $89=1*55+34$
4) $55=1*34+21$
5) $34=1*21+13$
6) $21=1*13+8$
7) $13=1*8+5$
8) $8=1*5+3$
9) $5=1*3+2$
10)$3=1*2+1$

Dunque,

$1=3-2=
$=3-(5-3)=3(2)+5(-1)=
$=(8-5)*(2)+5*(-1)=8*(2)+5*(-3)=
$=8*2+(13-8)*(-3)=8(5)+13(-3)=
$=(21-13)*5+13(-3)=21*(5)+13(-8)=
$=21*(5)+(34-21)*(-8)=21*(13)+34(-8)=
$=(55-34)(13)+34(-8)=55(13)+34(-21)=
$=55(13)+(89-55)(-21)=55(34)+89(-21)=
$=(144-89)(34)+89(-21)=144(34)+89(-55)=
$=144(34)+(233-144)(-55)=233(-55)+144(89)$

Abbiamo pertanto trovato che $1=233*(-55)+144(89)$

[Gi81]

In realtà questa marea di calcoli si può evitare se si riconosce che $233$ e $144$ sono due numeri di Fibonacci consecutivi.
Vale una proprietà per i numeri di Fibonacci:
Presi quattro numeri di Fibonacci consecutivi,
il prodotto del primo col quarto è sempre pari al prodotto del secondo col terzo, aumentato o diminuito di $1$.
In formule, $F_n*F_(n+3)=F_(n+1)*F_(n+2)+1$, oppure $F_n*F_(n+3)=F_(n+1)*F_(n+2)-1$ ( il $+$ o il $-$ si alternano lungo la sequenza)

possiamo sfruttare questa proprietà a nostro vantaggio: quattro numeri di Fibonacci sonsecutivi sono $55$, $89$, $144$ e $233$:
$55*233=89*144-1$. Quindi $144*89-=1$ (modulo $233$)