Congruence Modulo n

Two integers are congruent modulo n when their difference is a multiple of n. The definition and its three equivalent forms, the proof that congruence is an equivalence relation with exactly n classes, the rules for adding, multiplying and raising congruences to powers, when a common factor can be canceled, and applications to the calendar, to checking multiplication by digit sums, and to polynomials with no integer roots.

The first of January 2026 was a Thursday. The first of January 2027 is 365 days later, and

$$365 = 7 \cdot 52 + 1,$$

so the 365 days make 52 whole weeks and one day more, and that date is a Friday. What exactly is computed when we count "up to whole weeks", and which rules of ordinary arithmetic still hold when we do?

The weekday of a date depends only on the remainder when the number of days separating it from a known date is divided by 7. From 1 January 2026 to 1 January 2029 is 1,096 days, because 2028 is a leap year, and since $1096 = 7 \cdot 156 + 4$, that date is a Monday. The script for this article confirms these dates with Python's datetime module. Integers that differ by a multiple of $n$ are congruent modulo $n$, the name and notation Gauss gave the idea at the start of the Disquisitiones Arithmeticae (1801).

First we state the definition in three equivalent forms and prove that congruence is an equivalence relation with exactly $n$ classes. Then come the rules for adding, multiplying and raising congruences to powers, with three applications: a googol days, digit checks on multiplication, and polynomials with no integer roots. Finally we see that cancellation survives only in part.

This is the second article of Congruence and Modular Arithmetic and covers §2.1 of the course text (Hungerford, 2014). It assumes the previous article, on equivalence relations, and builds on the division algorithm and divisibility.

The definition

Definition. Let $n$ be a positive integer. Integers $a$ and $b$ are congruent modulo $n$, written

$$a \equiv b \pmod{n},$$

if $n$ divides $a - b$. The integer $n$ is the modulus. If $n \nmid (a - b)$, then $a$ and $b$ are incongruent modulo $n$, written $a \not\equiv b \pmod{n}$.

Some examples, each checked by computing the difference:

  • $47 \equiv 5 \pmod 7$, since $47 - 5 = 42 = 7 \cdot 6$;
  • $-16 \equiv 5 \pmod 7$, since $-16 - 5 = -21 = 7 \cdot (-3)$;
  • $1729 \equiv 1 \pmod{12}$, since $1729 - 1 = 1728 = 12 \cdot 144$;
  • $1729 \equiv 1001 \pmod 7$, since $1729 - 1001 = 728 = 7 \cdot 104$;
  • $47 \not\equiv 12 \pmod{11}$, since $47 - 12 = 35$ is not a multiple of 11.

Gauss defined congruence in his first article, for positive and negative integers alike. He introduced the sign $\equiv$ in his second, choosing it, he wrote, because of the strong analogy between equality and congruence. He noted that Legendre had used the ordinary equals sign for congruence, and declined to follow him to avoid ambiguity (Gauss, 1801, arts. 1 and 2). The analogy is the subject of this article. Congruences can be manipulated much as equations can, and the notation invites exactly the manipulations that are valid.

Three ways to say it

For a positive integer $n$ and integers $a$ and $b$, the following statements are equivalent.

  1. $a \equiv b \pmod{n}$, that is, $n \mid (a - b)$.
  2. $a = b + nk$ for some integer $k$.
  3. $a$ and $b$ leave the same remainder on division by $n$.

Statements 1 and 2 are the definition of divisibility rewritten: $n \mid (a - b)$ means $a - b = nk$ for some integer $k$. The equivalence of statements 1 and 3 is a proposition proved in the division algorithm, where the uniqueness of the remainder did the work. Statement 2 is the most useful in proofs, because it replaces a congruence by an equation. Statement 3 is the most useful for computing, and it has an immediate consequence.

Corollary. Every integer is congruent modulo $n$ to its remainder on division by $n$, which is exactly one of $0, 1, \ldots, n - 1$.

Proof. If $a = nq + r$ with $0 \le r < n$, then $a - r = nq$, so $a \equiv r \pmod n$. The remainder is unique by the division algorithm. $\blacksquare$

Two special cases are worth stating. An integer is congruent to 0 modulo $n$ exactly when it is a multiple of $n$, since $a - 0 = a$. And modulo 1, every integer is congruent to every other, since 1 divides everything. The modulus 1 is allowed but uninteresting, and later articles mostly take $n \ge 2$.

Congruence is an equivalence relation

The weekday count assumed that congruence, like "the same weekday", can be reversed and chained.

Theorem. For each positive integer $n$, congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$. That is, for all integers $a$, $b$ and $c$:

  1. $a \equiv a \pmod n$;
  2. if $a \equiv b \pmod n$, then $b \equiv a \pmod n$;
  3. if $a \equiv b \pmod n$ and $b \equiv c \pmod n$, then $a \equiv c \pmod n$.

The idea: the multiples of $n$ include 0, include the negative of each multiple, and include the sum of any two multiples.

Proof. (1) $a - a = 0 = n \cdot 0$. (2) If $a - b = nk$, then $b - a = n(-k)$. (3) If $a - b = nk$ and $b - c = nl$, then adding the two equations, $$a - c = (a - b) + (b - c) = nk + nl = n(k + l). \qquad \blacksquare$$

There is a second proof that needs no computation at all. By the equivalence of statements 1 and 3 above, $a \equiv b \pmod n$ means that $a$ and $b$ have the same value under the function "remainder on division by $n$". The previous article showed that "same value under a function" is always an equivalence relation. Each proof has its use. The first carries over to settings with no remainders, such as congruence modulo an ideal in a general ring (Congruence Modulo an Ideal and Quotient Rings). The second explains why the result had to be true.

Congruence classes

Since congruence is an equivalence relation, the general theory of the previous article applies. It supplies classes, a partition and a quotient set without further work.

Definition. The congruence class of $a$ modulo $n$ is

$$[a] = \{\, x \in \mathbb{Z} : x \equiv a \pmod{n} \,\} = \{\, a + nk : k \in \mathbb{Z} \,\}.$$

The second description, the set of all $a + nk$, is statement 2 above. It is often written $a + n\mathbb{Z}$, where $n\mathbb{Z}$ is the set of multiples of $n$. When several moduli are in play, the class is written $[a]_n$. Modulo 7,

$$[3] = \{\ldots, -18, -11, -4, 3, 10, 17, 24, \ldots\}, \qquad [5] = \{\ldots, -16, -9, -2, 5, 12, 19, 26, \ldots\}.$$

From the general theorem on equivalence classes, $[a] = [b]$ if and only if $a \equiv b \pmod n$, and two congruence classes are either equal or disjoint. For instance $[47] = [5] = [-16]$ modulo 7, because all three numbers are congruent to 5.

How many classes are there? The division algorithm suggests $n$, one per remainder, and that is right.

Theorem. Let $n$ be a positive integer. There are exactly $n$ congruence classes modulo $n$, namely

$$[0], [1], [2], \ldots, [n - 1],$$

and these $n$ classes are distinct.

The idea: every integer is congruent to its remainder, and two different remainders are too close together to differ by a multiple of $n$.

Proof. Every class is one of these: for any integer $a$, the corollary above gives $a \equiv r \pmod n$ for its remainder $r \in \{0, \ldots, n - 1\}$, so $[a] = [r]$.

The listed classes are distinct: let $0 \le s < t \le n - 1$. Then $0 < t - s < n$, and a positive integer smaller than $n$ is not a multiple of $n$. So $t \not\equiv s \pmod n$ and $[t] \neq [s]$. $\blacksquare$

The classes partition the integers into $n$ blocks. One way to see the partition is to wind the number line around a circle with $n$ positions, so that the integers in one class line up.

The integers from -7 to 27 wound around a circle of seven positions, one turn for every seven integers. Each ray is one congruence class modulo 7: follow the ray marked [3] through -4, 3, 10, 17 and 24, which differ by multiples of 7. Notice that every integer lies on exactly one ray, so the seven rays are the seven classes.
The integers from $-7$ to 27 wound around a circle of seven positions, one turn for every seven integers. Each ray is one congruence class modulo 7: follow the ray marked [3] through $-4$, 3, 10, 17 and 24, which differ by multiples of 7. Notice that every integer lies on exactly one ray, so the seven rays are the seven classes.

A set containing exactly one integer from each class is a complete system of residues modulo $n$. The remainders $0, 1, \ldots, n - 1$, the least nonnegative residues, are the standard choice. Gauss also used the residues of smallest absolute value (Gauss, 1801, art. 4):

  • for $n = 7$, they are $-3, -2, -1, 0, 1, 2, 3$;
  • for $n = 12$, they are $-5, \ldots, 5$ together with one of 6 and $-6$, which are equally small.

The smaller numbers can make hand computation easier: modulo 7, the integer 6 is easier to handle as $-1$.

Check your understanding. Can a complete system of residues modulo 7 consist of even numbers only?

It can: $0, 2, 4, 6, 8, 10, 12$ leave the remainders $0, 2, 4, 6, 1, 3, 5$, one in each class. Each class modulo 7 contains both even and odd integers ($3$ and $10$, for instance), so parity says nothing about a class.

Arithmetic with congruences

The analogy with equality extends to arithmetic: congruent numbers may be substituted for each other in sums and products. The division algorithm article showed this for remainders, and here it is in the language of congruences.

Theorem. Let $n$ be a positive integer. If $a \equiv b \pmod n$ and $c \equiv d \pmod n$, then

  1. $a + c \equiv b + d \pmod n$, and
  2. $ac \equiv bd \pmod n$.

Here is the idea: $a$ differs from $b$, and $c$ from $d$, by multiples of $n$. Multiplying out, every extra term carries a factor of $n$.

Proof. By hypothesis, $a = b + nk$ and $c = d + nl$ for some integers $k$ and $l$.

(1) Adding, $a + c = (b + d) + n(k + l)$, so $a + c \equiv b + d \pmod n$.

(2) Multiplying out,

$$ac = (b + nk)(d + nl) = bd + n(bl + dk + nkl),$$

so $ac - bd$ is $n$ times an integer, and $ac \equiv bd \pmod n$. $\blacksquare$

For example, $47 = 5 + 7 \cdot 6$ and $30 = 2 + 7 \cdot 4$, so with $k = 6$ and $l = 4$ the proof gives

$$47 \cdot 30 = 5 \cdot 2 + 7\,(5 \cdot 4 + 2 \cdot 6 + 7 \cdot 6 \cdot 4) = 10 + 7 \cdot 200 = 1410,$$

and indeed $1410 \equiv 10 \pmod 7$. Replacing 47 and 30 by the much smaller 5 and 2 did not change the product modulo 7. The theorem is Hungerford's Theorem 2.2 and is in Gauss's articles 6 to 8. The script for this article checks both parts for every modulus up to 12 and every choice of $a, b, c, d$ between $-15$ and $15$.

Repeated use of the theorem gives more:

  • Differences and multiples. Since $-1 \equiv -1$, multiplying gives $-c \equiv -d$, and adding to $a \equiv b$ gives $a - c \equiv b - d$. Any integer multiple satisfies $ka \equiv kb$.
  • Powers. If $a \equiv b \pmod n$, then $a^k \equiv b^k \pmod n$ for every positive integer $k$. By induction: the case $k = 1$ is the hypothesis, and if $a^k \equiv b^k$, multiplying by $a \equiv b$ gives $a^{k+1} \equiv b^{k+1}$.
  • Polynomials. If $f(x) = c_m x^m + \cdots + c_1 x + c_0$ has integer coefficients and $a \equiv b \pmod n$, then $f(a) \equiv f(b) \pmod n$. Each term $c_i a^i$ is congruent to $c_i b^i$ by the previous two rules, and the terms can be added. This is Gauss's article 9.

The practical meaning is that a computation modulo $n$ can replace any number by any congruent one, at any stage. Large numbers never need to be formed.

A googol days from Thursday

What day of the week will it be $10^{100}$ days after a Thursday? The number $10^{100}$ has 101 digits, but only its remainder modulo 7 matters. Since $10 \equiv 3 \pmod 7$, the rule for powers gives $10^{100} \equiv 3^{100} \pmod 7$. The powers of 3 modulo 7, each found from the previous one by multiplying by 3 and reducing, are

$$3, \; 2, \; 6, \; 4, \; 5, \; 1, \; 3, \; 2, \; 6, \; \ldots$$

Since $3^6 \equiv 1$, the pattern repeats with period 6. Dividing the exponent, $100 = 6 \cdot 16 + 4$, so

$$3^{100} = (3^6)^{16} \cdot 3^4 \equiv 1^{16} \cdot 81 \equiv 4 \pmod 7.$$

The day is four weekdays after Thursday, a Monday. The script confirms $10^{100} \equiv 4 \pmod 7$ both by Python's modular power function and by forming the full integer. That $3^6 \equiv 1 \pmod 7$, with exponent one less than the modulus, is no accident. It is an instance of Fermat's little theorem.

Check your understanding. The base 10 was replaced by its residue 3. Why not also reduce the exponent 100 modulo 7 and compute $3^2$?

That gives $3^2 = 9 \equiv 2$, a Saturday, but the true answer is 4, a Monday. The exponent is not a number being multiplied; it counts the factors. Changing 100 to 2 removes 98 factors of 3, and 98 is a multiple of 7, not of the period 6. Exponents may be reduced only modulo a period of the powers.

Checking multiplication by digit sums

The rule for polynomials has a classical use. A decimal numeral is a polynomial evaluated at 10.

Proposition. Let $m$ be a positive integer with decimal digits $d_k d_{k-1} \ldots d_1 d_0$, so that $m = d_k 10^k + \cdots + d_1 \cdot 10 + d_0$. Then

  1. $m \equiv d_k + d_{k-1} + \cdots + d_1 + d_0 \pmod 9$, and
  2. $m \equiv d_0 - d_1 + d_2 - \cdots + (-1)^k d_k \pmod{11}$.

Here is the idea: $10$ is congruent to 1 modulo 9 and to $-1$ modulo 11, so in the polynomial, 10 can be replaced by 1 or by $-1$.

Proof. The number $m$ is the value at $x = 10$ of the polynomial $f(x) = d_k x^k + \cdots + d_1 x + d_0$, which has integer coefficients. Since $10 \equiv 1 \pmod 9$, the rule for polynomials gives $m = f(10) \equiv f(1) \pmod 9$, and $f(1)$ is the sum of the digits. Since $10 \equiv -1 \pmod{11}$, it gives $m \equiv f(-1) \pmod{11}$. And $f(-1)$ is the alternating sum, starting with a plus sign at the units digit. $\blacksquare$

Gauss cites these rules for divisibility by 9 and 11 as consequences of the theorems in his first section (Gauss, 1801, art. 12). Their best-known use is to check a multiplication. If $xy = p$, then the residues must satisfy $x \cdot y \equiv p$ modulo 9 and modulo 11, and the residues come cheaply from the digits.

Take $31{,}415 \times 27{,}183 = 853{,}953{,}945$.

  • Modulo 9, the digit sums are 14, 21 and 51, so the residues are 5, 3 and 6, and $5 \cdot 3 = 15 \equiv 6$: consistent.
  • Modulo 11, the alternating sums are 10, $-9$ and 9, so the residues are 10, 2 and 9, and $10 \cdot 2 = 20 \equiv 9$: consistent again.

Now suppose two adjacent digits of the answer are swapped by mistake, giving $853{,}593{,}945$. Swapping digits does not change the digit sum, so the check modulo 9 still passes, and the error goes unnoticed. The alternating sum changes from 9 to 17, so the residue modulo 11 becomes 6 instead of 9, and the check modulo 11 catches the mistake. An answer that is off by a multiple of 9, such as $853{,}962{,}945$, also passes the check modulo 9 and fails the one modulo 11. A failed check proves that the multiplication is wrong. A passed check only makes an error less likely, since any answer congruent to the true one passes.

Check your understanding. Can a swap of two adjacent, different digits ever pass the check modulo 11?

It cannot. Adjacent digits enter the alternating sum with opposite signs, so swapping $d_i$ and $d_{i+1}$ changes the sum by $\pm 2(d_i - d_{i+1})$, a nonzero even number between $-18$ and $18$, never a multiple of 11. The script confirms it for all eight such swaps in $853{,}953{,}945$.

Polynomials with no integer roots

The same rule can prove that an equation has no solution, by showing that it has none modulo some $n$. Consider

$$f(x) = x^3 + 7x + 9.$$

Every integer $x$ is congruent modulo 2 to 0 or 1, so by the rule for polynomials $f(x)$ is congruent to $f(0) = 9$ or to $f(1) = 17$. Both are odd, so $f(x)$ is odd for every integer $x$, and in particular never 0. The equation $f(x) = 0$ has no integer solutions, and the argument needed two evaluations instead of an infinite search.

Gauss made the same point with an example of his own. He remarked that the method extends: if a polynomial equation with integer coefficients has no solutions modulo some $n$, it has none in integers (Gauss, 1801, arts. 10 and 11). The converse fails, and the method can only prove impossibility. Modulo 3, $f(0) = 9 \equiv 0$, so the test modulo 3 finds a solution and proves nothing, even though the equation has no integer solutions.

Cancellation

So far every rule for equations has carried over. One does not. Equations allow cancellation of a nonzero common factor: if $ca = cb$ and $c \neq 0$, then $a = b$. For congruences this fails. Modulo 18,

$$6 \cdot 5 = 30 \equiv 12 = 6 \cdot 2 \pmod{18},$$

but $5 \not\equiv 2 \pmod{18}$. The factor 6 is not congruent to 0, yet it cannot be canceled. The problem is that 6 shares a factor with the modulus. What cancellation does give is a congruence modulo a smaller number, and in the best case modulo $n$ itself.

Proposition. Let $n$ be a positive integer, $c$ an integer, and $d = \gcd(c, n)$. Then

$$ca \equiv cb \pmod n \quad \text{if and only if} \quad a \equiv b \pmod{n/d}.$$

In particular, if $\gcd(c, n) = 1$, then $ca \equiv cb \pmod n$ implies $a \equiv b \pmod n$.

Here is the idea: $n$ divides $c(a - b)$, and after the common part $d$ is divided out of $c$ and $n$, what remains of $c$ shares nothing with $n/d$, so $n/d$ must divide $a - b$.

Proof. Write $c = d c'$ and $n = d n'$, where $c'$ and $n'$ are integers. They are relatively prime: dividing Bezout's identity $d = cu + nv$ by $d$ gives $1 = c'u + n'v$.

Suppose $ca \equiv cb \pmod n$, so $c(a - b) = nk$ for some integer $k$. Dividing by $d$ gives $c'(a - b) = n'k$, so $n'$ divides $c'(a - b)$. Since $\gcd(n', c') = 1$, the cancellation theorem of the Euclidean algorithm article gives $n' \mid (a - b)$, that is, $a \equiv b \pmod{n'}$.

Conversely, if $a - b = n'm$, then $c(a - b) = d c' n' m = n (c' m)$, so $ca \equiv cb \pmod n$. $\blacksquare$

In the example, $d = \gcd(6, 18) = 6$, and $6 \cdot 5 \equiv 6 \cdot 2 \pmod{18}$ gives exactly $5 \equiv 2 \pmod 3$, which is true. When the common factor is relatively prime to the modulus, as with $7 \cdot 11 = 77 \equiv 5$ and $7 \cdot 29 = 203 \equiv 5$ modulo 18, cancellation is allowed, and indeed $11 \equiv 29 \pmod{18}$. The script checks the proposition for every $n$ and $c$ from 1 to 30 and every $a, b$ from 0 to 30.

Check your understanding. Suppose $91a \equiv 91b \pmod{1729}$. What can we conclude about $a$ and $b$?

Since $1729 = 91 \cdot 19$, we have $d = \gcd(91, 1729) = 91$ and $n/d = 19$, and the congruence holds exactly when $a \equiv b \pmod{19}$. For example, $a = 1$ and $b = 20$ satisfy it, and $a = 1$, $b = 2$ do not.

In the language of the next articles, the factors that can always be canceled are the units of the integers modulo $n$, and the obstruction is the existence of zero divisors.

Where it leads

  • The congruence classes modulo $n$, with addition and multiplication defined by representatives, form the integers modulo $n$ (The Integers Modulo n). The theorem on sums and products is exactly what makes those operations well defined.
  • Which factors can be canceled, and which linear congruences $ax \equiv b$ can be solved, is settled in Units and Zero Divisors in the Integers Modulo n.
  • Powers modulo a prime repeat with a period dividing $p - 1$, as the powers of 3 modulo 7 did (Fermat's Little Theorem). The RSA cryptosystem is built on this.
  • Simultaneous congruences to different moduli, such as finding a number that is 2 modulo 5 and 4 modulo 9, are the subject of the Chinese remainder theorem.

What we have learned

Congruence modulo $n$ is an equivalence relation with exactly $n$ classes, one for each remainder. Congruences can be added, multiplied and raised to powers like equations, so a computation may replace any number by a congruent one, which is how a googol days were counted in a few lines. Cancellation is the exception: a factor $c$ cancels modulo $n$ only when $\gcd(c, n) = 1$, and otherwise only modulo $n/d$.

The weekday counts treated each class as a single thing. Can the classes themselves be added and multiplied as numbers? That is the subject of the next article, The Integers Modulo n.

References

  • Gauss, C. F. (1801). Disquisitiones Arithmeticae, Section 1, articles 1 to 12. Leipzig: Gerhard Fleischer. The definition of congruence for positive and negative integers (art. 1); the notation $\equiv$, chosen for the analogy with equality, with the remark on Legendre's use of the equals sign (art. 2); least residues (art. 4); sums, products and powers of congruences (arts. 6 to 8); polynomials (art. 9); equations with no solutions modulo a number (arts. 10 and 11); the tests for divisibility by 9 and 11 (art. 12). record · 3 pages
  • Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), §2.1. Brooks/Cole, Cengage Learning. The course text: congruence is an equivalence relation (Theorem 2.1), respects sums and products (Theorem 2.2); two classes are equal exactly when their representatives are congruent and are otherwise disjoint (Theorem 2.3, Corollary 2.4), and the classes are exactly $[0], \ldots, [n - 1]$ (Corollary 2.5). record · 44 pages
  • Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), §1.2.3, Example 1.2.30 (congruence modulo $n$ as an equivalence relation). Free online at judsonbooks.org. record · 44 pages