gen-briefly-explain-modular-inverses-and-one-common-misconceptio-96ec

Briefly explain modular inverses and one common misconception about it.

## Modular Inverses A **modular inverse** of a number *a* modulo *n* is a number *x* such that: **ax ≡ 1 (mod n)** In other words, when you multiply *a* by *x*, the result leaves a remainder of 1 when divided by *n*. **Example:** The modular inverse of 3 modulo 7 is 5, because 3 × 5 = 15 ≡ 1 (mod 7). ## Common Misconception **Misconception:** "Every number has a modular inverse modulo *n*." **Reality:** A modular inverse of *a* modulo *n* exists **only if *a* and *n* are coprime** (their greatest common divisor is 1). For example, 2 has no modular inverse modulo 6, because gcd(2,6) = 2 ≠ 1. There's no integer that you can multiply by 2 to get a result that's 1 more than a multiple of 6.