Congruence Relations

Formalizing Congruence

When we use the modulo operator, we're really talking about a mathematical concept called congruence. Instead of just saying that two numbers have the same remainder, we can express this relationship with a specific notation. This formalizes the idea and gives us a powerful way to reason about numbers.

In mathematics, modular arithmetic refers to the arithmetic of integers that wraps around when a certain value is reached, called the modulus.

We say that two integers, $a$ and $b$ , are "congruent modulo $n$ " if their difference, $a - b$ , is an integer multiple of $n$ . This is the formal definition.

a \equiv b \pmod{n}

For example, $17 \equiv 5 \pmod{12}$ because $17 - 5 = 12$ , and 12 is a multiple of 12 (specifically, $12 \times 1$ ).

This definition works for all integers, including negative ones. For instance, $3 \equiv -7 \pmod{5}$ because $3 - (-7) = 10$ , and 10 is a multiple of 5.

A Special Relationship

This congruence relationship isn't just a casual connection; it's a formal mathematical structure known as an equivalence relation. For a relationship to be an equivalence relation, it must have three specific properties: it must be reflexive, symmetric, and transitive.

Property	Meaning	Example (mod 5)
Reflexive	Any integer is congruent to itself.	$7 \equiv 7 \pmod{5}$
Symmetric	If $a$ is congruent to $b$ , then $b$ is congruent to $a$ .	If $12 \equiv 2 \pmod{5}$ , then $2 \equiv 12 \pmod{5}$ .
Transitive	If $a \equiv b$ and $b \equiv c$ , then $a \equiv c$ .	$13 \equiv 8$ and $8 \equiv 3$ , so $13 \equiv 3 \pmod{5}$ .

These properties are what allow us to substitute one number for another within modular arithmetic. If two numbers are congruent modulo $n$ , they are interchangeable for calculations involving addition, subtraction, and multiplication modulo $n$ .

Residue Classes

Because congruence is an equivalence relation, it partitions all integers into a set of distinct groups, called residue classes or congruence classes. Each class contains all the integers that have the same remainder when divided by the modulus $n$ .

For any modulus $n$ , there are exactly $n$ residue classes, corresponding to the possible remainders: $0, 1, 2, \dots, n-1$ .

For modulus 4, the residue classes are:

Class 0: {..., -8, -4, 0, 4, 8, ...} (all integers of the form $4k$)
Class 1: {..., -7, -3, 1, 5, 9, ...} (all integers of the form $4k+1$)
Class 2: {..., -6, -2, 2, 6, 10, ...} (all integers of the form $4k+2$)
Class 3: {..., -5, -1, 3, 7, 11, ...} (all integers of the form $4k+3$)

Every integer belongs to exactly one of these classes. This collection of classes forms a new number system, a foundational concept in abstract algebra known as a ring.

A Programming Caveat

A crucial point of difference arises between the mathematical definition of modulo and its implementation in many programming languages, like C++, when dealing with negative numbers.

Mathematically, the remainder is always non-negative. For example, $-8 \pmod 5$ should be 2, because $-8 = 5 \times (-2) + 2$ . The remainder must be in the set ${0, 1, 2, 3, 4}$ .

However, C++ (and many other languages) implement the % operator as a remainder operation, not a true mathematical modulo. The sign of the result matches the sign of the dividend.

#include <iostream>

int main() {
    // Mathematical modulo: -8 mod 5 = 2
    // C++ remainder: -8 % 5 = -3

    std::cout << "-8 % 5 = " << (-8 % 5) << std::endl;

    // Mathematical modulo: 8 mod -5 = 3
    // C++ remainder: 8 % -5 = 3 (This one might be surprising!)

    std::cout << "8 % -5 = " << (8 % -5) << std::endl;

    return 0;
}

This difference can lead to bugs if you're not careful. When implementing algorithms that rely on mathematical congruence (like in cryptography or number theory), you often need the result to be non-negative. A common way to ensure a positive result for a % n is to use the formula (a % n + n) % n.

#include <iostream>

// A function for true mathematical modulo
int mod(int a, int n) {
    return (a % n + n) % n;
}

int main() {
    // Standard C++ operator
    std::cout << "-8 % 5 = " << (-8 % 5) << std::endl;

    // Correct mathematical result
    std::cout << "mod(-8, 5) = " << mod(-8, 5) << std::endl;

    return 0;
}

This trick works because if a % n is negative (e.g., -3), adding n (e.g., 5) makes it positive (2) before the final modulo operation, which then has no effect. If a % n is already positive, adding n and taking the modulo again simply returns the original result. This ensures your code aligns with the formal mathematical definition.

Quiz Questions 1/6

What is the formal definition of two integers, 'a' and 'b', being "congruent modulo n"?

Quiz Questions 2/6

Which of the following statements of congruence is true?

With these formal rules, we can build a consistent system of arithmetic that is essential for many areas of computer science and mathematics.

Mastering Modular Arithmetic for Algorithms