Modular Arithmetic Calculator (Mod Calculator)
A modular arithmetic calculator with 4 modes: basic mod, modular addition/subtraction/multiplication, modular exponentiation (repeated squaring), and modular inverse (extended Euclidean algorithm). Handles negative mod and huge exponents accurately using BigInt.
Basic Properties of Modular Arithmetic
| Property | Description |
|---|---|
| (a + b) mod n = ((a mod n) + (b mod n)) mod n | Whether you take the mod before or after adding, the result is exactly the same. |
| (a − b) mod n = ((a mod n) − (b mod n) + n) mod n | Since subtraction can produce a negative value, adding n at the end before taking mod n again keeps the result within [0, n). |
| (a × b) mod n = ((a mod n) × (b mod n)) mod n | As with addition, taking the mod partway through multiplication does not change the final result. This property underlies the fast computation of exponentiation (repeated squaring). |
| a and n are coprime ⇔ an inverse of a modulo n exists | Only when the extended Euclidean algorithm gives gcd(a, n) = 1 does there exist an x (the inverse) satisfying a × x ≡ 1 (mod n). |
Tips
- The behavior of mod on negative numbers differs between programming languages. This tool follows the mathematical definition (the result is always between 0 and n − 1), so -7 mod 3 is 2, not -1.
- The exponentiation mode uses repeated squaring, so it returns results instantly even when the exponent has hundreds of digits. The same algorithm is used in RSA encryption and decryption.
- Clock time is a familiar example of modular arithmetic: converting "15:00" to 12-hour notation gives 15 mod 12 = 3 o'clock.
- The inverse mode works as long as a and n are coprime (their greatest common divisor is 1), even if n is not prime.
- In competitive programming, problems often ask for an answer modulo a large prime such as 1,000,000,007 instead of the raw, huge number. This tool's exponentiation mode is handy for checking such calculations by hand.
Frequently Asked Questions
Side Note — The "Clock Arithmetic" Behind Modern Cryptography
Modular arithmetic (congruence) is often called "clock arithmetic." On a 12-hour clock, 13 o'clock is treated as the "same" as 1 o'clock — this is exactly the congruence 13 ≡ 1 (mod 12), an idea that focuses only on the remainder when a number is divided by a modulus (12 in this case). The German mathematician Carl Friedrich Gauss systematized the "≡" notation for congruence in his 1801 book Disquisitiones Arithmeticae, turning this idea into a standard tool of modern mathematics.
This seemingly simple operation underlies the foundations of modern internet security. In public-key cryptosystems such as RSA, "modular exponentiation" — computing a huge number raised to a power and then taking the remainder modulo n — is the central operation in encryption and decryption. Because the exponent and modulus can each run to hundreds of digits, naively computing the full power before taking the remainder would be computationally explosive. Repeated squaring instead requires only a number of multiplications proportional to the number of digits in the exponent, making it practical.
Computing modular inverses via the extended Euclidean algorithm is likewise a foundational technique used across computer science, from cryptography to coding theory and hash function design. The fact that "arithmetic over 2,000 years old" and "cutting-edge security technology" rest on the same mathematical foundation is a striking symbol of the universality of number theory.