Modular Arithmetic Calculator

Calculate modular arithmetic operations including modulo, modular inverse, and modular exponentiation for cryptography and number theory.

What is Modular Arithmetic?

Modular arithmetic is a system of arithmetic for integers where numbers "wrap around" after reaching a certain value (the modulus). It's often described as "clock arithmetic."

The expression a mod m gives the remainder when a is divided by m. For example, 17 mod 5 = 2 because 17 = 3 × 5 + 2.

Basic Operations

Modular arithmetic supports all basic operations:

• Addition: (a + b) mod m = ((a mod m) + (b mod m)) mod m
• Subtraction: (a - b) mod m = ((a mod m) - (b mod m)) mod m
• Multiplication: (a × b) mod m = ((a mod m) × (b mod m)) mod m

Modular Exponentiation

Modular exponentiation computes a^b mod m efficiently using the square-and-multiply algorithm. This is crucial for RSA encryption.

For example, 3^5 mod 7 = 243 mod 7 = 5.

Modular Inverse

The modular inverse of a modulo m is a number x such that:

a × x ≡ 1 (mod m)

A modular inverse exists only when a and m are coprime (gcd(a, m) = 1). It's calculated using the Extended Euclidean Algorithm.

For example, the inverse of 3 mod 7 is 5, because 3 × 5 = 15 ≡ 1 (mod 7).

Applications of Modular Arithmetic

Modular arithmetic is fundamental in many areas:

• Cryptography: RSA encryption, Diffie-Hellman key exchange
• Computer Science: Hash functions, checksums, random number generation
• Number Theory: Prime testing, factorization algorithms
• Coding Theory: Error detection and correction codes
• Music Theory: Twelve-tone technique and pitch class
• Calendar Calculations: Day of week algorithms

Why does 17 mod 5 = 2 and not -3?

Both answers are mathematically correct in the sense that 2 and -3 differ by 5 (the modulus), so they represent the same equivalence class modulo 5. The convention in this calculator — and in mathematics, computer science, and cryptography — is to return the non-negative remainder: the smallest value r such that 0 ≤ r < m. So 17 mod 5 returns 2 (because 17 = 3 × 5 + 2), and -3 mod 5 also returns 2 (because -3 = -1 × 5 + 2). This is called the "Euclidean" or "floored" modulo. Some programming languages (C, Java, JavaScript with %) use "truncated" modulo which preserves the sign of the dividend — so JavaScript's -3 % 5 returns -3, not 2. This calculator uses the mathematical convention because it is unambiguous and matches what every number theory and cryptography textbook does.

When does a modular inverse exist?

The inverse a⁻¹ mod m exists if and only if gcd(a, m) = 1, that is, a and m share no common factor besides 1 — they are coprime. Example: 3 mod 7 — gcd(3, 7) = 1, so the inverse exists, and is 5 (because 3 × 5 = 15 ≡ 1 mod 7). Example: 6 mod 9 — gcd(6, 9) = 3, so the inverse does not exist. This is computed using the Extended Euclidean Algorithm, which produces both the gcd and the inverse simultaneously. The condition is critical for RSA: the encryption exponent e and the totient φ(n) must be coprime, otherwise the private key cannot be derived. This calculator reports "no inverse" when gcd > 1, rather than silently giving a wrong answer.

Why is modular exponentiation important for RSA encryption?

RSA encryption computes c = m^e mod n, where m is the plaintext message, e is the public exponent (typically 65537), and n is the public modulus (typically 2048 or 4096 bits). For a 2048-bit n, the values can be hundreds of digits long. Computing m^e first and then reducing modulo n is impossible — the intermediate value would be astronomically large, far more than any computer can store. The square-and-multiply algorithm (also called modular exponentiation by repeated squaring) interleaves squaring with reduction modulo n, keeping all intermediate values smaller than n. For e = 65537 = 2^16 + 1, you need only 17 modular multiplications instead of 65536 — a roughly 4000-fold speedup. Most secure cryptographic libraries also add constant-time implementations to prevent timing attacks.

What is the difference between a mod m and a % m in programming?

They are not the same. Mathematical modulo (a mod m) always returns a non-negative result for positive m: 0 ≤ result < m. Programming's % operator depends on the language. C, C++, Java, JavaScript, Go: truncated modulo — sign matches the dividend, so -7 % 3 returns -1. Python: floor modulo — sign matches the divisor, so -7 % 3 returns 2. Mathematical convention: -7 mod 3 = 2 (matches Python). When porting cryptographic or number-theoretic code from a math source to JavaScript or C, you must handle the negative case explicitly: ((a % m) + m) % m gives the correct mathematical result regardless of sign. This calculator implements the mathematical convention, so results match number-theory textbooks regardless of the user's programming background.

Why is modular arithmetic called "clock arithmetic"?

Because a clock face is the most familiar example. A 12-hour clock works modulo 12: 11 o'clock + 4 hours = 3 o'clock, because 11 + 4 = 15, and 15 mod 12 = 3. Time "wraps around" the modulus the same way modular arithmetic does. A 24-hour military clock works modulo 24, a day-of-week schedule works modulo 7, and angles work modulo 360 degrees (or modulo 2π radians). Whenever you have a cyclic quantity — angles, days, hours, musical pitch classes, color hue values — modular arithmetic is the natural framework. The clock metaphor was popularized in Gauss's 1801 Disquisitiones Arithmeticae, the founding work of modular arithmetic, where he introduced the ≡ congruence notation we still use.

Can the modulus be negative or zero?

Zero, never — division by zero is undefined, and a mod 0 makes no sense. This calculator rejects modulus = 0 with an error. Negative modulus is mathematically allowed but conventionally treated as positive (-5 is equivalent to +5 as a modulus, since the equivalence classes are the same). To keep results predictable, this calculator requires the modulus to be a positive integer ≥ 1. Note: mod 1 is a special case where every integer is congruent to 0 — useful in proofs but trivial in computation. Most realistic uses have m ≥ 2.

What is Fermat's Little Theorem and how is it related?

Fermat's Little Theorem says: if p is a prime and a is any integer not divisible by p, then a^(p-1) ≡ 1 (mod p). This is the foundation of many things: (1) Primality testing — if you find any a with gcd(a, n) = 1 but a^(n-1) ≢ 1 mod n, then n is definitely composite. Miller-Rabin is a refined version of this test. (2) RSA key generation — the theorem is what makes RSA decryption work; the math relies on a^(φ(n)) ≡ 1 mod n, which generalizes Fermat's theorem via Euler's theorem to non-prime n. (3) Discrete logarithm cryptography — many protocols rely on exponents reducing modulo p-1 when the base is in a multiplicative group mod p. Try it: 2^6 mod 7 = 64 mod 7 = 1 (since 7 is prime and gcd(2,7)=1).

Can this calculator handle very large numbers used in cryptography?

Yes for normal-sized inputs (up to JavaScript's safe integer limit, 2^53 ≈ 9 × 10^15), but not for full cryptographic key sizes (2048+ bits ≈ 600+ decimal digits). The calculator runs in your browser using regular JavaScript numbers, which lose precision above 2^53. For real cryptographic computations, libraries use arbitrary-precision integers via BigInt (built into modern browsers) — open the browser console and try (3n ** 5n) % 7n for BigInt arithmetic. For day-to-day modular arithmetic — number theory homework, hash function analysis, calendar calculations, small-key demonstrations of RSA — this calculator's precision is more than enough. For actual encryption, use a vetted library like OpenSSL or libsodium, never roll your own.