Congruences and modular arithmetic

Five steps after eleven land on four

Label twelve equally spaced positions 0,1,2,…,11. Start at 11 and move five positions forward: 0,1,2,3,4. The integer sum is 11+5 = 16, while its position on this dial is 4. Subtracting one full turn, 12, preserves the position.

The dial uses residue 0 where an ordinary clock may print 12. The calculation does not say that 16 equals 4 or that five elapsed hours equal a negative seven-hour move. It records the same final position after whole turns have been discarded. Predict the position before revealing the directed steps.

Prepare with signed integer arithmetic

The published Multiplication and division lesson supplies exact products and division with remainders; Negative numbers and absolute value supplies signed integers. Powers, roots and the real number line prepares the repeated-multiplication example. The preparation links below return to this lesson’s proofs and solution formula.

Write ℤ for all integers, including zero and negative integers. For integers h,t, the notation h | t means t = hk for some integer k; h ∤ t means that no such integer exists. Fix an integer modulus m ≥ 2. Write a ≡ b (mod m) when m | (a−b), and a ≢ b (mod m) when that divisibility fails.

On a first reading, finish the dial, canonical residues and arithmetic rules, then try the worked calculations. Return to common divisors and integer combinations before studying cancellation or solving linear congruences. The needed greatest-common-divisor and Euclidean-division facts are proved locally, so no planned lesson is a required published prerequisite.

Each integer has one residue from zero through m−1

A canonical residue is the unique r with 0 ≤ r < m such that a = qm+r for an integer q. The quotient q may be negative. For −17 modulo 7, the correct division is −17 = (−3)·7+4, so the canonical residue is 4. A negative remainder produced by truncating a division is not this chosen representative.

For a nonnegative integer A, choose the greatest nonnegative integer q with qm ≤ A; the possible q form a finite nonempty list. Then r = A−qm is nonnegative and less than m, since r ≥ m would allow q+1. For a negative integer a, first choose an integer K ≥ 0 with a+Km ≥ 0, divide that nonnegative integer, then subtract K from its quotient. This supplies the same remainder bounds for every integer a.

If a = qm+r = q′m+r′ with both remainders in that range, then r−r′ is a multiple of m with absolute value less than m. The only such multiple is 0, so r = r′ and q = q′. Thus the canonical representative is unique.

Two integers are congruent modulo m exactly when their canonical residues agree. Equal residues make their difference a multiple of m. Conversely, write both divisions; a multiple difference forces their remainder difference to be a multiple of m of absolute value less than m, hence zero. Congruent integers may still be unequal.

One class contains infinitely many integers

The class of a representative r consists of every integer r+mk with k ∈ ℤ. For r = 4,m = 7 this includes …,−17,−10,−3,4,11,18,… . The six sample points below belong to one infinite class. The formula, not the finite drawing, describes every member. There are exactly m classes, represented by 0,1,…,m−1.

Congruence is reflexive: a−a = 0 = m·0. It is symmetric: if a−b = mk, then b−a = m(−k). It is transitive: if a−b = mk and b−c = mℓ, then a−c = m(k+ℓ). A relation with these three properties is called an equivalence relation.

These proofs hold for any integers in the stated domain. They explain why congruence classes are consistent groups, rather than relying on an enumeration of a few integers. The symbol ℓ is simply another integer coefficient.

Reduce before adding or multiplying

Suppose a ≡ a′ and b ≡ b′ modulo the same m. The sum difference is (a−a′)+(b−b′), and the subtraction difference is (a−a′)−(b−b′). Both are integer multiples of m. Thus a+b ≡ a′+b′ and a−b ≡ a′−b′ modulo m.

For products, ab−a′b′ = b(a−a′)+a′(b−b′). Each term is a multiple of m, so ab ≡ a′b′. Taking b = b′ also allows multiplying a congruence by any integer constant. No coprimality assumption is needed to multiply.

For every positive integer exponent e, a ≡ a′ implies a^e ≡ (a′)^e modulo m. The case e = 1 is the assumption. If the statement holds for e, the product rule applied to a^e·a proves it for e+1. This induction proves every positive exponent; negative powers require an inverse and are outside this power rule.

For instance, 44 has residue 2 and −17 has residue 4 modulo 7. Their sum 27 has residue 6; their difference 61 has residue 5; their product −748 has residue 1. Calculating with the representatives gives 2+4 = 6, 2−4 ≡ 5 and 2·4 ≡ 1.

Build a large exponent from repeated squares

To find 3^13 modulo 7, first compute 3² ≡ 2, then square to obtain 3⁴ ≡ 4 and 3⁸ ≡ 2. Since 13 = 8+4+1, multiply the residues for those three exponent contributions: 2·4·3 = 24 ≡ 3 (mod 7). The square with exponent 2 is available but is not selected.

At each stage the product and positive-power rules justify replacing a number by its residue. The exponent boxes state exact exponent values, not a numerical area or height. A complete table identifies the selected contributions, so the calculation remains readable without interpreting colour.

Multiplying is safe; cancelling needs a condition

Modulo 6, 2·1 = 2 and 2·4 = 8 are congruent, but 1 and 4 are not congruent modulo 6. Multiplication by 2 maps the distinct input classes 1 and 4 to the same output. Cancelling 2 with the original modulus would therefore lose a real distinction.

The complete multiplication map below pairs all six inputs with their outputs. Each output that occurs has two preimages; other output residues are unreachable. Compare it with multiplication by 3 modulo 7, which maps the seven inputs to seven distinct outputs. We next prove the exact condition behind that difference.

Euclidean division produces a useful integer combination

For an integer c and m ≥ 2, let d = gcd(c,m) be their greatest positive common divisor. Common divisors of c and m are the same as those of |c| and m; |c| is the nonnegative magnitude of c. Such divisors exist because 1 divides both, and form a finite list because they divide positive m. If c = 0, d = m. The pair is coprime when d = 1.

Divide a nonnegative A by a positive B to write A = qB+r with 0 ≤ r < B. An integer divides both A and B exactly when it divides both B and r: subtract qB in one direction and add qB in the other. Replacing (A,B) by (B,r) therefore preserves all common divisors. Repeating reaches remainder 0, because positive remainders strictly decrease. The last nonzero remainder is d.

Track integer combinations of the original c,m. Initially m = 0·c+1·m and |c| = s·c+0·m, where s = 1 for c ≥ 0 and s = −1 for c < 0. Subtracting q times one combination from another produces another integer combination. Consequently the final nonzero remainder satisfies d = uc+vm for integers u,v. This is Bézout’s identity. When c = 0, the identity is simply m = 0·c+1·m.

For c = 7,m = 26, the divisions are 26 = 3·7+5; 7 = 1·5+2; 5 = 2·2+1; 2 = 2·1+0. Back substitution gives 1 = 5−2·2 = 3·5−2·7 = 3·26−11·7. The integer coefficients are u = −11 and v = 3.

An inverse is a product that leaves residue one

A modular inverse of c is an integer t with ct ≡ 1 (mod m). If d = 1, an identity uc+vm = 1 gives cu ≡ 1; the canonical residue of u is the canonical inverse. Conversely, if ct−1 is a multiple of m, every common divisor of c,m divides ct and ct−1, hence divides 1. Therefore an inverse exists exactly when gcd(c,m) = 1.

Its canonical representative is unique. If ct ≡ cs ≡ 1, multiply ct ≡ cs by t to obtain t ≡ s, using ct ≡ 1 and the product rule. Two canonical representatives in 0,…,m−1 that are congruent must be equal. Other integer inverses are congruent copies; uniqueness does not mean only one integer works.

The identity 1 = 3·26−11·7 gives the inverse −11 ≡ 15 modulo 26. Check 7·15 = 105 = 4·26+1. In contrast, 6 has no inverse modulo 15 because their gcd is 3. The negative integer −3 has inverse 2 modulo 7, since −6 = (−1)·7+1. Zero has no inverse for any m ≥ 2.

Retain the modulus only for a coprime multiplier

If gcd(c,m) = 1 and m divides c(a−b), use uc+vm = 1. Multiplying by a−b gives a−b = uc(a−b)+vm(a−b), a sum of multiples of m. Hence a ≡ b (mod m). This proves cancellation with the original modulus; multiplying gives the converse implication.

For arbitrary c, write d = gcd(c,m), c′ = c/d and m′ = m/d. Dividing a Bézout identity by d gives uc′+vm′ = 1. Thus c′ and m′ are coprime. The divisibility m | c(a−b) is equivalent to m′ | c′(a−b), and then to m′ | (a−b). Therefore ca ≡ cb (mod m) holds exactly when a ≡ b (mod m/d).

If m/d = 1, this last divisibility says that every integer difference is divisible by 1; the reduced condition is automatic. This is the only use here of the shorthand modulo 1, whose unique residue is 0. It does not permit cancelling with the original modulus. For c = 0 it correctly records that 0a and 0b always agree.

In the failed cancellation example c = 2,m = 6, the reduced modulus is 3. The true conclusion is 1 ≡ 4 (mod 3). When c and m are coprime the reduced modulus equals m, so no residue information is lost.

Solve a linear congruence and retain every class

Consider cx ≡ b (mod m), with integers c,b,x and m ≥ 2. Let d = gcd(c,m). A solution gives cx−km = b for some integer k, so d must divide b. If d ∤ b there is no solution.

If d | b and uc+vm = d, multiply by b/d: c·u(b/d)+m·v(b/d) = b. Thus x₀ = u(b/d) is a solution. Any other x is a solution exactly when m | c(x−x₀). The adjusted cancellation result gives x = x₀+(m/d)k for some integer k. This proves both that every listed integer works and that no solution is omitted.

Choose x₀ canonically in 0,…,m/d−1, replacing it by a congruent integer with that spacing if necessary. Exactly d solution representatives lie in 0,…,m−1: x₀, x₀+m/d,…,x₀+(d−1)m/d. They are distinct and remain in range. There are infinitely many integer solutions, but only d solution classes modulo m.

For 6x ≡ 8 (mod 14), d = 2 and 2 = 14−2·6. The initial solution is x₀ = −2·4 = −8; its representative modulo 7 is 6. All integer solutions are x = 6+7k, and the two canonical residues modulo 14 are 6 and 13. Their products 36 and 78 both leave residue 8.

Zero coefficients follow the same criterion. For 0x ≡ b (mod m), d = m. If m | b, every integer x works, giving all m residue classes and spacing 1. If m ∤ b, none works. The formula never divides by c, so c = 0 does not create an exception or an undefined step.

Predict a result, then inspect its entire finite case

Try signed dial moves, negative members of a class, multiplication maps with and without collisions, and inverses with positive, negative and zero coefficients. For a linear case, predict whether the target is reachable and how many residue classes work before revealing all candidate products.

The finite tables exhaust the stated modulus or trace. They can establish a particular example and expose a counterexample. The general rules for every integer follow from the proofs above, not from testing a bounded list.

Worked examples

Try it yourself

1. Give the canonical residues of 35 modulo 12 and −25 modulo 6, including both quotients.

   Show the answer and reasoning

   35 = 2·12+11 and −25 = (−5)·6+5, so the residues are 11 and 5.

   Both remainders are nonnegative and less than the stated modulus. The second quotient must be −5, not −4, to meet those bounds.

2. Are 19 and −1 equal? Are they congruent modulo 5? List three more members of their class.

   Show the answer and reasoning

   They are unequal but congruent modulo 5. Examples of other members are −6,4,9.

   Their difference is 20 = 4·5. Every member has form 4+5k for an integer k; distinct integers can name the same residue class.

3. If a−b = 7u and b−c = 7v for integers u,v, prove a ≡ c (mod 7).

   Show the answer and reasoning

   a−c = (a−b)+(b−c) = 7(u+v), so 7 divides a−c.

   The sum u+v is an integer. This is the transitivity proof for arbitrary a,b,c, rather than a finite sample.

4. From a ≡ b (mod 6), may you conclude 2a ≡ 2b (mod 6)? May you reverse that implication without another condition?

   Show the answer and reasoning

   Multiplication is valid. The reverse implication fails: a = 1,b = 4 gives a counterexample.

   A multiple difference stays a multiple after multiplying. But 2·1 and 2·4 have the same residue 2 while 1 and 4 have different residues modulo 6.

5. Find the canonical inverse of −3 modulo 7. Does 6 have an inverse modulo 15?

   Show the answer and reasoning

   The inverse of −3 modulo 7 is 2. There is no inverse of 6 modulo 15.

   (−3)·2 = −6 ≡ 1 modulo 7. Every product 6t is divisible by 3, so it cannot differ from 1 by a multiple of 15, which is also divisible by 3.

6. State the exact cancellation conclusion from 5a ≡ 5b (mod 6) and from 3a ≡ 3b (mod 6).

   Show the answer and reasoning

   The first is equivalent to a ≡ b (mod 6). The second is equivalent to a ≡ b (mod 2).

   The gcd values are 1 and 3. Divide the original modulus by the corresponding gcd; retaining 6 in the second conclusion would lose valid pairs.

7. Does 6x ≡ 5 (mod 14) have an integer solution?

   Show the answer and reasoning

   No solution exists.

   The gcd is 2, which does not divide 5. Both 6x and every multiple of 14 are even, so their difference cannot equal odd 5.

8. Give every canonical solution of 4x ≡ 0 (mod 8), then all integer solutions.

   Show the answer and reasoning

   The canonical representatives are 0,2,4,6. All integer solutions are x = 2k for k ∈ ℤ.

   The gcd is 4 and the spacing is 8/4 = 2. Exactly four distinct solution classes appear modulo 8, while infinitely many even integers satisfy the congruence.

9. Solve 0x ≡ 0 (mod 6) and 0x ≡ 1 (mod 6).

   Show the answer and reasoning

   Every integer solves the first, with all six residue classes. The second has no solution.

   The gcd of 0 and 6 is 6, so the target must be divisible by 6. The calculation does not divide by zero.

10. Using 3² ≡ 2 and 3⁴ ≡ 4 modulo 7, find 3^5. Is the exponent-2 square selected?

    Show the answer and reasoning

    3^5 ≡ 4·3 = 12 ≡ 5 (mod 7). The exponent-2 square is not selected.

    5 = 4+1. Repeated squaring provides useful intermediate powers, but only the exponent contributions in the chosen sum enter the final product.

11. Does inverse uniqueness say that 15 is the only integer t with 7t ≡ 1 (mod 26)?

    Show the answer and reasoning

    No. It is the only canonical representative, and every t = 15+26k for k ∈ ℤ also works.

    The product difference 7·26k is a multiple of 26. The uniqueness statement requires the range 0 ≤ t < 26 or, equivalently, uniqueness of the residue class.

What to carry forward

• Congruence records a divisible difference, not equality of the integers.
• Canonical residues are the unique representatives 0,…,m−1, including for negative integers.
• With a fixed modulus, addition, subtraction, multiplication and positive integer powers preserve congruence.
• An inverse exists exactly for a coprime coefficient and is unique as a canonical residue.
• Cancel a coefficient c by reducing the modulus to m/gcd(c,m); keep m only when that gcd is 1.
• A linear congruence cx ≡ b has solutions exactly when gcd(c,m) divides b; its integer spacing is m/gcd(c,m).
• Complete finite tables establish their stated cases. Universal rules require the integer proofs.