Division with remainder and Bézout's identity (units 3.2 and 3.5) describe the integers in terms of divisibility. Congruences repackage this information so that questions about remainders can be settled by ordinary algebra. This unit shows that congruence modulo is compatible with addition and multiplication, determines exactly when a residue can be inverted, solves every linear congruence , and proves two classical results: the Chinese remainder theorem and Fermat's little theorem. Throughout, denotes a positive integer.
Congruence as an equivalence relation
Definition 3.6.1
(Congruence modulo n)
For integers we write if . Equivalently, and leave the same remainder on division by . The equivalence classes are the residue classes .
Proposition 3.6.2
(Congruence respects addition and multiplication)
Congruence modulo is an equivalence relation on , and if and , then and .
Proof
(Write the differences explicitly)
Reflexivity, symmetry and transitivity follow from the facts that , that implies , and that and imply . For the operations, write and . Then and .
The previous result says that addition and multiplication of residue classes are well defined. It follows that any polynomial expression with integer coefficients may be evaluated after reducing each term modulo .
Common mistake
(Canceling a non-invertible factor)
Cancellation is not always allowed. From one may conclude only when ; in general one gets . For example, because , yet ; here , and the correct conclusion is .
Inverses and cancellation
Definition 3.6.3
(Invertible modulo n)
An integer is invertible modulo if there is an integer with .
Theorem 3.6.4
(Inverses exist exactly for coprime residues)
The integer is invertible modulo if and only if . If and are both inverses, then . If and , then .
Proof
(Bézout gives the inverse)
If , then for some , so any common divisor of and divides . Conversely, if , Bézout's identity gives integers with , hence . For uniqueness, . For cancellation multiply by an inverse of .
The proof is constructive: the extended Euclidean algorithm produces .
Linear congruences
Theorem 3.6.5
(Solving a linear congruence)
Let . The congruence has a solution if and only if . If , write , , . Then the solutions are exactly the integers , where is any solution of ; modulo there are exactly solution classes, .
Proof
(Reduce to a coprime congruence)
If is a solution, then , so is divisible by . Conversely suppose . Dividing by shows that is equivalent to . Now , since a common divisor would make a common divisor of and larger than . By the inverse theorem there is an inverse of modulo , and holds if and only if . The integers congruent to modulo fall into exactly classes modulo .
Common mistake
(Miscounting solutions)
A solvable linear congruence has solution classes modulo , not one. The number is exactly when .
The Chinese remainder theorem
Theorem 3.6.6
(Chinese remainder theorem for two moduli)
Let be positive integers with and let be integers. Then the system
has a solution, and any two solutions are congruent modulo .
Proof
(Build the solution from a Bézout identity)
Bézout gives . Put . Since and , we get ; symmetrically . If and are two solutions, then and . Write . Then with , so (by Bézout, is divisible by ), hence .
Without coprimality both halves of the argument fail; the next point shows that existence itself can fail.
Common mistake
(Chinese remainder theorem with non-coprime moduli)
The system may have no solution: and is inconsistent, since the first forces odd and the second forces even.
Fermat's little theorem
Theorem 3.6.7
(Fermat's little theorem)
If is prime and , then . Consequently for every integer .
Proof
(Multiplication by a permutes the nonzero residues)
Consider the integers . None is divisible by , because for . They are pairwise incongruent modulo : if , canceling (by the inverse theorem) gives , so . Hence their residues are exactly in some order, and
The integer is coprime to since each factor is, so canceling it gives . If , both and are .
Proof X-ray
Why the product of the nonzero residues cancels
The key move is to compute the same product in two ways: once directly, and once after multiplying every factor by , which only rearranges the residues. The rearrangement claim has two halves: the multiples stay among the nonzero residues because is prime and divides neither nor , and they are distinct because is invertible. Primality of is used to make every invertible; a composite modulus has non-invertible residues and the argument stops. The final step cancels , which is legitimate for the same reason. The closing sentence about is separate, since the hypothesis was needed for the permutation.
The hypothesis that the modulus is prime cannot simply be dropped.
Counterexample mode
Fermat's theorem needs a prime modulus
Claim: if , then for every . Take and , which are coprime. Then , so , not . The proof above fails at the step that makes every invertible: and are not invertible modulo . For composite the exponent does not work in general.
Common mistake
(Reducing exponents modulo the wrong number)
The exponent of may be reduced modulo (when ), not modulo .
Worked examples
Worked example 3.6.8
(A linear congruence with several solutions)
Solve . Here divides , so solutions exist. Divide by : . Since , the inverse of is , so . Modulo the solutions are . Check: , , .
Worked example 3.6.9
(An inverse by the Euclidean algorithm)
Find the inverse of modulo . Euclid: , , . Back-substitute: . Hence , and the inverse is . Check: . Remainders on division by lie in ; and are congruent modulo but only is the standard representative.
Worked example 3.6.10
(Chinese remainder theorem)
Solve , . Bézout: , so and . Then . Check: and . The solutions are .
Worked example 3.6.11
(Powers by Fermat)
Compute . By Fermat, . Since , we get .
Exercises
Quick check
(Solve .)
Divide by and reduce the modulus too.
Solution · Guided solution
divides . Dividing by gives , whose solution is (as ). Modulo the solutions are and . Check: and .
Quick check
(Show that has no solution.)
Compare with the right-hand side.
Solution · Guided solution
does not divide , so by the linear congruence theorem there is no solution. Directly, would give , divisible by , which is false.
Quick check
(Find the inverse of modulo .)
Run the Euclidean algorithm on and and back-substitute.
Solution · Guided solution
Euclid: , , . Then . So and the inverse is . Check: .
Quick check
(Solve , .)
Find with , then use .
Solution · Guided solution
Here , , , . Bézout: , so (coefficient of ) and (coefficient of ). Then . The solutions are . Check: and .
Quick check
(Find the remainder of on division by .)
Use Fermat's little theorem with .
Solution · Guided solution
, so (this is Fermat's theorem with ). Hence , and the remainder is .