Enter a number and modulus to find the inverse.
The modular inverse of a number \( a \) under a modulus \( m \) is another number \( b \) such that: \( a \cdot b \equiv 1 \pmod{m} \) In simpler terms, \( b \) is the number that, when multiplied by \( a \), gives a remainder of 1 when divided by \( m \). Modular inverses are widely used in number theory, cryptographic algorithms, and modular arithmetic.
To compute the modular inverse of \( a \) under \( m \), follow these steps:
Solution:
1. Check coprimality:
gcd(7, 26) = 1, so 7 and 26 are coprime.
2. Apply the Extended Euclidean Algorithm:
Compute gcd(7, 26) using the Euclidean algorithm:
Since the remainder is 1, gcd(7, 26) = 1.
3. Back-substitute to find coefficients:
Starting from the second-to-last equation, express 1 as a linear combination of 7 and 26:
\( 1 = 5 - 2 \times 2 \)
Substitute \( 2 = 7 - 1 \cdot 5 \):
\( 1 = 5 - 2 \times (7 - 1 \times 5) = 3 \times 5 - 2 \times 7 \)
Substitute \( 5 = 26 - 3 \cdot 7 \):
\( 1 = 3 \times (26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 \)
Thus, \( -11 \) is the modular inverse.
4. Normalize the result:
Convert \( -11 \) to a positive equivalent under modulus 26: \( -11 \equiv 15 \pmod{26} \).
Result: The modular inverse of 7 under 26 is 15.
Solution:
1. Check coprimality:
gcd(3, 11) = 1, so 3 and 11 are coprime.
2. Apply the Extended Euclidean Algorithm:
Compute gcd(3, 11):
Since the remainder is 1, gcd(3, 11) = 1.
3. Back-substitute to find coefficients:
Starting from the second-to-last equation:
\( 1 = 3 - 1 \times 2 \)
Substitute \( 2 = 11 - 3 \cdot 3 \):
\( 1 = 3 - 1 \times (11 - 3 \times 3) = 4 \times 3 - 1 \times 11 \)
Thus, \( 4 \) is the modular inverse.
Result: The modular inverse of 3 under 11 is 4.