Calculator
MathModular Arithmetic Calculator
Free modular arithmetic calculator: modulo, modular inverse, modular exponentiation, modular division and a linear congruence solver via extended Euclidean GCD.
Have feedback? Report bugs, suggest features, or share your thoughts — we read them allCalculate 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
Frequently Asked Questions
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.
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.
Modular division a / b mod m means solving the linear congruence b · x ≡ a (mod m) for x. Unlike ordinary division you cannot just divide; instead you multiply by the modular inverse of b: x = a · b⁻¹ mod m. Step by step: (1) Check coprimality — compute gcd(b, m) with the Extended Euclidean Algorithm. If gcd(b, m) = 1, b is invertible and the congruence has a unique solution mod m. (2) If gcd(b, m) does not divide a, there is NO solution; this calculator reports that instead of returning a wrong number. (3) Find b⁻¹ mod m from the Extended Euclidean (Bezout) coefficients. (4) Compute x = (a × b⁻¹) mod m. (5) Verify: (b × x) mod m should equal a mod m. Example: solve 4x ≡ 3 (mod 7). gcd(4, 7) = 1, 4⁻¹ ≡ 2 (mod 7), so x = 3 × 2 = 6, and 4 × 6 = 24 ≡ 3 (mod 7). Select "Modular Division (a / b mod m)" above to run this with full steps and a coprimality pass/fail verdict.
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.
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.
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.
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.
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).
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.
MATH CALCULATORS32
WUTOOLS