Introduction

The modular multiplicative inverse, also known as the modular inverse element, modular reciprocal, or number-theoretic reciprocal, is a concept in number theory. For a given modulus $m$, a number $a$ has a modular multiplicative inverse $x$ if:

$$a \cdot x \equiv 1 \pmod{m}$$

In this case, $x$ is the multiplicative inverse of $a$ modulo $m$. This modular inverse $x$ exists if and only if $a$ and $m$ are coprime (i.e., $\gcd(a, m) = 1$).

Methods for Computing Modular Multiplicative Inverse

Extended Euclidean Algorithm

Theory

The Extended Euclidean Algorithm builds upon the Euclidean Algorithm and finds integer coefficients $x$ and $y$ such that:

$$\text{gcd}(a,m)=ax+my$$

According to Bézout’s Identity, if $\gcd(a,m)=1$, then there exist integers $x$ and $y$ such that:

$$ax+my=1$$

In this case, $x$ is the modular multiplicative inverse of $a$ modulo $m$, meaning:

$$a^{−1} \equiv x \pmod{m}$$

Steps

1. For given $a$ and modulus $m$, use the Extended Euclidean Algorithm to solve: $ax + my = \gcd(a,m)$

2. If $\gcd(a,m) \neq 1$, the modular inverse does not exist

3. If $\gcd(a,m) = 1$, the coefficient $x$ is the modular inverse

   • If $x < 0$, add the modulus $m$ to make the result positive
   • The final result should satisfy $0 \leq x < m$

Example

Find the multiplicative inverse of $3$ modulo $7$.

1. Use the Extended Euclidean Algorithm to solve $3x + 7y = \gcd(3,7)$

   Calculation process: $$ \begin{align*} 7 &= 2 \times 3 + 1 \\ 3 &= 3 \times 1 + 0 \\ \Rightarrow& \gcd(3, 7) = 1 \end{align*} $$

   Reverse substitution for coefficients: $$ \begin{align*} 1 &= 7 - 2 \times 3 \\ 1 &= 1 \times 7 + (-2) \times 3 \end{align*} $$

2. We obtain $3 \times (-2) + 7 \times 1 = 1$

3. Therefore, $x = -2$ is the modular inverse

   • Since $-2 < 0$, add the modulus $7$
   • $-2 + 7 = 5$
   • Thus, the multiplicative inverse of $3$ modulo $7$ is $5$

Verification: $3 \times 5 = 15 \equiv 1 \pmod{7}$

Code Implementation

#include <iostream>
using namespace std;

// Extended Euclidean Algorithm
// Returns gcd(a,b) and computes coefficients x and y through reference
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long gcd = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}

// Calculate modular multiplicative inverse
// Returns the multiplicative inverse of a modulo m, or -1 if it doesn't exist
long long mod_inverse(long long a, long long m) {
    long long x, y;
    long long gcd = extended_gcd(a, m, x, y);
    
    if (gcd != 1) {
        return -1;  // Modular inverse doesn't exist
    }
    
    // Ensure result is positive and less than m
    return (x % m + m) % m;
}

int main() {
    // Test case
    long long a = 3;
    long long m = 7;
    
    long long inv = mod_inverse(a, m);
    
    if (inv == -1) {
        cout << "Multiplicative inverse of " << a << " modulo " << m << " does not exist" << endl;
    } else {
        cout << "Multiplicative inverse of " << a << " modulo " << m << " is: " << inv << endl;
        
        // Verify result
        cout << "Verification: " << a << " * " << inv << " mod " << m 
             << " = " << (a * inv) % m << endl;
    }
    
    return 0;
}

Fermat’s Little Theorem

Theory

Fermat’s Little Theorem states that if $m$ is prime and $a$ is an integer coprime to $m$ (i.e., $\gcd(a, m) = 1$), then:

$$ a^{m-1} \equiv 1 \pmod{m} $$

This means that when $a$ and $m$ are coprime, $a$ raised to the power of $m-1$ is congruent to 1 modulo $m$.

Using Fermat’s Little Theorem, we can calculate the modular multiplicative inverse. In modulo $m$, the multiplicative inverse of a number $a$ is an integer $x$ such that:

$$ a \times x \equiv 1 \pmod{m} $$

According to Fermat’s Little Theorem, we have:

$$ a^{m-1} \equiv 1 \pmod{m} $$

This can be rewritten as:

$$ a \times a^{m-2} \equiv 1 \pmod{m} $$

Therefore, $a^{m-2}$ is the multiplicative inverse of $a$ modulo $m$.

Steps

1. Verify conditions: Ensure $m$ is prime and $a$ is coprime to $m$ (i.e., $\gcd(a, m) = 1$).
2. Calculate $a^{m-2} \mod m$: Use fast exponentiation to compute $a$ raised to the power of $m-2$ modulo $m$.

Example

Let’s calculate the multiplicative inverse of 3 modulo 7. Since 7 is prime and 3 is coprime to 7, we can use Fermat’s Little Theorem. According to the theorem, the inverse is:

$$ 3^{7-2} \mod 7 = 3^5 \mod 7 $$

The calculation process:

• $3^2 = 9 \equiv 2 \pmod{7}$
• $3^4 = (3^2)^2 = 2^2 = 4 \pmod{7}$
• $3^5 = 3^4 \times 3 = 4 \times 3 = 12 \equiv 5 \pmod{7}$

Therefore, the multiplicative inverse of 3 modulo 7 is 5, because:

$$ 3 \times 5 = 15 \equiv 1 \pmod{7} $$

Code Implementation

#include <iostream>
using namespace std;

// Fast exponentiation algorithm to calculate a^b % p
long long mod_exp(long long a, long long b, long long p) {
    long long result = 1;
    a = a % p;
    while (b > 0) {
        if (b % 2 == 1) {                   // If b is odd
            result = (result * a) % p;
        }
        b = b >> 1;                         // Divide b by 2
        a = (a * a) % p;                    // Square a
    }
    return result;
}

// Calculate multiplicative inverse of a modulo p
long long mod_inverse(long long a, long long p) {
    return mod_exp(a, p - 2, p);
}

int main() {
    long long a = 3, p = 7;
    cout << "The modular inverse of " << a << " mod " << p << " is " << mod_inverse(a, p) << endl;
    return 0;
}

Applications

1. Cryptography
   • RSA Encryption Algorithm: RSA is one of the most widely used asymmetric encryption algorithms. Modular multiplicative inverse plays a crucial role in RSA, being used in the calculation of private keys.
   • Elliptic Curve Cryptography: In elliptic curve cryptography, modular multiplicative inverse is used to calculate slopes in point addition and point multiplication operations on finite fields, enabling secure encryption and signature functionality.
   • Digital Signature Algorithm: In the Digital Signature Algorithm (DSA), modular multiplicative inverse is used to compute signature values.
2. Computer Science
   • Rolling Hash: In the Rolling Hash algorithm, modular multiplicative inverse is used when removing characters from the beginning of a string by multiplying by the modular inverse of the base to efficiently update hash values.

References

• Wikipedia - Modular multiplicative inverse
• Wikipedia - Euclidean algorithm
• Wikipedia - Extended Euclidean algorithm
• Wikipedia - Bézout’s identity
• Calculate Modular Inverse and Some Common Competition Mathematics by Grorge
• 【Note】Modular Multiplicative Inverse by YuiHuang
• How is the concept of multiplicative inverse applied in modular arithmetic, and why is it important for decryption in ciphers such as affine ciphers?
• Wikipedia - RSA (cryptosystem)
• Wikipedia - Rolling hash
• Wikipedia - Elliptic-curve cryptography
• Wikipedia - Digital Signature Algorithm