Inverse Mod N Calculator

What is Inverse Mod N?

The modular inverse of an integer a modulo n is an integer x such that:

This means that when a is multiplied by x, the result is congruent to 1 modulo n. The modular inverse exists if and only if a and n are coprime (their greatest common divisor is 1).

Inverse mod n calculations are fundamental in number theory and have important applications in cryptography, particularly in the RSA algorithm for secure data transmission.

How to Calculate Inverse Mod N

To find the modular inverse of a number a modulo n:

1. Verify that a and n are coprime (gcd(a, n) = 1).
2. Use the Extended Euclidean Algorithm to find integers x and y such that:
a × x + n × y = gcd(a, n)
3. Since gcd(a, n) = 1, the equation simplifies to:
a × x ≡ 1 mod n
4. The value of x is the modular inverse of a modulo n.

If a and n are not coprime, the modular inverse does not exist.

Formula

The modular inverse x of a modulo n can be found using the Extended Euclidean Algorithm:

Where x is the solution to the equation a × x + n × y = 1.

Example Calculation

Let's find the modular inverse of 7 modulo 26.

1. First, verify that gcd(7, 26) = 1 (they are coprime).
2. Apply the Extended Euclidean Algorithm:
26 = 3 × 7 + 5 7 = 1 × 5 + 2 5 = 2 × 2 + 1 2 = 2 × 1 + 0
3. Working backwards:
1 = 5 - 2 × 2 1 = 5 - 2 × (7 - 1 × 5) = 3 × 5 - 2 × 7 1 = 3 × (26 - 3 × 7) - 2 × 7 = 3 × 26 - 11 × 7
4. The coefficient of 7 is -11. To get a positive inverse, add 26 to -11:
-11 mod 26 = 15
5. Therefore, the modular inverse of 7 modulo 26 is 15.

Verification: 7 × 15 = 105, and 105 mod 26 = 1 (since 26 × 4 = 104 and 105 - 104 = 1).

Limitations

The modular inverse exists only when the number and modulus are coprime. If gcd(a, n) ≠ 1, the inverse does not exist.

For negative numbers, you can find the inverse of a negative number by first finding the inverse of its absolute value and then adjusting the sign appropriately.