1.15: Congruences

Definition \(\PageIndex{1}\)

Let \(m\ge0\). We write \(a\equiv b\pmod m\) if \(m\mid a-b\), and we say that \(a\) is congruent to \(b\) modulo \(m\). Here \(m\) is said to be the modulus of the congruence. The notation \(a\not\equiv b\pmod m\) means that it is false that \(a\equiv b\pmod m\).

Example \(\PageIndex{1}\)

1. \(25\equiv 1\pmod 4\) since \(4\mid 24\)
2. \(25\not\equiv 2\pmod 4\) since \(4\nmid 23\)
3. \(1\equiv -3\pmod 4\) since \(4\mid 4\)
4. \(a\equiv b\pmod 1\) for all \(a\), \(b\) since “\(1\) divides everything.”
5. \(a \equiv b \pmod 0 \Longleftrightarrow a = b\) for all \(a\), \(b\) since “\(0\) divides only \(0\).”

Remark \(\PageIndex{1}\)

As you see, the cases \(m=1\) and \(m=0\) are not very interesting so mostly we will only be interested in the case \(m\ge 2\).

WARNING

Do not confuse the use of mod in Definition \(\PageIndex{1}\) with that of Definition 5.3. We shall see that the two uses of mod are related, but have different meanings: Recall

Note \(\PageIndex{1}\)

\(a\pmod b=r\) where \(r\) is the remainder given by the Division Algorithm when \(a\) is divided by \(b\)

and by Definition 15.1 \[\boxed{a\equiv b\pmod m\text{ means }m\mid a-b.}\nonumber \]

Example \(\PageIndex{2}\)

\[\boxed{25\equiv 5\pmod 4\text{ is true}}\,,\nonumber \] since \(4\mid 20\) but \[\boxed{25=5\bmod 4\text{ is false}}\,,\nonumber \] since the latter means \(25=1\).

Remark \(\PageIndex{2}\)

The mod in \(a\equiv b\pmod m\) defines a binary relation, whereas the mod in \(a \bmod b\) is a binary operation.

More terminology:

Expressions such as \[\begin{aligned} x &=2 \\ 4^2 &=16 \\ x^2+2x &=\sin(x)+3\end{aligned}\] are called equations. By analogy, expressions such as \[\begin{aligned} x &\equiv 2\pmod{16} \\ 25 &\equiv 5\pmod 5 \\ x^3+2x &\equiv 6x^2+3\pmod{27}\end{aligned}\] are called congruences. Before discussing further the analogy between equations and congruences, we show the relationship between the two different definitions of mod.

Theorem \(\PageIndex{1}\)

For \(m>0\) and for all \(a\), \(b\): \[a \equiv b \pmod m \Longleftrightarrow a \bmod m= b \bmod m.\nonumber\]

Proof

“\(\Rightarrow\)” Assume that \(a\equiv b\pmod m\). Let \(r_1=a\bmod m\) and \(r_2=b\bmod m\). We want to show that \(r_1=r_2\). By definition we have

1. \(m\mid a-b\),
2. \(a=mq_1+r_1\), \(0\le r_1<m\), and
3. \(b=mq_2+r_2\), \(0\le r_2<m\)

From (1) we obtain \[a-b=mt\nonumber \] for some \(t\). Hence \[a=mt+b.\nonumber \] Using (2) and (3) we see that \[a=mq_1+r_1=m\left(q_2+t\right)+r_2.\nonumber \] Since \(0\le r_1<m\) and \(0\le r_2<m\) by the uniqueness part of the Division Algorithm we obtain \(r_1=r_2\), as desired.

\(``\Leftarrow\)” Assume that \(a\bmod m=b\bmod m\). We must show that \(a\equiv b\pmod m\). Let \(r=a\bmod m=b\bmod m\), then by definition we have \[a=mq_1+r,\quad 0\le r<m,\nonumber \] and \[b=mq_2+r,\quad 0\le r<m.\nonumber \] Hence \[a-b=m\left(q_1-q_2\right).\nonumber \] This shows that \(m\mid a-b\) and hence \(a\equiv b\pmod m\), as desired.

Exercise \(\PageIndex{1}\)

Prove that for all \(m>0\) and for all \(a\): \[a\equiv a\bmod m\pmod m.\nonumber \]

Exercise \(\PageIndex{2}\)

Using Definition \(\PageIndex{1}\) show that the following congruences are true \[\begin{aligned} 385 &\equiv 322\pmod 3 \\ -385 &\equiv -322\pmod 3 \\ 1 &\equiv -17\pmod 3 \\ 33 &\equiv 0\pmod 3.\end{aligned}\]

Exercise \(\PageIndex{3}\)

Use Theorem \(\PageIndex{1}\) to show that the congruences in Exercise \(\PageIndex{2}\) are valid.

Exercise \(\PageIndex{4}\)

1. Show that \(a\) is even \(\Leftrightarrow a\equiv 0\pmod 2\) and \(a\) is odd \(\Leftrightarrow a\equiv 1\pmod 2\).
2. Show that \(a\) is even \(\Leftrightarrow a \bmod 2 = 0\) and \(a\) is odd \(\Leftrightarrow a \bmod 2 = 1\).

Exercise \(\PageIndex{5}\)

Show that if \(m>0\) and \(a\) is any integer, there is a unique integer \(r\in\{0,1,2,\dotsc,m-1\}\) such that \(a\equiv r\pmod m\).

Exercise \(\PageIndex{6}\)

Find integers \(a\) and \(b\) such that \(0<a<15\), \(0<b<15\) and \(ab\equiv 0\pmod{15}\).

Exercise \(\PageIndex{7}\)

Find integers \(a\) and \(b\) such that \(1<a<15\), \(1<b<15\), and \(ab\equiv 1\pmod{15}\).

Exercise \(\PageIndex{8}\)

Show that if \(d\mid m\) and \(d>0\), then \[a\equiv b\pmod m\Rightarrow a\equiv b\pmod d.\nonumber\]

The next two theorems show that congruences and equations share many similar properties.

Theorem \(\PageIndex{2}\): Congruence is an Equivalence Relation

(Congruence is an equivalence relation). For all \(a\), \(b\), \(c\) and \(m>0\) we have

1. \(a\equiv a\pmod m\)[reflexivity]
2. \(a\equiv b\pmod m\Rightarrow b\equiv a\pmod m\)[symmetry]
3. \(a\equiv b\pmod m\) and \(b\equiv c\pmod m\Rightarrow a\equiv c\pmod m\)[transitivity]

Proof

Proof of (1). \(a-a=0=0\cdot m\), so \(m\mid a-a\). Hence \(a\equiv a\pmod m\).

Proof of (2). If \(a\equiv b\pmod m\), then \(m\mid a-b\). Hence \(a-b=mq\). Hence \(b-a=m(-q)\), so \(m\mid b-a\). Hence \(b\equiv a\pmod m\).

Proof of (3). If \(a\equiv b\pmod m\) and \(b\equiv c\pmod m\) then \(m\mid a-b\) and \(m\mid b-c\). By the linearity property \(m\mid (a-b)+(b-c)\). That is, \(m\mid a-c\). Hence \(a\equiv c\pmod m\).

Recall that a polynomial is an expression of the form \[f(x)=a_nx^n+a_{n-1}x^{n-1}+\dotsb+a_1x+a_0.\nonumber \] Here we will assume that the coefficients \(a_n,\dotsc,a_0\) are integers and \(x\) also represents an integer variable. Here, of course, \(n\ge 0\) and \(n\) is an integer.

Theorem \(\PageIndex{3}\)

If \(a\equiv b \pmod m\) and \(c\equiv d\pmod m\), then

1. \(a\pm c\equiv b\pm d\pmod m\)
2. \(ac\equiv bd\pmod m\)
3. \(a^n\equiv b^n\pmod m\) for all \(n\ge 1\)
4. \(f(a)\equiv f(b) \pmod m\) for all polynomials \(f(x)\) with integer coefficients.

Proof

Proof of (1). To prove (1) since \(a-c=a+(-c)\), it suffices to prove only the “\(+\) case.” By assumption \(m\mid a-b\) and \(m\mid c-d\). By linearity, \(m\mid (a-b)+(c-d)\), that is \(m\mid (a+c)-(b+d)\). Hence \[a+c\equiv b+d\pmod m.\nonumber \]

Proof of (2). Since \(m\mid a-b\) and \(m\mid c-d\) by linearity \[m\mid c(a-b)+b(c-d).\nonumber \] Now \(c(a-b)+b(c-d)=ca-bd\), hence \[m \mid ca-bd,\nonumber \] and so \(ca\equiv bd\pmod m\), as desired.

Proof of (3). We prove \(a^n\equiv b^n\pmod m\) by induction on \(n\). If \(n=1\), the result is true by our assumption that \(a\equiv b\pmod m\). Assume it holds for \(n=k\). Then we have \(a^k\equiv b^k\pmod m\). This, together with \(a\equiv b\pmod m\) using (2) above, gives \(aa^k\equiv bb^k\pmod m\). Hence \(a^{k+1}\equiv b^{k+1}\pmod m\). So it holds for all \(n\ge 1\), by the PMI.

Proof of (4). Let \(f(x)=c_nx^n+\dotsb+c_1x+c_0\). We prove by induction on \(n\) that if \(a\equiv b\pmod m\) then \[c_na^n+\dotsb+c_0\equiv c_nb^n+\dotsb+c_0\pmod m.\nonumber \] If \(n=0\) we have \(c_0\equiv c_0\pmod m\) by Theorem 15.2 (1). Assume the result holds for \(n=k\). Then we have \[\label{eq:1} c_ka^k+\dotsb+c_1a+c_0\equiv c_kb^k+\dotsb+c_1b+c_0\pmod m. \] By part (3) above we have \(a^{k+1}\equiv b^{k+1}\pmod m\). Since \(c_{k+1}\equiv c_{k+1}\pmod m\) using (2) above we have \[\label{eq:2} c_{k+1}a^{k+1}\equiv c_{k+1}b^{k+1}\pmod m. \] Now we can apply Theorem 15.3 (1) to \(\eqref{eq:1}\) and \(\eqref{eq:2}\) to obtain \[c_{k+1}a^{k+1}+c_ka^k+\dotsb+c_0\equiv c_{k+1}b^{k+1}+c_kb^k+\dotsb+c_0\pmod m.\nonumber\] So by the PMI, the result holds for \(n\ge 0\).

Before continuing to develop properties of congruences, we give the following example to show one way that congruences can be useful.

Example \(\PageIndex{3}\)

(This example was taken from Introduction to Analytic Number Theory, by Tom Apostol.)

The first five Fermat numbers \[F_0=3,\quad F_1=5,\quad F_2=17,\quad F_3=257,\quad F_4=65,537\nonumber \] are primes. We show using congruences without explicitly calculating \(F_5\) that \(F_5=2^{32}+1\) is divisible by \(641\) and is therefore not prime : [apostle] \[\begin{aligned} 2^2 &=4 \\ 2^4 &=\left(2^2\right)^2=4^2=16 \\ 2^8 &=\left(2^4\right)^2=16^2=256 \\ 2^{16} &=\left(2^8\right)^2=256^2=65,536\end{aligned}\] \[65,536\equiv 154\pmod{641}.\nonumber \] So we have \[2^{16}\equiv 154\pmod{641}.\nonumber \] By Theorem 15.3 (3): \[\left(2^{16}\right)^2\equiv (154)^2\pmod{641}.\nonumber \] That is, \[2^{32}\equiv 23,716\pmod{641}.\nonumber \] Since \[23,716\equiv 640\pmod{641}\nonumber \] and \[640\equiv-1\pmod{641}\nonumber \] we have \[2^{32}\equiv-1\pmod{641}\nonumber \] and hence \[2^{32}+1\equiv 0\pmod{641}.\nonumber \] So \(641\mid 2^{32}+1\), as claimed. Clearly \(2^{32}+1\ne 641\), so \(2^{32}+1\) is composite. Of course, if you already did Exercise 12.1 you will already know that \[2^{32}+1=4,294,967,297=(641)\cdot(6,700,417)\nonumber \] and that \(641\) and \(6,700,417\) are indeed primes. Note that \(641\) is the \(116^{th}\) prime, so if you used trial division you would have had to divide by 115 primes before reaching one that divides \(2^{32}+1\), and that assumes that you have a list of the first 116 primes.

Theorem \(\PageIndex{4}\)

If \(m>0\) and \[a\equiv r\pmod m\text{ where }0\le r<m\nonumber \] then \(a\bmod m=r\).

Exercise \(\PageIndex{9}\)

Prove Theorem \(\PageIndex{4}\).

Hint

The Division Algorithm may be useful.

Exercise \(\PageIndex{10}\)

Find the value of each of the following (without using Maple!).

1. \(2^{32}\bmod 7\)
2. \(10^{35}\bmod 7\)
3. \(3^{35}\bmod 7\)

Hint

Use Theorem \(\PageIndex{4}\) and the ideas used in the example

Exercise \(\PageIndex{11}\)

Let \(\gcd\left(m_1,m_2\right)=1\). Prove that \[\label{eq:3} a\equiv b\pmod{m_1}\text{ and }a\equiv b\pmod{m_2}\] if and only if \[\label{eq:4} a\equiv b\pmod{m_1m_2}.\]

Answer

Use Lemma 11.1.