Modular Arithmetic & Congruence Calculator

Modular Arithmetic Guide

What Is Modular Arithmetic?

a mod n = the remainder when a is divided by n. 17 mod 5 = 2 (17 = 3 × 5 + 2). 23 mod 7 = 2 (23 = 3 × 7 + 2). −1 mod 7 = 6 (not −1 — modular arithmetic uses positive remainders). Congruence notation: a ≡ b (mod n) means n divides (a − b). 17 ≡ 2 (mod 5) because 5 divides (17 − 2) = 15. The clock is the most intuitive modular arithmetic example: clocks operate modulo 12 (or 24). 15:00 ≡ 3:00 (mod 12). Day of the week cycles modulo 7.

What should I know about Modular Exponentiation?

Computing aᵇ mod n directly for large b is infeasible — but fast modular exponentiation solves it efficiently. Method: repeated squaring. To compute 2¹⁰ mod 7: 2¹ = 2. 2² = 4. 2⁴ = 16 ≡ 2 (mod 7). 2⁸ ≡ 4 (mod 7). 2¹⁰ = 2⁸ × 2² ≡ 4 × 4 = 16 ≡ 2 (mod 7). Fermats little theorem: if p is prime and gcd(a,p) = 1, then aᵖ⁻¹ ≡ 1 (mod p). This dramatically simplifies modular exponentiation for prime moduli. Used in: RSA encryption, digital signatures, Diffie-Hellman key exchange.

What should I know about Modular Inverse?

The modular inverse of a mod n is the value x such that ax ≡ 1 (mod n). Exists only if gcd(a, n) = 1 (a and n are coprime). Found using extended Euclidean algorithm. Example: 3⁻¹ mod 7: we need 3x ≡ 1 (mod 7). Test: 3×5 = 15 = 2×7 + 1 ≡ 1 (mod 7). So 3⁻¹ ≡ 5 (mod 7). Application: in RSA encryption, the private key exponent d is computed as d = e⁻¹ mod φ(n) — the modular inverse of the public exponent e modulo Euler's totient function of n.

What should I know about Cryptography Applications?

RSA encryption: select two large primes p and q. Compute n = pq (public key modulus). Choose public exponent e coprime to φ(n) = (p−1)(q−1). Private key d = e⁻¹ mod φ(n). Encrypt: c = mᵉ mod n. Decrypt: m = cᵈ mod n. Security: factoring n into p and q is computationally infeasible for large n (2048+ bits). Diffie-Hellman: two parties agree on a prime p and generator g. Each picks a secret a or b and computes gᵃ mod p or gᵇ mod p publicly. Shared secret: gᵃᵇ mod p — computed independently by both parties without ever transmitting the secret itself, which is the foundational idea behind secure key exchange over an insecure channel.

What should I know about Modular Addition and Multiplication Rules?

Modular arithmetic allows you to reduce numbers at each step rather than computing a huge result first: (a+b) mod n = [(a mod n)+(b mod n)] mod n, and the same holds for multiplication: (a×b) mod n = [(a mod n)×(b mod n)] mod n. This means 47×53 mod 12 can be computed as (47 mod 12)×(53 mod 12) mod 12 = 11×5 mod 12 = 55 mod 12 = 7, without ever needing the full product 2491. This property is what makes modular arithmetic practical for cryptography and computer science, where numbers involved (in RSA encryption, for example) are hundreds of digits long — reducing at every step keeps all intermediate values small and fast to compute, rather than building up an astronomically large number only to reduce it once at the end.

What do I need to know about Clock Arithmetic as an Everyday Example?

A 12-hour clock is modular arithmetic in disguise, using mod 12 (with 12 standing in for 0). If it's 9 o'clock and 7 hours pass, the new time is (9+7) mod 12 = 16 mod 12 = 4 o'clock, not 16 o'clock. Days of the week work the same way under mod 7: if today is day 3 (Wednesday, counting Monday as 1) and you want to know the day 100 days from now, compute (3+100) mod 7 = 103 mod 7 = 5 (Friday). This everyday familiarity with 'wrapping around' is the best intuition for understanding modular arithmetic generally — any quantity that cycles back to a starting point after a fixed interval (clock hours, calendar days, compass bearings mod 360°, colour wheel hues mod 360°) is mathematically a modular arithmetic problem, whether or not it's labelled as one.

What do I need to know about Solving Linear Congruences?

A linear congruence has the form ax ≡ b (mod m), and solving it for x is the modular-arithmetic equivalent of solving a linear equation. A solution exists if and only if gcd(a, m) divides b; when gcd(a, m) = 1, a unique solution exists modulo m, found by multiplying both sides by a's modular inverse. For example, solving 3x ≡ 4 (mod 7): since gcd(3,7) = 1, the modular inverse of 3 mod 7 is 5 (because 3×5 = 15 ≡ 1 mod 7), so multiplying both sides by 5 gives x ≡ 20 ≡ 6 (mod 7). When gcd(a, m) > 1 and it does divide b, there are exactly gcd(a, m) distinct solutions modulo m instead of just one, which is a key difference from solving ordinary linear equations, where a single valid solution (or none) is the only possibility.

What should I know about Modular Inverses Modulo 11?

What should I know about a Worked Example: The Chinese Remainder Theorem?

The Chinese Remainder Theorem solves a system of simultaneous congruences with different, coprime moduli: find a number that leaves remainder 2 mod 3, remainder 3 mod 5, and remainder 2 mod 7. Since 3, 5, 7 are pairwise coprime, a unique solution exists modulo 105. Combine x≡2(mod3) with x≡3(mod5): numbers satisfying the first are 2,5,8,11,14,...; x=8 works (8 mod5=3), giving x≡8(mod15). Combine x≡8(mod15) with x≡2(mod7): numbers satisfying the first are 8,23,38,...; x=23 works (23 mod7=2). So x≡23(mod105). Checking x=23: 23÷3 remainder 2 ✓; 23÷5 remainder 3 ✓; 23÷7 remainder 2 ✓. This step-by-step method works well by hand for small moduli, and is used directly inside RSA decryption optimisation (CRT-RSA) to speed up decryption significantly.

What should I know about Check Digits (ISBN, Barcodes)?

Modular arithmetic also underlies the check digits found on barcodes and ISBNs, which catch simple transcription errors. The ISBN-13 check digit is calculated so the weighted sum of all 13 digits (alternating weights of 1 and 3) is congruent to 0 mod 10. For the digits 978-0-13-468599 (12 known digits), multiply alternately by 1 and 3 and sum: 9+21+8+0+1+9+4+18+8+15+9+27 = 129. The check digit c must make the total a multiple of 10: c=(10−(129 mod10)) mod10 = (10−9) mod10 = 1, so the ISBN ends in 1 (matching the real ISBN 978-0-13-468599-1). This simple mod-10 arithmetic is why a single mistyped digit, or two adjacent digits swapped, almost always produces an invalid check digit.

What should I know about Zeller's Congruence (Finding the Day of the Week)?

Modular arithmetic can even determine the day of the week for any calendar date, using algorithms like Zeller's congruence, which compute a result modulo 7 and map it to a day. The core idea is that each calendar unit (years, months, and the extra day added every leap year) contributes a known, fixed offset modulo 7, and summing all these offsets together and reducing mod 7 gives the day of the week directly, without needing a calendar at all. This works because the Gregorian calendar's leap year pattern repeats on a predictable 400-year cycle, which is itself just a much larger modular structure layered on top of the familiar 7-day week. The same underlying principle — breaking a real-world cyclic system into fixed modular contributions and summing them — appears throughout computer science wherever a hash function needs to distribute inputs evenly across a fixed number of categories.

What should I know about Negative Numbers in Modular Arithmetic?

Modular arithmetic handles negative numbers by always wrapping them around to a positive remainder within the range 0 to n−1, rather than leaving a negative result. To compute −17 mod 5, first find how many full multiples of 5 fit below −17: −17 = (−4)×5 + 3, so −17 mod 5 = 3, not −2 (which would be the result of simple division-with-remainder in many programming languages, a common source of bugs when porting mathematical modular arithmetic into code). This convention — always returning a value between 0 and n−1 inclusive — ensures modular arithmetic behaves consistently as a closed system, where every integer, positive or negative, maps to exactly one of the n possible remainders, which is essential for applications like hashing and cryptography that rely on predictable, well-defined output ranges.