Inverse Modulo Calculator

This function calculates the multiplicative inverse x from an integer a and modulo m.

To calculate, enter the integers a and m, then click the 'Calculate' button.

Description of the multiplicative inverse

The multiplicative inverse of a number \(a\) modulo \(m\) is a number \(x\) such that: \[ a⋅x≡1(mod \ m)\] The modular multiplicative inverse of a number modulo \(m\) only exists if \(a\) and \(m\) are relatively prime (gcd(a, m) = 1).
In other words: \(x\) is the multiplicative inverse of \( a\) modulo \(m\), if the product \( a⋅x \) leaves a remainder of \( 1 \) when divided by \( m\).

Calculating the multiplicative inverse:

There are several methods to calculate the multiplicative inverse. The two most common are:

1. Extended Euclidean algorithm

   
   

   The extended Euclidean algorithm not only finds the greatest common divisor (gcd) of \(a\) and \(m\), but also the coefficients \(x\) and \(y\), such that \[a⋅x+m⋅y=gcd(a,m)\] If \( gcd(a,m)=1\), then \(x\) is the multiplicative inverse of \(a\) modulo \(m\).

   
   

2. Trial and error (for small numbers)

   
   

   For small numbers, you can simply try all possible values ​​of \(x\) until you find the right inverse.

   Example:

   Find the multiplicative inverse of \(3\) modulo \(7\).

   Step 1: Check if an inverse exists

   Calculate

   \[gcd(3,7)=1\]

   Since the gcd is 1, a multiplicative inverse exists.

   Step 2: Calculating with the extended Euclidean algorithm

   Finding x and y such that:

   \[ 3x+7y=1\]

   Applying the extended Euclidean algorithm:

   \[7=2⋅3+1\] \[ 3=3⋅1+0\]

   Substituting backwards:

   \[ 1=7−2⋅3\]

   This gives:

   \[ x=−2 \ \text{and} \ y=1\]

   Since we are calculating modulo 7, we take \[x=−2 \ \text{mod} \ 7=5\].

   Result:

   The multiplicative inverse of 3 modulo 7 is 5, because:

   \[ 3⋅5=15≡1(mod7)\]

You can find a video on the subject here.