Multiplicative Inverse mod n

Math

Find multiplicative inverse modulo n. Formula: Find x such that (a × x) ≡ 1 (mod n). Used in cryptography. Requires GCD(a, n) = 1.

Formula

Find x: (a × x) ≡ 1 (mod n) using Extended Euclidean Algorithm

a=3, n=11

Inputs
  • Number (a): 3
  • Modulus (n): 11

x=4 because (3×4) mod 11 = 1

Frequently asked questions

When needed?
RSA encryption, solving linear congruences
GCD requirement?
GCD(a,n) must equal 1 for inverse to exist