3.1: Introduction to Congruences
( \newcommand{\kernel}{\mathrm{null}\,}\)
As we mentioned in the introduction, the theory of congruences was developed by Gauss at the beginning of the nineteenth century.
Let m be a positive integer. We say that a is congruent to b modulo m if m∣(a−b) where a and b are integers, i.e. if a=b+km where k∈Z.
If a is congruent to b modulo m, we write a≡b(mod m).
19≡5(mod 7). Similarly 2k+1≡1(mod 2) which means every odd number is congruent to 1 modulo 2.
There are many common properties between equations and congruences. Some properties are listed in the following theorem.
Theorem: Properties of Congruences
Let a,b,c and d denote integers. Let m be a positive integers. Then:
- If a≡b(mod m), then b≡a(mod m).
- If a≡b(mod m) and b≡c(mod m), then a≡c(mod m).
- If a≡b(mod m), then a+c≡b+c(mod m).
- If a≡b(mod m), then a−c≡b−c(mod m).
- If a≡b(mod m), then ac≡bc(mod m).
- If a≡b(mod m), then ac≡bc(mod mc), for c>0.
- If a≡b(mod m) and c≡d(mod m) then a+c≡(b+d)(mod m).
- If a≡b(mod m) and c≡d(mod m) then a−c≡(b−d)(mod m).
- If a≡b(mod m) and c≡d(mod m) then ac≡bd(mod m).
- If a≡b(mod m), then m∣(a−b). Thus there exists integer k such that a−b=mk, this implies b−a=m(−k) and thus m∣(b−a). Consequently b≡a(mod m).
- Since a≡b(mod m), then m∣(a−b). Also, b≡c(mod m), then m∣(b−c). As a result, there exit two integers k and l such that a=b+mk and b=c+ml, which imply that a=c+m(k+l) giving that a=c(mod m).
- Since a≡b(mod m), then m∣(a−b). So if we add and subtract c we get m∣((a+c)−(b+c)) and as a result a+c≡b+c(mod m).
- Since a≡b(mod m), then m∣(a−b) so we can subtract and add c and we get m∣((a−c)−(b−c)) and as a result a−c≡b−c(mod m).
- If a≡b(mod m), then m∣(a−b). Thus there exists integer k such that a−b=mk and as a result ac−bc=m(kc). Thus m∣(ac−bc) and hence ac≡bc(mod m).
- If a≡b(mod m), then m∣(a−b). Thus there exists integer k such that a−b=mk and as a result ac−bc=mc(k). Thus mc∣(ac−bc) and hence ac≡bc(mod mc).
- Since a≡b(mod m), then m∣(a−b). Also, c≡d(mod m), then m∣(c−d). As a result, there exits two integers k and l such that a−b=mk and c−d=ml. Note that (a−b)+(c−d)=(a+c)−(b+d)=m(k+l). As a result, m∣((a+c)−(b+d)), hence a+c≡b+d(mod m).
- If a=b+mk and c=d+ml where k and l are integers, then (a−b)−(c−d)=(a−c)−(b−d)=m(k−l). As a result, m∣((a−c)−(b−d)), hence a−c≡b−d(mod m).
- There exit two integers k and l such that a−b=mk and c−d=ml and thus ca−cb=m(ck) and bc−bd=m(bl). Note that (ca−cb)+(bc−bd)=ac−bd=m(kc−lb). As a result, m∣(ac−bd),hence ac≡bd(mod m).
- Because 14≡8(mod 6) then 8≡14(mod 6).
- Because 22≡10(mod 6) and 10≡4(mod 6). Notice that 22≡4(mod 6).
- Because 50≡20(mod 15), then 50+5=55≡20+5=25(mod 15).
- Because 50≡20(mod 15), then 50−5=45≡20−5=15(mod 15).
- Because 19≡16(mod3), then 2(19)=38≡2(16)=32(mod 3).
- Because 19≡16(mod3), then 2(19)=38≡2(16)=32(mod 2(3)=6).
- Because 19≡3(mod 8) and 17≡9(mod 8), then 19+17=36≡3+9=12(mod 8).
- Because 19≡3(mod 8) and 17≡9(mod 8), then 19−17=2≡3−9=−6(mod 8).
- Because 19≡3(mod 8) and 17≡9(mod 8), then 19(17)=323≡3(9)=27(mod 8).
We now present a theorem that will show one difference between equations and congruences. In equations, if we divide both sides of the equation by a non-zero number, equality holds. While in congruences, it is not necessarily true. In other words, dividing both sides of the congruence by the same integer doesn’t preserve the congruence.
- If a,b,c and m are integers such that m>0, d=(m,c) and ac≡bc(mod m), then a≡b(mod m/d).
- If (m,c)=1 then a=b(mod m) if ac≡bc(mod m).
Part 2 follows immediately from Part 1. For Part 1, if ac≡bc(mod m), then m∣(ac−bc)=c(a−b). Hence there exists k such that c(a−b)=mk. Dividing both sides by d, we get (c/d)(a−b)=k(m/d). Since (m/d,c/d)=1, it follows that m/d∣(a−b). Hence a≡b(mod m/d).
38≡10(mod 7). Since (2,7)=1 then 19≡5(mod 7).
The following theorem combines several congruences of two numbers with different moduli.
If a≡b(mod m1),a≡b(mod m2),...,a≡b(mod mt) where a,b,m1,m2,...,mt are integers and m1,m2,...,mt are positive, then a≡b(mod ⟨m1,m2,...mt⟩)
Since a≡b(mod mi) for all 1≤i≤t. Thus mi∣(a−b). As a result, ⟨m1,m2,...,mt⟩∣(a−b) (prove this as an exercise). Thus a≡b(mod ⟨m1,m2,...mt⟩).
Exercises
- Determine whether 3 and 99 are congruent modulo 7 or not.
- Show that if x is an odd integer, then x2≡1(mod 8)
- Show that if a,b,m and n are integers such that m and n are positive, n∣m and a≡b(mod m), then a≡b(mod n).
- Show that if ai≡bi(mod m) for i=1,2,...,n, where m is a positive integer and ai,bi are integers for j=1,2,...,n, then ∑ni=1ai≡∑ni=1bi(mod m)
- For which n does the expression 1+2+...+(n−1)≡0(mod n) holds.
Contributors and Attributions
Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.