Modular Arithmetic Calculator
Modular inverses by the extended Euclidean algorithm, Euler's totient from the factorisation, linear congruences with every solution listed, and fast modular powers — number theory with the working shown.
Example — Inverse of 3 modulo 113⁻¹ ≡ 4 (mod 11)
How we got it — the example, step by step
- Extended Euclid on 3 and 11: 11 = 3×3 + 2; 3 = 1×2 + 1; back-substitute to write 1 = 4×3 − 1×11.
- So 3 × 4 ≡ 1 (mod 11), and the inverse is 4.
Check it backwards
3 × 4 = 12, and 12 mod 11 = 1 — the definition of the inverse, verified by one multiplication.
Questions people also ask
Why does 6x ≡ 4 (mod 10) have two answers?
Because gcd(6, 10) = 2 divides 4: the congruence splits into 2 solutions modulo 10 — x ≡ 4 and x ≡ 9. In general ax ≡ b (mod m) has either no solution or exactly gcd(a, m) of them, and the tool tells you which case you are in and why.
What is Euler's totient used for?
φ(n) counts the numbers up to n that are coprime to n. It is the exponent in Euler's theorem — a^φ(n) ≡ 1 (mod n) — which is the arithmetic RSA encryption is built on. φ(36) = 12, from the primes 2 and 3: 36 × ½ × ⅔.