3.1: Introduction to Congruences

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 \mid (a-b)\) where \(a\) and \(b\) are integers, i.e. if \(a=b+km\) where \(k\in \mathbb{Z}\).

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

\(19\equiv 5 (mod \ 7)\). Similarly \(2k+1 \equiv 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:

1. If \(a \equiv b(mod \ m)\), then \(b\equiv a (mod \ m)\).
2. If \(a\equiv b(mod \ m)\) and \(b\equiv c(mod \ m)\), then \(a\equiv c (mod \ m)\).
3. If \(a\equiv b(mod\ m)\), then \(a+c \equiv b+c (mod \ m)\).
4. If \(a\equiv b(mod\ m)\), then \(a-c \equiv b-c (mod \ m)\).
5. If \(a\equiv b(mod\ m)\), then \(ac \equiv bc (mod \ m)\).
6. If \(a\equiv b(mod\ m)\), then \(ac \equiv bc (mod \ mc)\), for \(c>0\).
7. If \(a\equiv b(mod\ m)\) and \(c \equiv d (mod \ m)\) then \(a+c \equiv (b+d) (mod \ m)\).
8. If \(a\equiv b(mod\ m)\) and \(c \equiv d (mod \ m)\) then \(a-c \equiv (b-d) (mod \ m)\).
9. If \(a\equiv b(mod\ m)\) and \(c \equiv d (mod \ m)\) then \(ac \equiv bd (mod \ m)\).

1. If \(a \equiv b(mod \ m)\), then \(m\mid (a-b)\). Thus there exists integer \(k\) such that \(a-b=mk\), this implies \(b-a=m(-k)\) and thus \(m\mid (b-a)\). Consequently \(b\equiv a (mod \ m)\).

2. Since \(a\equiv b(mod \ m)\), then \(m\mid (a-b)\). Also, \(b\equiv c(mod \ m)\), then \(m\mid (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)\).

3. Since \(a\equiv b (mod \ m)\), then \(m \mid (a-b)\). So if we add and subtract \(c\) we get \[m\mid ((a+c)-(b+c))\] and as a result \[a+c\equiv b+c (mod \ m).\]

4. Since \(a\equiv b (mod \ m)\), then \(m \mid (a-b)\) so we can subtract and add \(c\) and we get \[m\mid ((a-c)-(b-c))\] and as a result \[a-c\equiv b-c (mod \ m).\]

5. If \(a \equiv b(mod \ m)\), then \(m\mid (a-b)\). Thus there exists integer \(k\) such that \(a-b=mk\) and as a result \(ac-bc=m(kc)\). Thus \[m\mid (ac-bc)\] and hence \[ac\equiv bc (mod \ m).\]

6. If \(a \equiv b(mod \ m)\), then \(m\mid (a-b)\). Thus there exists integer \(k\) such that \(a-b=mk\) and as a result \[ac-bc=mc(k).\] Thus \[mc\mid (ac-bc)\] and hence \[ac\equiv bc (mod \ mc).\]

7. Since \(a\equiv b(mod \ m)\), then \(m\mid (a-b)\). Also, \(c\equiv d(mod \ m)\), then \(m\mid (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\mid ((a+c)-(b+d)),\] hence \[a+c\equiv b+d(mod \ m).\]

8. 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\mid ((a-c)-(b-d)),\] hence \[a-c\equiv b-d(mod \ m).\]

9. 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\mid (ac-bd),\]hence \[ac\equiv bd(mod \ m).\]

1. Because \(14\equiv 8(mod\ 6)\) then \(8 \equiv 14 (mod\ 6)\).

2. Because \(22\equiv 10(mod \ 6)\) and \(10 \equiv 4(mod \ 6)\). Notice that \(22\equiv 4(mod \ 6)\).

3. Because \(50\equiv 20 (mod\ 15)\), then \(50+5=55\equiv 20+5=25(mod\ 15)\).

4. Because \(50\equiv 20 (mod\ 15)\), then \(50-5=45\equiv 20-5=15(mod\ 15)\).

5. Because \(19\equiv 16(mod3)\), then \(2(19)=38\equiv 2(16)=32(mod \ 3).\)

6. Because \(19\equiv 16(mod3)\), then \(2(19)=38\equiv 2(16)=32(mod \ 2(3)=6).\)

7. Because \(19\equiv 3 (mod \ 8)\) and \(17\equiv 9(mod \ 8)\), then \(19+17=36\equiv 3+9=12(mod \ 8)\).

8. Because \(19\equiv 3 (mod \ 8)\) and \(17\equiv 9(mod \ 8)\), then \(19-17=2\equiv 3-9=-6(mod \ 8)\).

9. Because \(19\equiv 3 (mod \ 8)\) and \(17\equiv 9(mod \ 8)\), then \(19(17)=323\equiv 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.

1. If \(a,b, c\) and \(m\) are integers such that \(m>0\), \(d=(m,c)\) and \(ac\equiv bc(mod \ m)\), then \(a\equiv b (mod \ m/d)\).

2. If \((m,c)=1\) then \(a=b(mod \ m)\) if \(ac\equiv bc(mod \ m)\).

Part 2 follows immediately from Part 1. For Part 1, if \(ac\equiv bc(mod \ m)\), then \[m\mid (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 \mid (a-b)\). Hence \(a\equiv b (mod \ m/d)\).

\(38 \equiv 10 (mod\ 7)\). Since \((2,7)=1\) then \(19\equiv 5 (mod \ 7).\)

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

If \[a\equiv b(mod \ m_1), a\equiv b(mod \ m_2),...,a\equiv b(mod \ m_t)\] where \(a,b,m_1,m_2,...,m_t\) are integers and \(m_1,m_2,...,m_t\) are positive, then \[a\equiv b(mod \ \langle m_1,m_2,...m_t\rangle)\]

Since \(a\equiv b (mod \ m_i)\) for all \(1\leq i\leq t\). Thus \(m_i \mid (a-b)\). As a result, \[\langle m_1,m_2,...,m_t\rangle \mid (a-b)\] (prove this as an exercise). Thus \[a\equiv b(mod \ \langle m_1,m_2,...m_t\rangle).\]

Exercises

1. Determine whether 3 and 99 are congruent modulo 7 or not.

2. Show that if \(x\) is an odd integer, then \(x^2\equiv 1(mod \ 8)\)

3. Show that if \(a,b, m\) and \(n\) are integers such that \(m\) and \(n\) are positive, \(n \mid m\) and \(a\equiv b (mod \ m)\), then \(a\equiv b (mod \ n).\)

4. Show that if \(a_i\equiv b_i(mod \ m)\) for \(i=1,2,...,n\), where \(m\) is a positive integer and \(a_i,b_i\) are integers for \(j=1,2,...,n\), then \(\sum_{i=1}^na_i\equiv \sum_{i=1}^nb_i(mod \ m)\)

5. For which \(n\) does the expression \(1+2+...+(n-1)\equiv 0(mod \ n)\) holds.

Contributors

• 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.