Mathematics · Number Theory
Modular Arithmetic Calculator
Computes the remainder, modular inverse, modular exponentiation, and related properties for two integers under a given modulus.
Calculator
Formula
a is the integer (dividend), m is the modulus (a positive integer), and r is the remainder satisfying 0 ≤ r < m. For modular inverse: x such that a·x ≡ 1 (mod m), computed via the Extended Euclidean Algorithm when gcd(a, m) = 1. For modular exponentiation: a^b mod m, computed efficiently using repeated squaring.
Source: Hardy, G. H. & Wright, E. M. — An Introduction to the Theory of Numbers, Oxford University Press.
How it works
Modular arithmetic, sometimes called "clock arithmetic," works by wrapping numbers around once they reach a certain value — the modulus. Given integers a and m (m > 0), the expression a mod m yields the unique non-negative remainder r satisfying a = q·m + r where 0 ≤ r < m and q is the integer quotient. This system defines equivalence classes called residues, and two numbers are congruent modulo m if they share the same residue.
The modular inverse of a modulo m is the integer x such that a·x ≡ 1 (mod m). It exists if and only if gcd(a, m) = 1 (i.e., a and m are coprime). This calculator uses the Extended Euclidean Algorithm to find it efficiently in O(log m) steps. Modular exponentiation computes ab mod m using the repeated squaring method (also called fast exponentiation or binary exponentiation), which runs in O(log b) multiplications — crucial for handling the enormous exponents seen in RSA encryption, where b can be hundreds of digits long. GCD(a, m) is computed via the standard Euclidean algorithm and indicates whether a modular inverse exists.
These operations are foundational across many fields: RSA and elliptic-curve cryptography depend on modular inverses and exponentiation; hash functions and checksums use modular reduction; calendar calculations use modular arithmetic to determine days of the week; and computer architecture uses it in memory addressing, cyclic buffers, and CRC error detection. Number theorists use modular arithmetic to prove theorems about primes, Fermat's Little Theorem, Euler's totient function, and the Chinese Remainder Theorem.
Worked example
Example: Compute all outputs for a = 17, b = 5, m = 13.
Step 1 — Remainder (17 mod 13): Divide 17 by 13: 17 = 1 × 13 + 4. So the remainder is 4, meaning 17 ≡ 4 (mod 13).
Step 2 — Quotient: ⌊17 / 13⌋ = 1.
Step 3 — GCD(17, 13): Apply the Euclidean algorithm: gcd(17, 13) → gcd(13, 4) → gcd(4, 1) → gcd(1, 0) = 1. Since GCD = 1, the modular inverse exists.
Step 4 — Modular Inverse of 17 mod 13: Since 17 ≡ 4 (mod 13), we need 4·x ≡ 1 (mod 13). Using the Extended Euclidean Algorithm: 13 = 3·4 + 1 → 1 = 13 − 3·4. So x = −3 ≡ 10 (mod 13). Check: 4 × 10 = 40 = 3 × 13 + 1 ✓. The modular inverse is 10.
Step 5 — Modular Exponentiation (17^5 mod 13): Since 17 ≡ 4 (mod 13), compute 4^5 mod 13 using repeated squaring: 4^1 = 4; 4^2 = 16 ≡ 3 (mod 13); 4^4 = 3^2 = 9 (mod 13); 4^5 = 4^4 × 4^1 = 9 × 4 = 36 ≡ 10 (mod 13). Result: 10.
Limitations & notes
This calculator uses JavaScript's native 64-bit floating-point integers, so results are exact for integers up to 253 − 1 (approximately 9 × 1015). For cryptographic applications with very large numbers (e.g., 2048-bit RSA keys), a big-integer library is required. The modular inverse is displayed as NaN when gcd(a, m) ≠ 1, since the inverse does not exist in that case — this is mathematically correct, not an error. The exponent b must be a non-negative integer; negative exponents (equivalent to modular inverse of the positive power) are not supported. The modulus m must be a positive integer greater than zero. Decimal inputs are automatically truncated to their integer parts.
Frequently asked questions
What is modular arithmetic used for in real life?
Modular arithmetic underlies RSA and elliptic-curve cryptography (securing internet communications), checksums and CRC error detection, hash table indexing in software, and even everyday calendar calculations like finding what day of the week a date falls on. It is one of the most practically applied areas of pure mathematics.
When does a modular inverse not exist?
The modular inverse of a modulo m exists if and only if gcd(a, m) = 1 — that is, a and m must be coprime (share no common factor other than 1). For example, 4 has no inverse modulo 6 because gcd(4, 6) = 2 ≠ 1. If the modulus m is a prime number, then every non-zero residue has an inverse, which is why prime moduli are preferred in cryptography.
What is the difference between remainder and modulo for negative numbers?
In mathematics, a mod m is always non-negative (0 ≤ r < m). In many programming languages, the % operator returns a remainder that can be negative for negative inputs (e.g., −7 % 3 = −1 in C/Java). This calculator always returns the mathematical modulo, adding m when necessary to ensure the result is non-negative (e.g., −7 mod 3 = 2).
How does the Extended Euclidean Algorithm compute the modular inverse?
The Extended Euclidean Algorithm finds integers x and y such that a·x + m·y = gcd(a, m). When gcd(a, m) = 1, this gives a·x + m·y = 1, which means a·x ≡ 1 (mod m). The x value, adjusted to be non-negative, is the modular inverse. The algorithm runs in O(log(min(a, m))) steps, making it highly efficient.
Why is fast modular exponentiation important in cryptography?
RSA encryption requires computing values like a^b mod m where b can be a 2048-bit number — far too large for naive repeated multiplication. The repeated squaring (binary exponentiation) method reduces the number of multiplications from b to just O(log b), making computation feasible. Without it, RSA decryption on even a 512-bit key would be computationally impossible in practice.
Last updated: 2025-01-15 · Formula verified against primary sources.