math.wiki
Logic, proof and discrete math › Introductory number theory › Modular arithmetic › Congruence modulo n and its arithmetic
Open on the map
Discrete Mathematics and Proof

Congruence modulo n and its arithmetic

A clock forgets how many times its hand has gone around, and a weekday forgets how many weeks have passed. Can we do arithmetic that keeps only the remainder, and trust every step of it?

You need
The division algorithmDiscrete Mathematics and Proof
Unlocks
Powers modulo nDiscrete Mathematics and ProofRelations, equivalence classes and partitionsDiscrete Mathematics and ProofWhere the divisibility tests come fromDiscrete Mathematics and ProofModular inverses and linear congruencesDiscrete Mathematics and Proof+1 more
Where you are 7 in Modular arithmetic
Logic, proof and discrete math6
Introductory number theory8
Modular arithmetic7
Congruence modulo n and its arithmetic
Powers modulo nWhere the divisibility tests come fromFermat's little theoremModular inverses and linear congruences▾ Show all 7 (2 more)

Why this exists

Ask what day of the week it will be 260 days from now, or what the last two digits of 3{,}147 \cdot 5{,}286 are, and most of each number is irrelevant. Only a remainder matters: on division by 7 for the weekday, by 100 for the digits. Congruence is the language for “equal as far as the remainder can tell.” Its value is that it behaves like equality under addition, subtraction and multiplication, so a large number may be swapped for a small one partway through a computation without changing the remainder at the end. This lesson sets up that language on the first day and proves the arithmetic rules on the second, together with the one place where the analogy with equality breaks: division.

Definition

Day 1: congruence and remainders

Fix a positive integer n, the modulus. For integers a and b,

a \equiv b \pmod{n} \quad \text{means} \quad n \mid (a - b).

It is read “a is congruent to b modulo n.” When n \nmid (a - b) we write a \not\equiv b \pmod{n}. Since n \mid (a - b) means a - b = kn for some integer k (Divisibility as a relation), an equivalent form is

\begin{aligned} a \equiv b \pmod{n} &\iff a = b + kn \\ &\phantom{\iff} \text{ for some integer } k. \end{aligned}

So the integers congruent to b are b and everything reached from it by whole steps of n, forward or backward. The examples use n \ge 2; with n = 1 every pair of integers is congruent, since 1 divides everything.

The second idea is the remainder. By the division algorithm (The division algorithm), for every integer a there are unique integers q and r with

a = qn + r, \qquad 0 \le r < n.

The remainder r is written a \bmod n. Here \bmod is an operation that produces a number, 23 \bmod 7 = 2, while \pmod{n} in a congruence only names the modulus. The condition 0 \le r holds for negative a as well: -23 = (-4) \cdot 7 + 5, so -23 \bmod 7 = 5, not -2.

Day 2: arithmetic modulo n

On day 2 the definition stays the same; what is new is permission. Theorem 3 below says that congruences modulo the same n may be added, subtracted and multiplied like equations. Working modulo n means doing a computation in which any number may be replaced, at any stage, by another number congruent to it, usually its remainder or a small negative number. A remainder taken at the end of such a computation is the remainder of the original expression.

Intuition

Picture the integers on a number line and mark everything congruent to 5 modulo 7. Starting at 5 and stepping by 7 each way gives \dots, -23, -16, -9, -2, 5, 12, 19, 26, \dots, a row of evenly spaced points. Any two of them differ by a multiple of 7, which is the definition.

−23 −16 −9 −2 5 12 19 26 0 +7 +7 +7 +7 +7 +7 +7
Figure 1The integers congruent to 5 modulo 7. They sit 7 apart in both directions, so -23 belongs with 5.

Now wind the number line around a circle whose circumference is 7. A step of 7 goes once around and returns to the same spot, so the whole row lands on one point, the point for remainder 5. Each of the 7 points of the circle collects one such row, and the label of a point is the remainder of every integer that lands there. Two integers are congruent exactly when they land on the same point. A clock face is the case n = 12 (Morning and afternoon on a twelve hour clock reads time on it; here only the winding matters).

0 1 2 3 4 6
\dots, -9, -2, 5, 12, 19, \dots
Figure 2Wind the number line around a circle of circumference 7. Every integer lands on its remainder; the point for 5 is labeled with the integers that land on it.

Arithmetic on the circle is arithmetic of positions. Adding 3 moves three places clockwise from wherever you stand, and it does not matter which integer in the row you started from. That is the content of the addition rule; the multiplication rule says the same holds for repeated addition.

Results

Theorem 1 (congruence is sameness of remainder). Let n be a positive integer. For all integers a and b, a \equiv b \pmod{n} if and only if a \bmod n = b \bmod n. In particular every integer is congruent modulo n to exactly one of 0, 1, \dots, n - 1, namely its remainder.

Theorem 2 (equivalence relation). For all integers a, b, c:

  • a \equiv a \pmod{n} (reflexive);
  • if a \equiv b \pmod{n} then b \equiv a \pmod{n} (symmetric);
  • if a \equiv b \pmod{n} and b \equiv c \pmod{n} then a \equiv c \pmod{n} (transitive).

Theorem 3 (arithmetic rules). If a \equiv b \pmod{n} and c \equiv d \pmod{n}, then

\begin{aligned} a + c &\equiv b + d \pmod{n}, \\ a - c &\equiv b - d \pmod{n}, \\ ac &\equiv bd \pmod{n}. \end{aligned}

Corollary 4 (replacement). In any expression built from integers by addition, subtraction and multiplication, replacing one or more of the integers by numbers congruent to them modulo n gives a result congruent to the original modulo n. In particular, if a \equiv b \pmod{n} then a^k \equiv b^k \pmod{n} for every positive integer k.

Why it is true

Proof of Theorem 1. Write a = qn + r and b = q'n + r' with 0 \le r, r' < n, by the division algorithm. Then

a - b = (q - q')n + (r - r').

If r = r', this reads a - b = (q - q')n, so n \mid (a - b). Conversely, suppose n \mid (a - b). Then r - r' = (a - b) - (q - q')n is a difference of two multiples of n, so it is a multiple of n. But 0 \le r, r' < n gives -n < r - r' < n, and the only multiple of n strictly between -n and n is 0. So r = r'. For the last sentence: a = qn + r gives a - r = qn, so a \equiv r, and by what was just proved no other number among 0, \dots, n - 1 can be congruent to a, because each of them is its own remainder. \square

Proof of Theorem 2. Reflexive: a - a = 0 = 0 \cdot n. Symmetric: if a - b = kn then b - a = (-k)n. Transitive: if a - b = kn and b - c = jn, then adding, a - c = (k + j)n. Each conclusion is n times an integer. \square

A relation with these three properties is an equivalence relation (Relations and their properties: reflexive, symmetric, antisymmetric, transitive). The groups it sorts the integers into, the rows of the circle picture, are the subject of Relations, equivalence classes and partitions.

Proof of Theorem 3. Write a = b + kn and c = d + jn for integers k and j. Adding and subtracting,

\begin{aligned} (a + c) - (b + d) &= (k + j)n, \\ (a - c) - (b - d) &= (k - j)n. \end{aligned}

For the product, add and subtract bc so that each piece contains one known difference:

\begin{aligned} ac - bd &= (ac - bc) + (bc - bd) \\ &= (a - b)c + b(c - d) \\ &= knc + bjn = (kc + bj)n. \end{aligned}

The second line uses the distributive property. Each difference is n times an integer. \square

Proof of Corollary 4. An expression is evaluated one operation at a time. At an operation whose two inputs have each been replaced by congruent numbers (an input left alone is congruent to itself, by reflexivity), Theorem 3 says the output is congruent to the original output. So the congruence passes up through every operation to the final value. For powers, a^k is the product of k copies of a; exercise 25 turns this into an induction. \square

Worked examples

Examples 1 to 3 go with day 1, examples 4 to 7 with day 2.

Example 1

Testing a congruence two ways

Decide whether 59 \equiv 17 \pmod{6} and whether 59 \equiv 17 \pmod{8}. Confirm each answer with remainders.

Solution

By the definition, look at the difference 59 - 17 = 42. Since 42 = 7 \cdot 6, 6 \mid 42 and 59 \equiv 17 \pmod{6}. Since 42 = 5 \cdot 8 + 2, 8 \nmid 42 and 59 \not\equiv 17 \pmod{8}.

Theorem 1 says the remainders must agree in the first case and differ in the second. Modulo 6: 59 = 9 \cdot 6 + 5 and 17 = 2 \cdot 6 + 5, both remainder 5. Modulo 8: 59 = 7 \cdot 8 + 3 and 17 = 2 \cdot 8 + 1, remainders 3 and 1. Both tests agree, as they must.

Example 2

A negative number

Show that -23 \equiv 5 \pmod{7}, find -23 \bmod 7, and list every integer x with -30 \le x \le 30 and x \equiv 5 \pmod{7}.

Solution

The difference is -23 - 5 = -28 = (-4) \cdot 7, so 7 \mid (-23 - 5) and -23 \equiv 5 \pmod{7}.

For the remainder, the division algorithm asks for -23 = 7q + r with 0 \le r < 7. The multiple of 7 just at or below -23 is -28, so q = -4 and r = -23 - (-28) = 5. Thus -23 \bmod 7 = 5. It is also true that -23 \equiv -2 \pmod{7}, since -23 - (-2) = -21; a congruence may use any member of the row, while the remainder is the one member in \{0, \dots, 6\}.

By the equivalent form of the definition, x \equiv 5 \pmod{7} means x = 5 + 7k. The condition -30 \le 5 + 7k \le 30 gives -5 \le k \le 3 after dividing -35 \le 7k \le 25 by 7 and keeping integers. So

x \in \{-30, -23, -16, -9, -2, 5, 12, 19, 26\}.
Example 3

A smaller modulus inherits the congruence

Prove that if m and n are positive integers with m \mid n, and a \equiv b \pmod{n}, then a \equiv b \pmod{m}. Then show with an example that the converse fails.

Solution

Proof. Since a \equiv b \pmod{n}, a - b = kn for some integer k. Since m \mid n, n = tm for some integer t. Substituting, a - b = k(tm) = (kt)m by the associative property, and kt is an integer, so m \mid (a - b). That is, a \equiv b \pmod{m}. \square

The converse would say: if m \mid n and a \equiv b \pmod{m}, then a \equiv b \pmod{n}. Take m = 4, n = 12, a = 5, b = 1. Then 5 - 1 = 4, so 5 \equiv 1 \pmod{4}, but 12 \nmid 4, so 5 \not\equiv 1 \pmod{12}. On a clock face: two times congruent modulo 12 hours are also congruent modulo 4, but not the other way round.

Example 4

Reducing before multiplying

Find the remainder when 803 \cdot 1{,}217 - 395 is divided by 8.

Solution

Reduce each number first. Since 800 = 100 \cdot 8, 803 \equiv 3 \pmod{8}. Since 1{,}216 = 152 \cdot 8, 1{,}217 \equiv 1 \pmod{8}. Since 392 = 49 \cdot 8, 395 \equiv 3 \pmod{8}. By Corollary 4 these replacements may all be made at once:

\begin{aligned} 803 \cdot 1{,}217 - 395 &\equiv 3 \cdot 1 - 3 \\ &= 0 \pmod{8}. \end{aligned}

The remainder is 0: the number is a multiple of 8. Check by direct computation: 803 \cdot 1{,}217 = 977{,}251, and subtracting 395 leaves 976{,}856 = 8 \cdot 122{,}107.

Example 5

Last two digits

Find the last two digits of 3{,}147 \cdot 5{,}286.

Solution

The last two digits of a positive integer are its remainder on division by 100: 3{,}147 = 31 \cdot 100 + 47, and in general the hundreds and above form a multiple of 100. So the question asks for 3{,}147 \cdot 5{,}286 \bmod 100. Replace each factor by its last two digits, which is allowed by the multiplication rule:

\begin{aligned} 3{,}147 \cdot 5{,}286 &\equiv 47 \cdot 86 \\ &= 4{,}042 \equiv 42 \pmod{100}. \end{aligned}

The last two digits are 42. A second route shows how negative numbers keep the work small: 86 \equiv -14 \pmod{100}, so the product is congruent to 47 \cdot (-14) = -658, and -658 + 7 \cdot 100 = 42. Direct check: 3{,}147 \cdot 5{,}286 = 16{,}635{,}042.

Example 6

Weekdays and a 24-hour clock

Number the weekdays Sunday 0, Monday 1, through Saturday 6. (a) Bheki signs a lease on a Wednesday that ends 260 days later. On what weekday does it end? (b) What weekday was 100 days before that Wednesday? (c) Jovanka ships a package that leaves at 21:00 on a 24-hour clock and is in transit for 53 hours. At what time does it arrive, and how many days later?

Solution

(a) Seven days later is the same weekday, so weekdays are arithmetic modulo 7. Wednesday is 3, and 260 = 37 \cdot 7 + 1, so 260 \equiv 1 \pmod{7} and

3 + 260 \equiv 3 + 1 = 4 \pmod{7}.

Day 4 is Thursday.

(b) Going back 100 days is adding -100. Since -100 + 105 = 5, -100 \equiv 5 \pmod{7}, so 3 - 100 \equiv 3 + 5 = 8 \equiv 1 \pmod{7}: a Monday. Check: 98 = 14 \cdot 7 days before is a Wednesday, and two days before that is Monday.

(c) Hours on a 24-hour clock are arithmetic modulo 24. The arrival time is 21 + 53 = 74, and 74 = 3 \cdot 24 + 2. So the package arrives at 02:00, and the quotient 3 counts the midnights passed: three days after it left.

Example 7

A remainder no value can reach

Prove that for every integer m, the number m^2 + m + 1 is not divisible by 5.

Solution

Proof. “Divisible by 5” means congruent to 0 modulo 5. By Theorem 1, m is congruent to exactly one of 0, 1, 2, 3, 4; call it r. By Corollary 4, m^2 + m + 1 \equiv r^2 + r + 1 \pmod{5}, so there are only five cases:

rr^2 + r + 1modulo 5
011
133
272
3133
4211

No case gives 0, so m^2 + m + 1 \not\equiv 0 \pmod{5} for every integer m. \square

The replacement rule is what turns a statement about infinitely many integers into a table of five rows.

Boundaries

  • The modulus is a positive integer. Congruence compares integers; it says nothing about 2.5 or \tfrac{1}{3}. With n = 1 every pair is congruent, so the interesting cases have n \ge 2.
  • Congruences with different moduli do not combine. Theorem 3 needs one n throughout: 1 \equiv 4 \pmod{3} and 1 \equiv 6 \pmod{5}, but 1 + 1 = 2 and 4 + 6 = 10 are congruent modulo neither 3 nor 5.
  • Division and cancellation are not allowed in general. Modulo 10, 2 \cdot 3 = 6 and 2 \cdot 8 = 16 differ by 10, so 2 \cdot 3 \equiv 2 \cdot 8 \pmod{10}, yet 3 \not\equiv 8 \pmod{10}. Cancelling the 2 gives a false statement. Relatedly, a product can be 0 modulo n with neither factor 0: 4 \cdot 5 = 20 \equiv 0 \pmod{10}. Cancelling a factor c is safe exactly when c has an inverse modulo n, which is the subject of Modular inverses and linear congruences.
  • Exponents may not be reduced modulo n. Corollary 4 replaces bases, not exponents: 6 \equiv 1 \pmod{5}, but 2^6 = 64 \equiv 4 \pmod{5} while 2^1 = 2.

Where this goes next

Congruence is an equivalence relation, and Relations, equivalence classes and partitions studies the rows it sorts the integers into, the remainder classes. Reducing a number written in base ten one power of 10 at a time explains the familiar divisibility tests (Where the divisibility tests come from). Replacing a base, then squaring and reducing over and over, computes powers with hundreds of digits (Powers modulo n). Repairing division, by multiplying by an inverse when one exists, is Modular inverses and linear congruences, and from there the road runs to Fermat's little theorem, the The Chinese remainder theorem and RSA public-key encryption.

Exercises

Day 1: deciding and listing

  1. Decide whether 83 \equiv 20 \pmod{9}, and confirm with remainders.
  2. Decide whether 64 \equiv 15 \pmod{8}, and confirm with remainders.
  3. Decide whether -17 \equiv 18 \pmod{5}, and confirm with remainders.
  4. Find -40 \bmod 6.
  5. Show that -1 \bmod n = n - 1 for every integer n \ge 2.
  6. List every integer x with -20 \le x \le 20 and x \equiv 4 \pmod{9}.
  7. Find every positive integer n for which 31 \equiv 7 \pmod{n}.

Day 1: reasoning

  1. Prove that every integer is congruent modulo 3 to exactly one of -1, 0, 1.
  2. Find integers a and b with a \equiv b \pmod{4} and a \equiv b \pmod{6} but a \not\equiv b \pmod{24}.
  3. Let n be even. Prove that if a \equiv b \pmod{n}, then a and b are both even or both odd.
  4. Prove directly from the definition that if a \equiv b \pmod{n} then -a \equiv -b \pmod{n}.

Day 2: computing with reduction

  1. Find the remainder when 1{,}234 + 5{,}678 is divided by 7, reducing each term first.
  2. Find the remainder when 998 \cdot 1{,}003 is divided by 11.
  3. Find the remainder when 517 \cdot 263 - 1{,}000 is divided by 12.
  4. Find the last two digits of 2{,}053 \cdot 7{,}318.
  5. Find the last two digits of 99 \cdot 98 using negative numbers.
  6. Find the last two digits of 1{,}234 \cdot 5 + 7{,}777 \cdot 3.

Day 2: calendars and clocks

  1. What weekday is 200 days after a Saturday?
  2. What weekday was 45 days before a Friday?
  3. A cargo ship leaves port at 19:00 on a 24-hour clock and sails for 100 hours. At what time does it arrive, and how many days later?
  4. A kiln timer is started at 10:45 and runs for 500 minutes. At what time on a 24-hour clock does it stop?

Day 2: reasoning

  1. Prove that the square of every odd integer is congruent to 1 modulo 8.
  2. Verify that 3 \cdot 4 \equiv 3 \cdot 9 \pmod{15} but 4 \not\equiv 9 \pmod{15}. Show that 4 \equiv 9 does hold for a smaller modulus that divides 15, and name it.
  3. Prove that 11 \nmid m^2 + 1 for every integer m.
  4. Prove by induction on k that if a \equiv b \pmod{n}, then a^k \equiv b^k \pmod{n} for every positive integer k.
Answers
  1. Yes. 83 - 20 = 63 = 7 \cdot 9. Remainders: 83 = 9 \cdot 9 + 2 and 20 = 2 \cdot 9 + 2, both 2.
  2. No. 64 - 15 = 49 and 8 \nmid 49. Remainders: 64 = 8 \cdot 8 + 0 and 15 = 1 \cdot 8 + 7, so 0 and 7.
  3. Yes. -17 - 18 = -35 = (-7) \cdot 5. Remainders: -17 = (-4) \cdot 5 + 3 and 18 = 3 \cdot 5 + 3, both 3.
  4. -40 \bmod 6 = 2, since -40 = (-7) \cdot 6 + 2 with 0 \le 2 < 6.
  5. -1 = (-1) \cdot n + (n - 1), and 0 \le n - 1 < n because n \ge 2. By uniqueness in the division algorithm the remainder is n - 1.
  6. x = 4 + 9k with -24 \le 9k \le 16, so k \in \{-2, -1, 0, 1\} and x \in \{-14, -5, 4, 13\}.
  7. The condition is n \mid 31 - 7 = 24, so n \in \{1, 2, 3, 4, 6, 8, 12, 24\}.
  8. Proof. Let a be an integer. By Theorem 1, a is congruent modulo 3 to exactly one of 0, 1, 2. Since 2 - (-1) = 3, 2 \equiv -1 \pmod{3}, so by transitivity a is congruent to at least one of -1, 0, 1. It cannot be congruent to two of them: if it were, those two would be congruent to each other by symmetry and transitivity, but their differences 1, 1 and 2 are not multiples of 3. \square
  9. For example a = 12, b = 0: 12 - 0 = 12 is a multiple of 4 and of 6 but not of 24. (Any a - b that is an odd multiple of 12 works.)
  10. Proof. Write n = 2t and a - b = kn = 2(kt), so a - b is even. If a and b had different parity, say a = 2p and b = 2s + 1, then a - b = 2(p - s - 1) + 1 would be odd; the other order is the same with signs swapped. So they have the same parity. \square
  11. Proof. From a - b = kn, (-a) - (-b) = b - a = (-k)n, and -k is an integer, so n \mid (-a) - (-b). \square
  12. 3. 1{,}234 = 176 \cdot 7 + 2 and 5{,}678 = 811 \cdot 7 + 1, so the sum is congruent to 2 + 1 = 3. Check: 6{,}912 = 987 \cdot 7 + 3.
  13. 5. 998 = 990 + 8 \equiv 8 \equiv -3 and 1{,}003 = 990 + 13 \equiv 2 \pmod{11}, so the product is congruent to -6 \equiv 5. Check: the product is 1{,}000{,}994, which is 90{,}999 \cdot 11 + 5.
  14. 7. 517 = 43 \cdot 12 + 1 \equiv 1, 263 = 21 \cdot 12 + 11 \equiv -1, 1{,}000 = 83 \cdot 12 + 4 \equiv 4. So the value is congruent to 1 \cdot (-1) - 4 = -5, and -5 \equiv 7 \pmod{12}. Check: 134{,}971 = 11{,}247 \cdot 12 + 7.
  15. 54. Modulo 100 the product is congruent to 53 \cdot 18 = 954 \equiv 54. Check: 2{,}053 \cdot 7{,}318 = 15{,}023{,}854.
  16. 02. 99 \equiv -1 and 98 \equiv -2 \pmod{100}, so 99 \cdot 98 \equiv (-1)(-2) = 2. Check: 99 \cdot 98 = 9{,}702.
  17. 01. 34 \cdot 5 = 170 \equiv 70 and 77 \cdot 3 = 231 \equiv 31, and 70 + 31 = 101 \equiv 1 \pmod{100}. Check: 6{,}170 + 23{,}331 = 29{,}501.
  18. Wednesday. Saturday is 6, 200 = 28 \cdot 7 + 4, and 6 + 4 = 10 \equiv 3 \pmod{7}.
  19. Tuesday. Friday is 5, -45 \equiv -45 + 49 = 4 \pmod{7}, and 5 + 4 = 9 \equiv 2 \pmod{7}.
  20. 23:00, four days later. 19 + 100 = 119 = 4 \cdot 24 + 23.
  21. 19:05. Minutes: 45 + 500 = 545 = 9 \cdot 60 + 5, so the clock shows 5 minutes past and 9 hours carry. Hours: 10 + 9 = 19, below 24, so the same day.
  22. Proof. Let m be odd and write m = 8q + r with 0 \le r < 8. Then r = m - 8q = m - 2(4q) is odd minus even, so r is odd: r \in \{1, 3, 5, 7\}. By Corollary 4, m^2 \equiv r^2 \pmod{8}, and r^2 is 1, 9, 25, 49, each congruent to 1 modulo 8 (since 8, 24, 48 are multiples of 8). So m^2 \equiv 1 \pmod{8}. \square
  23. 3 \cdot 4 = 12 and 3 \cdot 9 = 27 differ by 15, so they are congruent modulo 15; but 4 - 9 = -5 is not a multiple of 15. Modulo 5, which divides 15, 4 \equiv 9 holds since -5 = (-1) \cdot 5. Cancelling the 3 is not valid modulo 15 because 3 and 15 share the factor 3; the valid statement keeps only the modulus 15 / 3 = 5.
  24. Proof. m is congruent to one of 0, \dots, 10, and by Corollary 4 m^2 + 1 is congruent to r^2 + 1. For r = 0, 1, \dots, 10 the values of r^2 + 1 are congruent to 1, 2, 5, 10, 6, 4, 4, 6, 10, 5, 2 modulo 11. None is 0, so 11 \nmid m^2 + 1. \square
  25. Proof. Base case k = 1: a^1 = a \equiv b = b^1. Inductive step: assume a^k \equiv b^k \pmod{n}. Together with a \equiv b \pmod{n}, the multiplication rule of Theorem 3 gives a^k \cdot a \equiv b^k \cdot b, that is, a^{k+1} \equiv b^{k+1} \pmod{n}. By induction the claim holds for every positive integer k. \square
kg1128 · updated 2026-10-22 · CC-BY-SA-4.0