Omni Calculator logo
Ultimo aggiornamento:

Calcolatore dell'Inverso di Modulo n

Indice

Congruenza modulareChe cos'è l'inverso modulare?Come si calcola l'inverso modulare?Come si usa questo calcolatore dell'inverso di modulo n?FAQ

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!

Congruenza modulare

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!

Che 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.

🙋 L'inverso modulare moltiplicativo è legato all'esponenziazione modulare — vedi il calcolatore di potenza modulo n di Omni per saperne di più!

Come si calcola l'inverso modulare?

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 am-1 - 1 è divisibile per m.

Possiamo scrivere l'affermazione del piccolo teorema di Fermat come

am-1 - 1 ≡ 1 mod m

che, a sua volta, possiamo riscrivere come

a × am-2 - 1 ≡ 1 mod m

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

Come si usa questo calcolatore dell'inverso di modulo n?

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.
FAQ

101 ha un inverso modulare moltiplicativo di 4620?

, 101 e 4620 sono coprimi (il loro unico fattore comune è 1), quindi l'inverso moltiplicativo di 101 mod 4620 esiste. Possiamo facilmente verificare che è uguale a 1601, perché 101 × 1601 ≡ 161 701 e 161 701 = 4620 × 35 + 1; cioè, 101 × 1601 = 1 (mod 4620). Tuttavia, mentre è facile verificare l'esistenza dell'inverso modulare, per trovare il risultato è necessario utilizzare l'algoritmo euclideo esteso.

Come si trova l'inverso additivo di 15 modulo 7?

Per determinare l'inverso additivo di 15 mod 7:

  1. Scrivi -15, cioè l'inverso del numero di cui ti serve il modulo;
  2. Aggiungi ripetutamente 7 a -15. In questo modo otterremo la sequenza -15, -8, -1, 6, 13, 20...;
  3. Da questa sequenza, scegliamo il numero compreso tra 0 e 6. Si tratta di 6; e
  4. Abbiamo trovato l'inverso additivo di 15 mod 7!

Come si verifica se esiste l'inverso di un modulo?

Per verificare se l'inverso di a mod m esiste, devi controllare se a e m sono coprimi. A tal fine:

  1. Elenca tutti i fattori (divisori) di a;
  2. Elenca tutti i fattori (divisori) di m; e
  3. Verifica se l'unico fattore comune è 1.

Quali numeri hanno un inverso modulare?

Ricordiamo che il numero in questione e 10 devono essere coprimi per avere un inverso modulare. Possiamo facilmente verificare che:

  • 1, 3, 7, 9 sono coprimi con 10, quindi ognuno di loro ha un inverso moltiplicativo modulo 10, che può essere calcolato con l'aiuto dell'algoritmo di Euclide esteso; e
  • 2, 4, 5, 6, 8 non sono coprimi con 10, quindi nessuno di loro ha un inverso modulare.

Cerchiamo un x tale che:

a × x = 1 mod m

Check out 75 similar arithmetic calculators ➗
Absolute changeAbsolute valueAdding and subtracting fractions...72 more