Finding the Modular Inverse #numbertheory

The modular inverse of a number a modulo n is an integer x such that a * x ≡ 1 (mod n). In other words, it's the number you can multiply by a to get a product that leaves a remainder of 1 when divided by n. This concept is crucial in various fields, including cryptography and number theory.

Q1. What is the modular inverse of 2 modulo 5, that is, 2^(−1) (mod 5)?

Q2. Use the extended Euclidean algorithm to find the modular inverse of 31 modulo 105.

Note: gcd(31, 105) = 1