The modular arithmetic calculator computes a mod n, GCD(a,n), the modular inverse using the extended Euclidean algorithm, and modular exponentiation aᵏ mod n — with full step-by-step Euclidean division table.
Modular Arithmetic Calculator
Steps
How to Use the Modular Arithmetic Calculator
Modular arithmetic — "clock arithmetic" — computes remainders after division. a mod n is the remainder when a is divided by n. It appears in computer science (hash tables, cyclic buffers), cryptography (RSA, Diffie-Hellman), and number theory.
Basic Remainder (a mod n)
17 mod 5 = 2, because 17 = 3×5 + 2. For negative numbers: −7 mod 5 = 3, because −7 = (−2)×5 + 3 (remainder is always non-negative). The calculator always returns the least non-negative residue.
Extended Euclidean and Modular Inverse
The extended Euclidean algorithm finds integers x, y such that ax + ny = GCD(a,n). When GCD = 1, x is the modular inverse of a. Example: 3⁻¹ mod 7. GCD(3,7) = 1, and 3×5 = 15 = 2×7+1, so 3×5 ≡ 1 (mod 7). The inverse is 5.
Modular Exponentiation
Computing aᵏ mod n directly overflows for large k. Fast exponentiation uses repeated squaring: 2¹⁰ mod 13. 2²=4, 2⁴=16≡3, 2⁸=9, 2¹⁰=2⁸×2²=9×4=36≡10 (mod 13). This runs in O(log k) steps.
FAQ
What is modular arithmetic?
Modular arithmetic (also called 'clock arithmetic') computes remainders after division. a mod n is the remainder when a is divided by n. Example: 17 mod 5 = 2 because 17 = 3×5 + 2. It wraps around like a clock: 14 mod 12 = 2 (2 PM).
What is the extended Euclidean algorithm?
The extended Euclidean algorithm finds GCD(a,n) and also finds integers x and y such that ax + ny = GCD(a,n). When GCD(a,n) = 1, this gives the modular inverse of a: x is the inverse because ax ≡ 1 (mod n).
What is a modular inverse?
The modular inverse of a (mod n) is a number x such that ax ≡ 1 (mod n). It exists only when GCD(a,n) = 1 (a and n are coprime). Example: 3⁻¹ (mod 7) = 5, because 3×5 = 15 ≡ 1 (mod 7).
Is this calculator free?
Yes, completely free with no signup required. All calculations run in your browser.
How is modular arithmetic used in RSA encryption?
RSA uses modular exponentiation: encrypt message m as c = mᵉ mod n, decrypt as m = cᵈ mod n. The keys are chosen so eᵈ ≡ 1 (mod φ(n)), making modular inverse essential. The security relies on the difficulty of factoring large n = p×q.