Modular Multiplicative Inverse

A modular inverse of a modulo m is a residue x satisfying ax≡1 (mod m). It replaces division only when it exists. The exact existence condition is gcd(a,m)=1 for m≥2. Extended Euclid finds inverses under prime or composite moduli without factoring m; Fermat’s theorem offers exponentiation when the modulus is known prime. We provide both complete approaches with separate contracts.

Prerequisites: Extended Euclid; Modular Arithmetic; Binary Exponentiation.

Build the idea

1. 1. Derive the existence condition

   If ax≡1, then ax+my=1 for some integer y, so every common divisor of a,m divides 1; hence gcd(a,m)=1. Conversely, Bézout supplies such x,y when that GCD is one. Reducing the identity modulo m proves x is an inverse. This is an if-and-only-if statement, not merely a sufficient shortcut.

   $$\mathrm{ax}\equiv 1\left(\mathrm{mod}m\right)\iff \gcd (a,m)=1$$

2. 2. Normalize the Bézout coefficient

   Run Extended Euclid on normalized a and positive m. Its x may be negative, so return (x%m+m)%m. For a=3,m=11, coefficients 4 and −1 give 3·4−11=1, hence inverse 4. Check by multiplying modulo m; a returned coefficient without normalization is mathematically valid but not the usual canonical residue.

3. 3. Detect failure instead of dividing anyway

   For a=6,m=9, GCD is 3 and no inverse exists. Some congruences 6x≡b may still have solutions when 3 divides b, but there is no single multiplicative inverse of 6. Treat such equations with Diophantine reasoning rather than pretending division by 6 is globally available modulo 9.

4. 4. Use Fermat only for a prime modulus

   If p is prime and a is nonzero modulo p, a^(p−1)≡1, so a^(p−2) is its inverse. The supplementary program fixes p=1000000007, a known prime, and rejects a≡0. This method costs logarithmic exponentiation. For a composite modulus, m−2 is generally the wrong exponent even when an inverse exists.

   $$a^{p-2}\equiv a^{-1}\left(\mathrm{mod}p\right)$$

5. 5. Apply modular division carefully

   To solve x≡b/a modulo m under coprimality, compute b·inverse(a) modulo m with safe multiplication. Cancelling ordinary fractions before reduction can sometimes avoid a nonexistent modular denominator, but it needs its own exact derivation. The program’s m≤10^9 makes inverse verification products safe in long long.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
using ll=long long;
ll extended(ll a,ll b,ll&x,ll&y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1,g=extended(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1; // Substitute the smaller equation back into a,b.
    return g;
}
int main(){
    ll a,m;
    std::cin>>a>>m;
    a=(a%m+m)%m;
    ll x,y,g=extended(a,m,x,y);
    if(g!=1){
        std::cout<<"NO INVERSE\n";
        return 0;
    }
    ll inverse=(x%m+m)%m;
    std::cout<<inverse<<'\n'<<a*inverse%m<<'\n';
}

Complexity analysis

Extended Euclid: O(log m) arithmetic time and recursion stack. Fermat supplement: O(log p) modular multiplications, O(1) iterative exponentiation space. Moduli and normalized operands are at most about 10^9, so products fit long long. The fixed-prime guarantee is part of the supplementary program, not a runtime primality claim.

Example input and output

Read a m with |a|≤10^18 and 2≤m≤10^9. Print inverse then its product with normalized a modulo m, or NO INVERSE.

Input

3 11

Output

4
1

3·4=12≡1 modulo 11, so 4 is the inverse.

Read a with |a|≤10^18. The modulus is the fixed prime 1000000007; print its inverse or NO INVERSE.

// Key idea: 5. Apply modular division carefully To solve x≡b/a modulo m under coprimality, compute
// b·inverse(a) modulo m with safe multiplication.
#include<iostream>
using ll=long long;
ll power(ll a,unsigned long long exponent,ll mod){
    a=(a%mod+mod)%mod;
    ll result=1%mod;
    while(exponent>0){
        if(exponent&1ULL){
            result=result*a%mod;
        }
        a=a*a%mod;
        exponent>>=1;
    }
    return result;
}
int main(){
    ll a;
    std::cin>>a;
    const ll prime=1000000007;
    a=(a%prime+prime)%prime;
    if(a==0){
        std::cout<<"NO INVERSE\n";
    }
    else{
        std::cout<<power(a,prime-2,prime)<<'\n';
    }
}

Input

2

Output

500000004

2×500000004=1000000008≡1 modulo 1000000007.

Complexity: O(log p) time, O(1) auxiliary space.

Practical applications

Use for modular rational expressions, factorial formulas with invertible denominators, hashing normalization and CRT. Extended Euclid is appropriate under any coprime modulus; Fermat is convenient when a prime modulus is a known problem constant. Later lessons explain Euler’s generalized theorem.

Check your understanding

When may division by a be replaced by multiplying one inverse modulo m?

Put it into practice

Compare the Extended-Euclid and Fermat answers under the fixed prime.