Last updated: 2026-06-05

Modular arithmetic is the branch of number theory that studies integers reduced by a fixed divisor called the modulus. Two integers are congruent modulo n if they differ by a multiple of n, written a ≡ b (mod n). This calculator evaluates three core operations: the remainder after division, fast modular exponentiation, and the modular inverse.

The modulo operation

For a positive modulus n, the mathematical modulo a mod n is defined as the unique integer r in [0, n − 1] satisfying:

a = q × n + r

where q = ⌊a / n⌋ is the floor quotient and r is the remainder. This definition always produces a non-negative result, unlike the truncated remainder used in many programming languages.

Worked example. For a = 17 and n = 5:

q = ⌊17 / 5⌋ = 3
r = 17 − 3 × 5 = 2

So 17 mod 5 = 2. This matches clock arithmetic: counting 17 steps on a five-position dial lands on position 2.

Negative values. For a = −7 and n = 5:

q = ⌊−7 / 5⌋ = −2
r = −7 − (−2) × 5 = 3

So −7 mod 5 = 3, not −2. The mathematical definition keeps r non-negative; the programming % operator in languages such as C and JavaScript gives −2 instead, because those languages use truncated division rather than floor division.

Modular exponentiation

Computing a^b mod n directly — first computing a^b and then reducing — is impractical for large exponents because a^b grows exponentially. Fast modular exponentiation (square-and-multiply) avoids this by reducing modulo n at each step.

The algorithm decomposes the exponent in binary. Starting with result = 1:

• At each bit of b from least significant to most significant, square the running base modulo n.
• When the bit is 1, multiply result by the current base power, reducing modulo n.

This requires at most 2 log₂(b) multiplications rather than b − 1, and every intermediate value stays in [0, n − 1].

Worked example. For a = 17, b = 3, n = 5:

17 ≡ 2 (mod 5)
17^2 ≡ 4 (mod 5)
17^3 = 17^2 × 17 ≡ 4 × 2 = 8 ≡ 3 (mod 5)

So 17^3 mod 5 = 3. Direct check: 17^3 = 4913 = 982 × 5 + 3.

Modular inverse

The modular inverse of a modulo n is an integer x satisfying:

a × x ≡ 1 (mod n)

This inverse exists if and only if gcd(a, n) = 1 — that is, a and n are coprime. When n is a prime, every integer from 1 to n − 1 has an inverse. When n is composite, any a sharing a factor with n has no inverse.

The extended Euclidean algorithm computes the inverse when it exists. It extends the standard Euclidean GCD computation to track linear combinations, yielding integers s and t such that:

a × s + n × t = gcd(a, n)

When gcd(a, n) = 1, s is the modular inverse of a mod n.

Worked example. For a = 3, n = 5:

Apply the extended Euclidean algorithm:

• 5 = 1 × 3 + 2
• 3 = 1 × 2 + 1

Back-substituting: 1 = 3 − 1 × 2 = 3 − 1 × (5 − 1 × 3) = 2 × 3 − 1 × 5

So 3 × 2 ≡ 1 (mod 5), meaning 3⁻¹ ≡ 2 (mod 5).

Verification: 3 × 2 = 6 = 1 × 5 + 1. ✓

Practical applications

Modular arithmetic appears throughout mathematics and computing:

• Public-key cryptography. RSA encryption raises a message to a large exponent modulo a product of two primes. Decryption uses the modular inverse of the encryption exponent.
• Checksums. The ISBN-13, IBAN, and credit-card Luhn algorithm all use modular arithmetic to detect transcription errors.
• Calendar arithmetic. The day of the week after d days is computed modulo 7; Easter's date follows cycles that reduce to congruences.
• Hash tables. A key is mapped to a bucket index using key mod table_size.
• Cyclic data structures. Ring buffers and circular arrays advance a read/write pointer using index mod capacity.

Floor quotient and Euclidean identity

For every pair (a, n) with n ≥ 1, the floor quotient q = ⌊a / n⌋ and the remainder r = a mod n satisfy the Euclidean identity:

a = q × n + r, 0 ≤ r < n

This calculator displays both r and q, so the identity can be verified directly for any inputs.