Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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(ab) where a and b are integers, i.e. if a=b+km where kZ.

If a is congruent to b modulo m, we write ab(mod m).

195(mod 7). Similarly 2k+11(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:

  1. If ab(mod m), then ba(mod m).
  2. If ab(mod m) and bc(mod m), then ac(mod m).
  3. If ab(mod m), then a+cb+c(mod m).
  4. If ab(mod m), then acbc(mod m).
  5. If ab(mod m), then acbc(mod m).
  6. If ab(mod m), then acbc(mod mc), for c>0.
  7. If ab(mod m) and cd(mod m) then a+c(b+d)(mod m).
  8. If ab(mod m) and cd(mod m) then ac(bd)(mod m).
  9. If ab(mod m) and cd(mod m) then acbd(mod m).
  1. If ab(mod m), then m(ab). Thus there exists integer k such that ab=mk, this implies ba=m(k) and thus m(ba). Consequently ba(mod m).
  2. Since ab(mod m), then m(ab). Also, bc(mod m), then m(bc). 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).
  3. Since ab(mod m), then m(ab). So if we add and subtract c we get m((a+c)(b+c)) and as a result a+cb+c(mod m).
  4. Since ab(mod m), then m(ab) so we can subtract and add c and we get m((ac)(bc)) and as a result acbc(mod m).
  5. If ab(mod m), then m(ab). Thus there exists integer k such that ab=mk and as a result acbc=m(kc). Thus m(acbc) and hence acbc(mod m).
  6. If ab(mod m), then m(ab). Thus there exists integer k such that ab=mk and as a result acbc=mc(k). Thus mc(acbc) and hence acbc(mod mc).
  7. Since ab(mod m), then m(ab). Also, cd(mod m), then m(cd). As a result, there exits two integers k and l such that ab=mk and cd=ml. Note that (ab)+(cd)=(a+c)(b+d)=m(k+l). As a result, m((a+c)(b+d)), hence a+cb+d(mod m).
  8. If a=b+mk and c=d+ml where k and l are integers, then (ab)(cd)=(ac)(bd)=m(kl). As a result, m((ac)(bd)), hence acbd(mod m).
  9. There exit two integers k and l such that ab=mk and cd=ml and thus cacb=m(ck) and bcbd=m(bl). Note that (cacb)+(bcbd)=acbd=m(kclb). As a result, m(acbd),hence acbd(mod m).
  1. Because 148(mod 6) then 814(mod 6).
  2. Because 2210(mod 6) and 104(mod 6). Notice that 224(mod 6).
  3. Because 5020(mod 15), then 50+5=5520+5=25(mod 15).
  4. Because 5020(mod 15), then 505=45205=15(mod 15).
  5. Because 1916(mod3), then 2(19)=382(16)=32(mod 3).
  6. Because 1916(mod3), then 2(19)=382(16)=32(mod 2(3)=6).
  7. Because 193(mod 8) and 179(mod 8), then 19+17=363+9=12(mod 8).
  8. Because 193(mod 8) and 179(mod 8), then 1917=239=6(mod 8).
  9. Because 193(mod 8) and 179(mod 8), then 19(17)=3233(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.

  1. If a,b,c and m are integers such that m>0, d=(m,c) and acbc(mod m), then ab(mod m/d).
  2. If (m,c)=1 then a=b(mod m) if acbc(mod m).

Part 2 follows immediately from Part 1. For Part 1, if acbc(mod m), then m(acbc)=c(ab). Hence there exists k such that c(ab)=mk. Dividing both sides by d, we get (c/d)(ab)=k(m/d). Since (m/d,c/d)=1, it follows that m/d(ab). Hence ab(mod m/d).

3810(mod 7). Since (2,7)=1 then 195(mod 7).

The following theorem combines several congruences of two numbers with different moduli.

If ab(mod m1),ab(mod m2),...,ab(mod mt) where a,b,m1,m2,...,mt are integers and m1,m2,...,mt are positive, then ab(mod m1,m2,...mt)

Since ab(mod mi) for all 1it. Thus mi(ab). As a result, m1,m2,...,mt(ab) (prove this as an exercise). Thus ab(mod m1,m2,...mt).

Exercises

  1. Determine whether 3 and 99 are congruent modulo 7 or not.
  2. Show that if x is an odd integer, then x21(mod 8)
  3. Show that if a,b,m and n are integers such that m and n are positive, nm and ab(mod m), then ab(mod n).
  4. Show that if aibi(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=1aini=1bi(mod m)
  5. For which n does the expression 1+2+...+(n1)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.


This page titled 3.1: Introduction to Congruences is shared under a CC BY license and was authored, remixed, and/or curated by Wissam Raji.

  • Was this article helpful?

Support Center

How can we help?