come posso trovare l'inverso di un numero con il modulo

[bergamo87]

Ciao a tutti, mi serve una mano per trovare l'inverso di 46^11 mod 143

[euphoric]

Anzitutto trovare l'inverso di \( \displaystyle {{46}}^{{11}}{\left(\text{mod}{143}\right)} \) equivale a risolvere la congruenza \( \displaystyle {{46}}^{{11}}{x}\equiv{1}{\left(\text{mod}{143}\right)} \).

Io ridurrei prima \( \displaystyle {{46}}^{{11}} \) a modulo 143, quindi \( \displaystyle {{46}}^{{11}}={{46}}^{{2}}^{3}\cdot{{46}}^{{2}}\cdot{46} \) risolvendo man mano modulo 143 arriverai velocemente a \( \displaystyle {{46}}^{{11}}\equiv{2}{\left(\text{mod}{143}\right)} \).

Quindi \( \displaystyle {2}{x}\equiv{1}{\left(\text{mod}{143}\right)} \) da cui è evidente che il risultato è \( \displaystyle {72} \)

Dovrebbe andare, no?


P.S. con \( \displaystyle {{46}}^{{2}}^{3} \) intendo \( \displaystyle {{46}}^{{8}} \), purtroppo non so in che modo si possa correttamente scrivere la potenza di potenza!

[bergamo87]

Scusa la mia ignoranza ma una volta che ho scomposto 46^11 come faccio a calcolare il modulo?

[euphoric]

\( \displaystyle {{46}}^{{2}}\equiv{114}{\left(\text{mod}{143}\right)} \), calcoli le congruenze man mano che scomponi.
Quando non puoi applicare teoremi, come la legge di Eulero, etc. credo tu debba agire così.
È lo stesso metodo che utilizziamo in crittografia (RSA, ad esempio)