What is modular arithmetic and congruence in discrete mathematics?
Modular arithmetic, often called clock arithmetic, is a system of arithmetic for integers where numbers wrap around upon reaching a certain value called the modulus. In US university computer science and discrete mathematics courses (such as Berkeley CS 70, MIT 6.042J, or standard curricula following Kenneth Rosen's Discrete Mathematics and Its Applications), modular arithmetic is the foundational language of algorithm analysis, number theory, hashing, and modern public-key cryptography.
Two integers a and b are defined to be congruent modulo n, written as a ≡ b (mod n), if their difference (a - b) is an integer multiple of the modulus n. Equivalently, a ≡ b (mod n) means that a and b leave the exact same remainder when divided by n. The Division Algorithm states that for any integer a and positive integer n, there exist unique integers q (the quotient) and r (the remainder) such that:
a = q × n + r, where 0 ≤ r < n
Here, r is the canonical remainder, denoted a mod n. For example, dividing 17 by 60 gives 17 = 0 × 60 + 17, so 17 mod 60 = 17.
The negative modulo trap: programming language % vs mathematical modulo
One of the most frequent sources of bugs in homework assignments and competitive programming is assuming that the remainder operator in languages like C, C++, Java, and JavaScript computes the true mathematical modulo.
In C, C++, Java, and JavaScript, the % operator is a remainder operator, not a modulo operator. It truncates towards zero. When dividing -17 by 5:
- Truncating division yields a quotient of
-3and a remainder of-2, because-17 = (-3) × 5 + (-2). - However, the mathematical Division Algorithm strictly requires
0 ≤ r < n. The remainder cannot be negative. - Rewriting
-17with a non-negative remainder gives-17 = (-4) × 5 + 3. - Therefore, in mathematics and discrete math courses,
-17 mod 5 = 3, not-2.
This calculator uses true mathematical modulo across all inputs: if a % n is negative, it automatically normalizes the remainder to ((a % n) + n) % n, guaranteeing a result in the range [0, n - 1].
The Extended Euclidean Algorithm: finding modular inverses and Bezout coefficients
In standard arithmetic, every non-zero real number a has a multiplicative inverse 1 / a such that a × (1 / a) = 1. In modular arithmetic modulo n, division is defined through the modular multiplicative inverse. An integer x is the modular inverse of a modulo n if:
a × x ≡ 1 (mod n)
This equivalence means that a × x - 1 is a multiple of n, so there exists an integer y such that:
a × x + n × y = 1
This equation is a special case of Bezout's identity, which states that for any integers a and n, there exist integers x and y (called Bezout coefficients) such that a × x + n × y = gcd(a, n).
A modular inverse exists if and only if gcd(a, n) = 1 (meaning a and n are relatively prime, or coprime). If gcd(a, n) > 1, no modular inverse can ever exist, because any linear combination a × x + n × y must be a multiple of gcd(a, n), which cannot equal 1.
Worked example: finding 17⁻¹ mod 43
Consider finding the modular inverse of a = 17 modulo n = 43:
- Start with Row 0:
r0 = 43, x0 = 0, y0 = 1 - Row 1:
r1 = 17, x1 = 1, y1 = 0 - Divide 43 by 17: quotient
q = 2, remainderr = 43 - 2 × 17 = 9. Updatex = 0 - 2 × 1 = -2, andy = 1 - 2 × 0 = 1. - Divide 17 by 9: quotient
q = 1, remainderr = 17 - 1 × 9 = 8. Updatex = 1 - 1 × (-2) = 3, andy = 0 - 1 × 1 = -1. - Divide 9 by 8: quotient
q = 1, remainderr = 9 - 1 × 8 = 1. Updatex = -2 - 1 × 3 = -5, andy = 1 - 1 × (-1) = 2. - Divide 8 by 1: quotient
q = 8, remainderr = 0. The algorithm terminates.
The last non-zero remainder is 1, confirming gcd(17, 43) = 1. Bezout's identity gives:(-5) × 17 + 2 × 43 = 1
Taking this equation modulo 43:(-5) × 17 ≡ 1 (mod 43)
To find the canonical positive inverse in [0, 42], reduce -5 modulo 43:-5 mod 43 = 38
Verifying: 17 × 38 = 646 = 15 × 43 + 1 ≡ 1 (mod 43). Thus, 17⁻¹ ≡ 38 (mod 43).
Modular exponentiation by repeated squaring (binary exponentiation)
Computing powers like 3¹³ mod 7 or cryptographic values like gᵃ mod p with 2048-bit numbers cannot be done by computing aᵇ as a massive integer and then taking the remainder. The number 3¹³ is small (1,594,323), but 3¹⁰⁰⁰ has 478 decimal digits, and cryptographic powers have thousands of bits, which would exhaust memory and CPU resources.
Instead, discrete mathematics uses modular exponentiation by repeated squaring (also known as binary exponentiation), which computes aᵇ mod n in O(log b) multiplications:
- Express the exponent b in binary. For example,
13 = 1101₂ = 8 + 4 + 1 = 2³ + 2² + 2⁰. - Compute repeated squarings of the base modulo n:
3¹ mod 7 = 33² mod 7 = 9 mod 7 = 23⁴ mod 7 = 2² mod 7 = 43⁸ mod 7 = 4² mod 7 = 16 mod 7 = 2
- Multiply the running accumulator by the powers corresponding to bits that are 1:
- Bit 0 is 1:
accumulator = (1 × 3) mod 7 = 3 - Bit 1 is 0: skip multiplication, accumulator stays 3
- Bit 2 is 1:
accumulator = (3 × 4) mod 7 = 12 mod 7 = 5 - Bit 3 is 1:
accumulator = (5 × 2) mod 7 = 10 mod 7 = 3
- Bit 0 is 1:
Final result: 3¹³ mod 7 = 3. We computed the power using only 3 squarings and 3 multiplications, rather than 12 successive multiplications.
Applications in computer science and public-key cryptography
Modular arithmetic is the cornerstone of computer security:
- RSA Cryptography: Key generation chooses two large primes p and q, sets
n = p × q, and selects a public exponent e coprime to(p - 1)(q - 1). The private key d is computed as the modular inversed = e⁻¹ mod ((p - 1)(q - 1))using the Extended Euclidean Algorithm. Encryption computesc = mᵉ mod n, and decryption computesm = cᵈ mod nvia repeated squaring. - Diffie-Hellman Key Exchange: Relies on modular exponentiation
gᵃ mod pand the hardness of the discrete logarithm problem. - Hashing and Checksums: Hash tables and cyclic redundancy checks use prime moduli to distribute keys evenly and minimize collisions.