Calcolatore dell'Inverso di Modulo n

Eccoti nel calcolatore dell'inverso di modulo n! È qui per aiutarti ogni volta che hai bisogno di determinare gli inversi moltiplicativi modulari o gli inversi additivi modulari.

Se non sai cos'è l'inverso modulare, scorri la pagina! Ti forniremo tutte le definizioni necessarie e ti insegneremo come trovare l'inverso modulare a mano!

Prima di imparare cos'è l'inverso modulare, dobbiamo familiarizzare con la relazione di congruenza.

Sia n un numero naturale (non nullo). Due numeri interi a e b si dicono congruenti modulo n se hanno entrambi lo stesso resto quando vengono divisi per n. In modo equivalente, la situazione è la stessa quando la differenza a - b è divisibile per n con zero come resto, cioè se a - b è un multiplo di n.

Indichiamo il fatto che a e b sono congruenti modulo n con:

a ≡ b (mod n).

Vediamo due esempi.

• Esempio 1

  14 e 99 sono congruenti modulo 5:

  14 ≡ 99 (mod 5),

  perché 99 - 14 = 85 e 85 è un multiplo di 5. In modo equivalente, vediamo che 14 e 99 hanno lo stesso resto quando vengono divisi per 5:

  14 mod 5 = 4

  99 mod 5 = 4

• Esempio 2

  14 e 99 sono non congruenti modulo 7.

  Siccome 99 - 14 = 85 e 85 non è un multiplo di 7. In modo equivalente, è sufficiente verificare che 14 e 99 hanno resti diversi quando vengono divisi per 7:

  14 mod 7 = 0

  99 mod 7 = 1

Per saperne di più sull'operazione modulo, e in particolare sulle sue applicazioni nella vita reale, visita il nostro calcolatore di modulo.

Siamo pronti per imparare cos'è l'inverso modulare!

Sia a e x un numero intero. Si dice che x è un inverso modulare di a quando un'operazione algebrica eseguita su x, e a produce l'elemento neutro.

A seconda che l'operazione in questione sia un'addizione o una moltiplicazione, distinguiamo due tipi di inversi modulari — additivi e moltiplicativi.

Parliamo di questi due concetti:

Inverso modulare additivo

Nel caso dell'addizione, l'elemento neutro è 0. Diciamo quindi che x è un inverso additivo di a modulo m se a + x e 0 sono congruenti modulo m:

a + x ≡ 0 mod m

Un inverso additivo di a modulo m esiste sempre per ogni a e m. È dato da un numero intero della forma -a + k × m, dove k è un numero intero. Di solito vogliamo trovare l'inverso nell'intervallo {0, ... , m - 1}, cioè nell'insieme dei resti della divisione per m.

Come trovare l'inverso modulare additivo a mano? È molto facile! Ecco i passi da seguire per trovare l'inverso modulare di a modulo m:

1. Scrivi a;
2. Scrivi i numeri creati aggiungendo o sottraendo ripetutamente m ad a; e
3. Scegli il numero compreso tra 0 e m - 1.

Vediamo come funziona.

• Esempio 1

  Troviamo l'inverso additivo di 4 modulo 30.

  I numeri della forma -4 + 30k sono: ..., -4, 26, 56, ....

  Quindi, nell'insieme {0, ..., 29} l'inverso additivo di 4 modulo 30 è 26.

• Esempio 2

  Troviamo l'inverso additivo di 44 modulo 13.

  I numeri della forma -44 + 13k sono: ..., -44, -31, -18, -5, 8, 22....

  Quindi, nell'insieme {0, ..., 12} l'inverso additivo di 44 modulo 13 è 8.

Inverso modulare moltiplicativo

Ricordiamo che l'elemento neutro della moltiplicazione è 1. Quindi, x è un inverso moltiplicativo di a modulo m se a × x e 1 sono congruenti modulo m:

a × x ≡ 1 mod m

A differenza degli inversi additivi, l'inverso modulare moltiplicativo non esiste sempre! Se esiste, tuttavia, tutti i numeri della forma x + k × m soddisfano la congruenza richiesta. In particolare, in questi casi è sempre possibile trovare la soluzione (esattamente una!) nell'intervallo {1, ... , m - 1}.

Un esempio

Non esiste un inverso modulare moltiplicativo di 2 modulo 6. Puoi verificare questa affermazione controllando che per x ∊ {1, 2, 3, 4, 5} l'operazione 2 × x (mod 6) non produce 1.

È fondamentale ricordare che l'inverso modulare moltiplicativo di a modulo m esiste se e solo se a e m sono coprimi, ovvero se il loro massimo comune divisore (MCD) è uguale a uno. In particolare, se m è primo, allora l'inverso modulare moltiplicativo di m esiste per qualsiasi a ≠ 0 che non sia un multiplo di m.

L'intera teoria degli inversi modulari può sembrare un po' astratta e probabilmente ti starai chiedendo: "Perché mai qualcuno dovrebbe interessarsi agli inversi moltiplicativi modulari?" Ebbene, devi sapere che il calcolo degli inversi moltiplicativi modulari è essenziale in crittografia, in particolare nel metodo di crittografia RSA. Ciò significa che gli inversi moltiplicativi modulari proteggono la tua carta di credito!

Ovviamente, il metodo più veloce per determinare gli inversi modulari moltiplicativi è utilizzare il nostro calcolatore per l'inverso modulare! 😉 Tuttavia, se hai bisogno di imparare a trovare l'inverso modulare a mano, consulta la prossima sezione.

In questa sezione spieghiamo come trovare l'inverso modulare moltiplicativo. Esistono tre metodi principali:

• Il metodo ingenuo (chiamato anche metodo della forza bruta, è semplice ma lento);
• L'algoritmo euclideo esteso (più veloce, funziona in tutti i casi); e
• Il piccolo teorema di Fermat (più veloce, più bello, ma funziona solo in alcuni casi).

Indipendentemente dal metodo utilizzato, il primo passo è assicurarsi che l'inverso modulare moltiplicativo esista — ricorda che devi verificare se a e m sono coprimi, cioè se MCD(a,m) = 1. Per farlo, puoi utilizzare il nostro Calcolatore di MCD e m.c.m. 🇺🇸.

Metodo ingenuo

Un metodo ingenuo consiste nel provare tutti i numeri dell'insieme {0, ..., m - 1}. Per ogni numero x di questo insieme, calcola a × x mod m, cioè il resto della divisione di a × x per m.

L'inverso modulare di a modulo m è il valore di x per il quale il resto è uguale a 1.

Algoritmo euclideo esteso

Il secondo metodo utilizza l'identità di Bézout e l'algoritmo euclideo esteso.

Identità di Bézout. Supponiamo che a e b siano numeri interi. Esistono due numeri interi x e y tali che: a × x + b × y = gcd(a, b).

Ricordiamo che l'algoritmo euclideo esteso ci permette di determinare efficacemente MCD(a, b) insieme ai numeri interi x e y, la cui esistenza è garantita dall'identità di Bézout.

Ora vediamo come utilizzare questa teoria per trovare l'inverso moltiplicativo di a modulo m:

1. Ricordiamo che a e m sono supposti relativamente primi, quindi sappiamo che gcd(a,m) = 1;

2. Quindi, dall'identità di Bézout sappiamo che:

   a × x + m × y = 1

   per alcuni numeri interi x e y. Utilizziamo l'algoritmo euclideo esteso per trovarli;

3. Ora vediamo come è collegato all'inverso modulare moltiplicativo. Applicando l'operazione mod m a entrambi i lati dell'equazione precedente, otteniamo:

   a × x + m × y ≡ 1 (mod m); e

4. Poiché ogni multiplo di m è congruente a 0 modulo m, otteniamo in particolare: m × y ≡ 0 (mod m). Di conseguenza, possiamo semplificare la nostra equazione in:

   a × x ≡ 1 (mod m).

Ma quest'ultima equazione dice che l'intero x trovato dall'algoritmo di Euclide esteso è proprio l'inverso moltiplicativo di a modulo m! Tra l'altro, questo è il metodo utilizzato dal nostro calcolatore per l'inverso di modulo n. 😀

Piccolo teorema di Fermat

L'ultimo metodo utilizza il piccolo teorema di Fermat. Supponiamo che m sia un numero primo e che a non sia un multiplo di m.

Il piccolo teorema di Fermat
Se m è primo e a non è divisibile per m, allora a^m-1 - 1 è divisibile per m.

Possiamo scrivere l'affermazione del piccolo teorema di Fermat come

a^m-1 - 1 ≡ 1 mod m

che, a sua volta, possiamo riscrivere come

a × a^m-2 - 1 ≡ 1 mod m

Questa equazione dice che l'inverso moltiplicativo di a modulo m è uguale a a^m-2.

L'utilizzo del calcolatore dell'inverso di modulo n è semplice:

1. Scegli il tipo di inverso modulare che ti interessa trovare:
   • Inverso modulare moltiplicativo, oppure
   • Inverso modulare additivo;
2. Inserisci i coefficienti dell'equazione che vuoi risolvere; e
3. Il nostro calcolatore dell'inverso di modulo n mostrerà la risposta insieme a una breve spiegazione.