1. What is Modular Inverse?

The modular inverse of an integer \( a \) modulo \( m \) is an integer \( x \) such that \( a \times x \equiv 1 \mod m \). It exists only if \( a \) and \( m \) are coprime (their greatest common divisor is 1).

2. How Does the Calculator Work?

The calculator uses the Extended Euclidean Algorithm to find integers \( x \) and \( y \) that satisfy:

When \( \gcd(a, m) = 1 \), the solution \( x \) modulo \( m \) gives the modular inverse.

3. Applications of Modular Inverse

Details: Modular inverses are essential in cryptography (RSA algorithm), computer algebra systems, and solving linear congruences.

4. Using the Calculator

Tips: Enter positive integers where \( a \) is less than \( m \). The modulus \( m \) must be greater than 1.

5. Frequently Asked Questions (FAQ)

Q1: When does a modular inverse exist?
A: A modular inverse exists only when \( a \) and \( m \) are coprime (gcd(a, m) = 1).

Q2: What's the difference between this and regular division?
A: Modular inverse is about finding a multiplicative inverse in modular arithmetic, not standard division.

Q3: Can negative numbers have modular inverses?
A: Yes, but the calculator returns a positive result between 0 and \( m-1 \).

Q4: How is this used in cryptography?
A: RSA encryption uses modular inverses to compute private keys from public keys.

Q5: What's the time complexity of this algorithm?
A: The Extended Euclidean Algorithm runs in \( O(\log(\min(a, m))) \) time.