Home
/
Categories
/
Home › Advanced Math & Statistics › Modular inverse Modular inverse calculator This modular inverse calculator finds the modular multiplicative inverse of an integer \(a\) modulo \(m\). In other words, it finds an integer \(x\) such that \(a x \equiv 1 \pmod m\), or tells you when no such inverse exists. The tool is built for students, engineers and cryptography practitioners who need a reliable, step-by-step implementation of the extended Euclidean algorithm. Integer \(a\) Any non-zero integer. The calculator will automatically reduce it modulo \(m\). Modulus \(m\) Positive integer > 1. For cryptography, \(m\) is often a large prime or product of primes. Show extended Euclidean algorithm steps Compute modular inverse Reset Quick examples Click an example to auto-fill the fields and see a typical modular inverse computation. a = 3, m = 11 a = 17, m = 43 a = 35, m = 64 a = −7, m = 26 Result Extended Euclidean algorithm steps The table below shows the recurrence for the extended Euclidean algorithm applied to the reduced value \(a' = a \bmod m\) and the modulus \(m\). Step q r s t What is a modular inverse? Given an integer \(a\) and a modulus \(m > 1\), a modular multiplicative inverse of \(a\) modulo \(m\) is an integer \(x\) such that \[ a x \equiv 1 \pmod m. \] Intuitively, \(x\) plays the role of a reciprocal of \(a\) in modular arithmetic: multiplying by \(x\) “undoes” the effect of multiplying by \(a\), but only up to congruence modulo \(m\). Existence and uniqueness A modular inverse exists if and only if \(\gcd(a, m) = 1\) (that is, \(a\) and \(m\) are coprime). If an inverse exists, it is unique modulo \(m\) . All solutions differ by a multiple of \(m\). If \(\gcd(a, m) > 1\), then no modular inverse exists. Algorithm used by this calculator This calculator uses the extended Euclidean algorithm , a classic number-theoretic method that not only computes \(\gcd(a, m)\) but also finds integers \(x\) and \(y\) such that \[ a x + m y = \gcd(a, m). \] When \(\gcd(a, m) = 1\), the coefficient \(x\) is precisely a modular inverse of \(a\) modulo \(m\). We then reduce \(x\) to the standard range \(0 \le x \le m-1\). Extended Euclidean algorithm (high-level outline) Reduce the input \(a\) modulo \(m\): set \(a' = a \bmod m\). Initialize \(r_0 = a'\), \(r_1 = m\), \(s_0 = 1\), \(s_1 = 0\), \(t_0 = 0\), \(t_1 = 1\). Repeat until \(r_k = 0\): Compute the quotient \(q_k = \lfloor r_{k-1}
/
r_k \rfloor\). Update \(r_{k+1} = r_{k-1} - q_k r_k\). Update \(s_{k+1} = s_{k-1} - q_k s_k\), \(t_{k+1} = t_{k-1} - q_k t_k\). When the loop ends, the last non-zero remainder is \(\gcd(a', m)\), and the corresponding \(s\) is the inverse. Worked example Consider \(a = 17\) and \(m = 43\). They are already reduced, so \(a' = 17\), \(m = 43\). Compute \(\gcd(17, 43)\) with the extended Euclidean algorithm. We find \(\gcd(17, 43) = 1\). One of the Bézout representations is \[ 17 \cdot 38 + 43 \cdot (-15) = 1. \] Therefore \(x = 38\) is a modular inverse of \(17\) modulo \(43\). Check: \[ 17 \cdot 38 = 646,\quad 646 \bmod 43 = 1. \] So the calculator will display \(x = 38\) as the modular inverse. Typical applications Cryptography — RSA key generation, Diffie–Hellman, ECDSA and other public-key schemes. Chinese remainder theorem — combining congruences with different moduli. Solving linear congruences — equations of the form \(a x \equiv b \pmod m\). Modular linear algebra — inverting matrices modulo a prime. Coding theory and algorithms — operations in finite fields and residue rings. Frequently asked questions How do I solve \(a x \equiv b \pmod m\) using the modular inverse? First, compute the modular inverse \(a^{-1}\) of \(a\) modulo \(m\) (if it exists). Then multiply both sides of the congruence by \(a^{-1}\): \[ x \equiv a^{-1} b \pmod m. \] This calculator gives you \(a^{-1}\); you can then multiply by \(b\) and reduce modulo \(m\). What if \(\gcd(a, m) \neq 1\)? If \(\gcd(a, m) > 1\), then \(a\) does not have a modular inverse modulo \(m\). In that case, the calculator clearly states that no inverse exists. For a congruence \(a x \equiv b \pmod m\), solutions may still exist, but they require a slightly different analysis (dividing everything by \(\gcd(a, m)\) and reducing the modulus). Can I use negative values for \(a\)? Yes. The calculator internally replaces \(a\) with \(a' = a \bmod m\), so negative values are reduced to an equivalent representative in \(\{0, 1, \dots, m-1\}\) before applying the algorithm. Are very large cryptographic moduli supported? This implementation uses standard JavaScript integers and is numerically safe up to \(|a|, |m| \le 9{,}007{,}199{,}254{,}740{,}991\) (the maximum safe integer in JavaScript). For industrial-grade cryptographic key sizes (for example 2048-bit RSA), you should rely on specialised big-integer libraries or computer algebra systems. Related advanced math tools Modular arithmetic Euclidean algorithm (gcd) Chinese remainder theorem Modulo calculator Remainder and division Number theory toolbox Euler’s totient function Prime number checker Explore more math & statistics Linear algebra calculators Statistics toolbox Complex number calculator Boolean algebra

r_k \rfloor\). Update \(r_{k+1} = r_{k-1} - q_k r_k\). Update \(s_{k+1} = s_{k-1} - q_k s_k\), \(t_{k+1} = t_{k-1} - q_k t_k\). When the loop ends, the last non-zero remainder is \(\gcd(a', m)\), and the corresponding \(s\) is the inverse. Worked example Consider \(a = 17\) and \(m = 43\). They are already reduced, so \(a' = 17\), \(m = 43\). Compute \(\gcd(17, 43)\) with the extended Euclidean algorithm. We find \(\gcd(17, 43) = 1\). One of the Bézout representations is \[ 17 \cdot 38 + 43 \cdot (-15) = 1. \] Therefore \(x = 38\) is a modular inverse of \(17\) modulo \(43\). Check: \[ 17 \cdot 38 = 646,\quad 646 \bmod 43 = 1. \] So the calculator will display \(x = 38\) as the modular inverse. Typical applications Cryptography — RSA key generation, Diffie–Hellman, ECDSA and other public-key schemes. Chinese remainder theorem — combining congruences with different moduli. Solving linear congruences — equations of the form \(a x \equiv b \pmod m\). Modular linear algebra — inverting matrices modulo a prime. Coding theory and algorithms — operations in finite fields and residue rings. Frequently asked questions How do I solve \(a x \equiv b \pmod m\) using the modular inverse? First, compute the modular inverse \(a^{-1}\) of \(a\) modulo \(m\) (if it exists). Then multiply both sides of the congruence by \(a^{-1}\): \[ x \equiv a^{-1} b \pmod m. \] This calculator gives you \(a^{-1}\); you can then multiply by \(b\) and reduce modulo \(m\). What if \(\gcd(a, m) \neq 1\)? If \(\gcd(a, m) > 1\), then \(a\) does not have a modular inverse modulo \(m\). In that case, the calculator clearly states that no inverse exists. For a congruence \(a x \equiv b \pmod m\), solutions may still exist, but they require a slightly different analysis (dividing everything by \(\gcd(a, m)\) and reducing the modulus). Can I use negative values for \(a\)? Yes. The calculator internally replaces \(a\) with \(a' = a \bmod m\), so negative values are reduced to an equivalent representative in \(\{0, 1, \dots, m-1\}\) before applying the algorithm. Are very large cryptographic moduli supported? This implementation uses standard JavaScript integers and is numerically safe up to \(|a|, |m| \le 9{,}007{,}199{,}254{,}740{,}991\) (the maximum safe integer in JavaScript). For industrial-grade cryptographic key sizes (for example 2048-bit RSA), you should rely on specialised big-integer libraries or computer algebra systems. Related advanced math tools Modular arithmetic Euclidean algorithm (gcd) Chinese remainder theorem Modulo calculator Remainder and division Number theory toolbox Euler’s totient function Prime number checker Explore more math & statistics Linear algebra calculators Statistics toolbox Complex number calculator Boolean algebra

Calculators in r_k \rfloor\). Update \(r_{k+1} = r_{k-1} - q_k r_k\). Update \(s_{k+1} = s_{k-1} - q_k s_k\), \(t_{k+1} = t_{k-1} - q_k t_k\). When the loop ends, the last non-zero remainder is \(\gcd(a', m)\), and the corresponding \(s\) is the inverse. Worked example Consider \(a = 17\) and \(m = 43\). They are already reduced, so \(a' = 17\), \(m = 43\). Compute \(\gcd(17, 43)\) with the extended Euclidean algorithm. We find \(\gcd(17, 43) = 1\). One of the Bézout representations is \[ 17 \cdot 38 + 43 \cdot (-15) = 1. \] Therefore \(x = 38\) is a modular inverse of \(17\) modulo \(43\). Check: \[ 17 \cdot 38 = 646,\quad 646 \bmod 43 = 1. \] So the calculator will display \(x = 38\) as the modular inverse. Typical applications Cryptography — RSA key generation, Diffie–Hellman, ECDSA and other public-key schemes. Chinese remainder theorem — combining congruences with different moduli. Solving linear congruences — equations of the form \(a x \equiv b \pmod m\). Modular linear algebra — inverting matrices modulo a prime. Coding theory and algorithms — operations in finite fields and residue rings. Frequently asked questions How do I solve \(a x \equiv b \pmod m\) using the modular inverse? First, compute the modular inverse \(a^{-1}\) of \(a\) modulo \(m\) (if it exists). Then multiply both sides of the congruence by \(a^{-1}\): \[ x \equiv a^{-1} b \pmod m. \] This calculator gives you \(a^{-1}\); you can then multiply by \(b\) and reduce modulo \(m\). What if \(\gcd(a, m) \neq 1\)? If \(\gcd(a, m) > 1\), then \(a\) does not have a modular inverse modulo \(m\). In that case, the calculator clearly states that no inverse exists. For a congruence \(a x \equiv b \pmod m\), solutions may still exist, but they require a slightly different analysis (dividing everything by \(\gcd(a, m)\) and reducing the modulus). Can I use negative values for \(a\)? Yes. The calculator internally replaces \(a\) with \(a' = a \bmod m\), so negative values are reduced to an equivalent representative in \(\{0, 1, \dots, m-1\}\) before applying the algorithm. Are very large cryptographic moduli supported? This implementation uses standard JavaScript integers and is numerically safe up to \(|a|, |m| \le 9{,}007{,}199{,}254{,}740{,}991\) (the maximum safe integer in JavaScript). For industrial-grade cryptographic key sizes (for example 2048-bit RSA), you should rely on specialised big-integer libraries or computer algebra systems. Related advanced math tools Modular arithmetic Euclidean algorithm (gcd) Chinese remainder theorem Modulo calculator Remainder and division Number theory toolbox Euler’s totient function Prime number checker Explore more math & statistics Linear algebra calculators Statistics toolbox Complex number calculator Boolean algebra.

Modular Inverse Calculator

/modular-inverse