1.17: 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 1.5.3. We shall see that the two uses of mod are related, but have different meanings: Recall

\[\boxed{\begin{array}{l}a\pmod b=r\text{ where }r\text{ is the remainder given by }\\ \text{the Division Algorithm when }a\text{ is divided by }b,\end{array}}\nonumber\]

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

Example \(\PageIndex{2}\)

The statement \[25\equiv 5\pmod 4\text{ is true}\, ,\nonumber \] since \(4\mid 20\) but \[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\) is, together with the \(\equiv\), part of 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 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\). If \(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.

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

Theorem \(\PageIndex{2}\)

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

of (1) See Exercise \(\PageIndex{1}\).

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\).

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

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 \]

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 \(ca\equiv bd\pmod m\), as desired.

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.

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 \(\PageIndex{2}\) (1). Assume the result holds for \(n=k\). Then we have \[\label{eq: thm 17-3 first} 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: thm 17-3 second} c_{k+1}a^{k+1}\equiv c_{k+1}b^{k+1}\pmod m.\] Now we can apply Theorem \(\PageIndex{3}\) (1) to equations \(\eqref{eq: thm 17-3 first}\) and \(\eqref{eq: thm 17-3 second}\) 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 [1] 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 \(\PageIndex{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 1.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^{\rm 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 this 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\).

Exercises

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 if and only if \(a\equiv 0\pmod 2\), and \(a\) is odd if and only if \(a\equiv 1\pmod 2\).
2. Show that \(a\) is even if and only if \(a \bmod 2 = 0\), and \(a\) is odd if and only if \(a \bmod 2 = 1\).

(Note: your answers to parts (a) and (b) will be similar, but they should not be identical! Make every effort to use the vocabulary correctly.)

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 three separate pairs \(a,b\) of integers 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 \]

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 a computer!).

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 Example \(\PageIndex{3}\).)

Exercise \(\PageIndex{11}\)

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

(Hint: use Lemma 1.12.1.)