5.1: Number Theory- Divisibility and Congruence

In this section, we will get some practice with proving properties of integers.

5.1A. Divisibility.

Every math student knows that some numbers are even and some numbers are odd; some numbers are divisible by 3, and some are not; etc. Let us introduce a notation that makes it easy to talk about whether or not one number \(b\) is divisible by some other number \(a\):

Definition \(5.1.1\).

Suppose \(a, b \in \mathbb{Z}\). We say \(a\) is a divisor of \(b\) (and write “\(a \mid b\)”) iff there exists \(k \in \mathbb{Z}\), such that \(ak = b\). (Since multiplication is commutative and equality is symmetric, this equation can also be written as \(b = ka\).)

Notation \(5.1.2\).

\(a \nmid b\) is an abbreviation for “\(a\) does not divide \(b\).”

Remark \(5.1.3\).

When \(a\) is a divisor of \(b\), we may also say:

1. \(a\) divides \(b\), or
2. \(a\) is a factor of \(b\), or
3. \(b\) is a multiple of \(a\), or
4. \(b\) is divisible by \(a\).

Example \(5.1.4\).

1. We have \(5 \mid 30\), because \(5 \cdot 6=30\), and \(6 \in \mathbb{Z}\).
2. We have \(5 \nmid 27\), because there is no integer \(k\), such that \(5k = 27\).

Exercise \(5.1.5\).

Fill each blank with \(\mid\) or \(\nmid\), as appropriate.

1. 3________18
2. 4________18
3. 5________18
4. 6________18
5. 18________6
6. −6________6

The following definition is perhaps the best known example of divisibility.

Definition \(5.1.6\).

Let \(n \in \mathbb{Z}\). We say \(n\) is even iff \(2 \mid n\). We say \(n\) is odd iff \(2 \nmid n\).

Here are some examples of proofs involving divisibility. We will assume the well-known fact that the sum, difference, and product of integers are integers: for all \(k_{1}, k_{2} \in \mathbb{Z}\), we know that \(k_{1}+k_{2} \in \mathbb{Z}, k_{1}-k_{2} \in \mathbb{Z}\), and \(k_{1} k_{2} \in \mathbb{Z} .\) Also, the negative of any integer is an integer: for all \(k \in \mathbb{Z}\), we have \(−k \in \mathbb{Z}\).

Our first result is a generalization of the well-known fact that the sum of two even numbers is even.

Proposition \(5.1.7\).

Suppose \(a, b_{1}, b_{2} \in \mathbb{Z}\). If \(a \mid b_{1}\) and \(a \mid b_{2}\), then \(a \mid\left(b_{1}+b_{2}\right)\).

Scratchwork. Since \(a \mid b_{1}\) and \(a \mid b_{2}\), we know there is some \(k \in \mathbb{Z}\), such that \(ak = b_{1}\), and we know there is some \(k \in \mathbb{Z}\), such that \(ak = b_{2}\). However, these are probably two different values of \(k\), so we need to give them different names if we want to talk about both of them at the same time. So let’s call the first one \(k_{1}\) and the second one \(k_{2}\):

• there exists \(k_{1} \in \mathbb{Z}\), such that \(a k_{1}=b_{1}\), and
• there exists \(k_{2} \in \mathbb{Z}\), such that \(a k_{2}=b_{2}\).

To show \(a \mid\left(b_{1}+b_{2}\right)\), we want to find some \(k \in \mathbb{Z}\), such that \[a k \stackrel{?}{=} b_{1}+b_{2} .\]
Since \(b_{1}+b_{2}=a k_{1}+a k_{2}=a\left(k_{1}+k_{2}\right)\), this means we want \[a k \stackrel{?}{=} a\left(k_{1}+k_{2}\right) .\]
So it is clear that we should let \(k = k_{1} + k_{2}\).

Proof

Since, by assumption, a is a divisor of both \(b_{1}\) and \(b_{2}\), there exist \(k_{1}, k_{2} \in \mathbb{Z}\), such that \(a k_{1}=b_{1}\) and \(a k_{2}=b_{2}\). Let \(k = k_{1} + k_{2}\). Then \(k \in \mathbb{Z}\) and \[a k=a\left(k_{1}+k_{2}\right)=a k_{1}+a k_{2}=b_{1}+b_{2} ,\]

so \(a\) is a divisor of \(b_{1} + b_{2}\), as desired.

Proposition \(5.1.8\).

Suppose \(a, b \in \mathbb{Z}\). We have \(a \mid b\) iff \(a \mid −b\).

Scratchwork.

(\(\Rightarrow\)) Since \(a \mid b\), we know there is some \(k\), such that \(ak = b\). To show \(a \mid −b\), we want to find some other \(k\) — let’s call it \(k^{\prime}\) — such that \(a k^{\prime} \stackrel{?}{=}-b\). Since \(-b=-(a k)=a(-k)\), this means we want \(a k^{\prime} \stackrel{?}{=} a(-k)\). So we should let \(k^{\prime} = −k\).

(\(\Leftarrow\)) Since \(a \mid −b\), we know there is some \(k\), such that \(ak = −b\). To show \(a \mid b\), we want to find some \(k^{\prime}\), such that \(a k^{\prime} \stackrel{?}{=} b .\) Since \(−b = ak\), we have \(b = −(ak) = a(−k)\), so we can let \(k^{\prime} = −k\). This is the same work as in the proof of (\(\Rightarrow\)), and the official proof given below avoids the need for repeating this algebra, by appealing to the result that we have already proved.

Proof

(\(\Rightarrow\)) By assumption, there is some \(k \in \mathbb{Z}\), such that \(ak = b\). Then \(−k \in \mathbb{Z}\), and we have \(a(−k) = −ak = −b\), Therefore, \(a\) divides \(−b\).

(\(\Leftarrow\)) Assume \(a \mid −b\). From the preceding paragraph, we conclude that \(a \mid −(−b) = b\), as desired.

Exercise \(5.1.9\).

Assume \(a, a^{\prime} , b, b^{\prime} \in \mathbb{Z}\).

1. Show that if \(a \mid b\) and \(a \mid b^{\prime}\), then \(a \mid b - b^{\prime}\).
2. Show that \(a \mid b\) iff \(−a \mid b\).
3. Show \(1 \mid b\).
4. Show \(a \mid 0\).
5. Show that if \(0 \mid b\), then \(b = 0\).
6. Show that if \(a \mid b\), then \(a | bb^{\prime}\).
7. Show that if \(a \mid b\) and \(a^{\prime} \mid b^{\prime}\), then \(a a^{\prime} \mid b b^{\prime}\).

Proposition \(5.1.10\).

Suppose \(a, b_{1}, b_{2} \in \mathbb{Z}\). If \(a \mid b_{1}\) and \(a \nmid b_{2}\), then \(a \nmid\left(b_{1}+b_{2}\right)\).

Proof

Assume \(a \mid b_{1}\) and \(a \nmid b_{2}\).

Suppose \(a \mid\left(b_{1}+b_{2}\right)\). (This will lead to a contradiction.) Then \(a\) is a divisor of both \(b_{1} +b_{2}\) and (by assumption) \(b_{1}\). So Exercise \(5.1.9(1)\) tells us \[a \mid\left(\left(b_{1}+b_{2}\right)-b_{1}\right)=b_{2}\]
This contradicts the assumption that \(a \nmid b_{2}\).

Because it leads to a contradiction, our hypothesis that \(a \mid\left(b_{1}+b_{2}\right)\) must be false. This means \(a \nmid\left(b_{1}+b_{2}\right) .\)

It is well known that 1 and −1 are the only integers whose reciprocal is also an integer. In the language of divisibility, this can be restated as the following useful fact: \[\text { For any integer } n \text {, we have } n \mid 1 \text { iff } n=\pm 1 \text {. }\]

Exercise \(5.1.11\).

Prove:

1. For all \(a \in \mathbb{Z}\), we have \(a \mid a\).
2. For all \(a, b, c \in \mathbb{Z}\), if \(a \mid b\) and \(b \mid c\), then \(a \mid c\).
3. It is not true that, for all \(a, b \in \mathbb{Z}\), we have \(a \mid b\) iff \(b \mid a\).

Remark \(5.1.12\).

The three parts of the preceding exercise show that divisibility is “reflexive” and “transitive,” but not “symmetric.” These terms will be defined in Definition \(7.1.9\).

Exercise \(5.1.13\).

Assume \(a, b, x, y \in \mathbb{Z}\). Prove:

1. If \(a \mid x\) and \(b \mid y\), then \(ab \mid 2xy\).
2. If \(a, b \in \mathbb{N}^{+}\), and \(a \mid b\), then \(a \leq b\).

Exercise \(5.1.14\).

Prove or disprove each assertion.

1. For all \(a, b_{1}, b_{2} \in \mathbb{Z}\), if \(a \nmid b_{1}\) and \(a \nmid b_{2}\), then \(a \nmid\left(b_{1}+b_{2}\right)\).
2. For all \(a, b_{1}, b_{2} \in \mathbb{Z}\), if \(a \nmid b_{1}\) and \(a \nmid b_{2},\), then \(a \nmid b_{1} b_{2}\).
3. For all \(a, b, c \in \mathbb{Z} \text {, }\) if \(a \nmid b\) and \(b \nmid c\), then \(a \nmid c\).
4. For all \(a, b \in \mathbb{Z}\), if \(a \nmid b\), then \(a \nmid −b\).

5.1B. Congruence modulo \(n\).

Definition \(5.1.15\).

Suppose \(a, b, n \in \mathbb{Z}\). We say \(a\) is congruent to \(b\) modulo \(n\) iff \(a − b\) is divisible by \(n\). The notation for this is: \(a \equiv b(\bmod n)\).

Example \(5.1.16\).

1. We have \(22 \equiv 0(\bmod 2)\), because \(22 − 0 = 22 = 11 \times 2\) is a multiple of 2. (More generally, for \(a \in \mathbb{Z}\), one can show that \(a \equiv 0 (\bmod 2)\) iff \(a\) is even.)
2. We have \(15 \equiv 1 (\bmod 2)\), because \(15 − 1 = 14 = 7 \times 2\) is a multiple of 2. (More generally, for \(a \in \mathbb{Z}\), one can show that \(a \equiv 1 (\bmod 2)\) iff \(a\) is odd.)
3. We have \(28 \equiv 13 (\bmod 5)\), because \(28 − 13 = 15 = 3 \times 5\) is a multiple of 5.
4. For any \(a, n \in \mathbb{Z}\), it is not difficult to see that \(a \equiv 0 (\bmod n)\) iff \(a\) is a multiple of \(n\).

Exercise \(5.1.17\).

Fill each blank with \(\equiv\) or \(\not \equiv\), as appropriate.

1. 14______5 \((\bmod 2)\)
2. 14______5 \((\bmod 3)\)
3. 14______5 \((\bmod 4)\)
4. 14______32 \((\bmod 2)\)
5. 14______32 \((\bmod 3)\)
6. 14______32 \((\bmod 4)\)

Exercise \(5.1.18\).

(“Congruence modulo \(n\) is reflexive, symmetric, and transitive.”) Let \(n \in \mathbb{Z}\). Prove:

1. For all \(a \in \mathbb{Z}\), we have \(a \equiv a (\bmod n)\).
2. For all \(a, b \in \mathbb{Z}\), we have \(a \equiv b (\bmod n)\) iff \(b \equiv a (\bmod n)\).
3. For all \(a, b, c \in \mathbb{Z}\), if \(a \equiv b (\bmod n)\) and \(b \equiv c (\bmod n)\), then \(a \equiv c (\bmod n)\).

Exercise \(5.1.19\).

Assume \(a_{1} \equiv a_{2} (\bmod n)\) and \(b_{1} \equiv b_{2} (\bmod n)\). Show:

1. \(a_{1}+b_{1} \equiv a_{2}+b_{2}(\bmod n)\).
2. \(a_{1}-b_{1} \equiv a_{2}-b_{2}(\bmod n)\).
3. \(a_{1} b_{1} \equiv a_{2} b_{2}(\bmod n)\). [Hint: \(a_{1} b_{1}-a_{2} b_{2}=a_{1}\left(b_{1}-b_{2}\right)+\left(a_{1}-a_{2}\right) b_{2}\).]

Children are taught that if a number \(a\) is divided by a number \(n\), then there may be a remainder, but the remainder is always smaller than \(n\). That idea is said more precisely in the following theorem:

Theorem \(5.1.20\) (Division Algorithm).

Suppose \(a, n \in \mathbb{Z}\), and \(n \neq 0\). Then there exist unique integers \(q\) and \(r\) in \(\mathbb{Z}\), such that:

1. \(a = qn + r\), and
2. \(0 \leq r < |n|\).

Definition \(5.1.21\).

In the situation of Theorem \(5.1.20\), the number \(r\) is called the remainder when \(a\) is divided by \(n\).

The following exercise reveals the close relationship between congruence and remainders.

Exercise \(5.1.22\).

Suppose \(a, b, n \in \mathbb{Z}\) (and \(n \neq 0\)).

1. Let \(r\) be the remainder when \(a\) is divided by \(n\). Show \(a \equiv r (\bmod n)\).
2. Show that \(a \equiv b (\bmod n)\) iff \(a\) and \(b\) have the same remainder when divided by \(n\).

Remark \(5.1.23\).

From the second half of parts (1) and (2) of Example \(5.1.16\), we see that every integer is congruent to either 0 or 1 modulo 2 (and not both).

\(n\) is even iff \(n \equiv 0 (\bmod 2)\).
\(n\) is odd iff \(n \equiv 0 (\bmod 2)\).

Exercise \(5.1.22(1)\) generalizes this to congruence modulo numbers other than 2: if \(n \equiv \mathbb{N}^{+}\), then every integer is congruent (modulo \(n\)) to some number in \(\{0,1,2, \ldots, n-1\}\).

Example \(5.1.24\).

Let us show that if \(n\) is odd, then \(9n+ 6\) is also odd. To see this, note that:

• \(9 \equiv 1 (\bmod 2)\), because \(9 = 4(2) + 1\),
• \(n \equiv 1 (\bmod 2)\), because \(n\) is odd, and
• \(6 \equiv 0 (\bmod 2)\), because \(6 = 3(2) + 0\).

Therefore, using Exercise \(5.1.19\), we have \(9n + 6 \equiv (1)(1) + 0 \equiv 1 (\bmod 2)\).

The same method can be applied in the following exercises:

Exercise \(5.1.25\).

Let \(n \in \mathbb{Z}\).

1. Show \(6n + 3\) is odd.
2. Show that if \(n\) is even, then \(5n + 3\) is odd.
3. Show that if \(n\) is odd, then \(5n + 3\) is even.

Proposition \(5.1.26\).

Let \(n \in \mathbb{Z}\). Then \(n^{2} + n\) is even.

Proof

From Remark \(5.1.23\), we know that \(n\) is congruent to either 0 or 1 modulo 2. We consider these two possibilities as separate cases.

Case 1. Assume \(n \equiv 0 (\bmod 2)\). By the assumption of this case, we have \(n = 2q\), for some \(q \in \mathbb{Z}\). Therefore \[n^{2}+n=(2 q)^{2}+2 q=4 q^{2}+2 q=2\left(2 q^{2}+q\right)\]
is divisible by 2.

Case 2. Assume \(n \equiv 1 (\bmod 2)\). By the assumption of this case, we have \(n = 2q + 1\), for some \(q \in \mathbb{Z}\). Therefore \[n^{2}+n=(2 q+1)^{2}+(2 q+1)=\left(4 q^{2}+4 q+1\right)+(2 q+1)=4 q^{2}+6 q+2=2\left(2 q^{2}+3 q+1\right)\]
is divisible by 2.

Exercise \(5.1.27\).

Let \(n \in \mathbb{Z}\).

1. Show that if \(n\) is even, then \(n^{2} \equiv 0 (\bmod 4)\). [Hint: We have \(n = 2q\), for some \(q \in \mathbb{Z}\).]
2. Show that if \(n\) is odd, then n 2 ≡ 1 (mod 8). [Hint: We have n = 2q + 1, for some q ∈ Z.]
3. Show that if \(n^{2}\) is even, then \(n\) is even.

5.1C. Examples of Irrational Numbers.

Every rational number is a real number (in other words, \(\mathbb{Q} \subset \mathbb{R}\)), but it is perhaps not so obvious that some real numbers are not rational (in other words, \(\mathbb{R} \not \subset \mathbb{Q}\)). Such numbers are said to be irrational. We now give one of the simplest examples of an irrational number.

Proposition \(5.1.28\).

\(\sqrt{2}\) is irratioinal.

Proof

BY CONTRADICTION.

Suppose \(\sqrt{2}\) is rational. (This will lead to a contradiction.) By definition, this means \(\sqrt{2}=a / b\) for some \(a, b \in \mathbb{Z}\), with \(b \neq 0\). By reducing to lowest terms, we may assume that \(a\) and \(b\) have no common factors. In particular, \[\text { it is not the case that both } a \text { and } b \text { are even. }\]
We have \[\frac{a^{2}}{b^{2}}=\left(\frac{a}{b}\right)^{2}=\sqrt{2}^{2}=2 ,\]
so \(a^{2}=2 b^{2}\) is even. Then Exercise \(5.1.27(3)\) tells us that \[a \text { is even, }\]
so we have \(a = 2k\), for some \(k \in \mathbb{Z}\). Then \[2 b^{2}=a^{2}=(2 k)^{2}=4 k^{2} ,\]
so \(b^{2} = 2k^{2}\) is even. Then Exercise \(5.1.27(3)\) tells us that \[b \text { is even. }\]
We have now shown that \(a\) and \(b\) are even, but this contradicts the fact, mentioned above, that it is not the case that both \(a\) and \(b\) are even.

Exercise \(5.1.29\).

1. For \(n \in \mathbb{Z}\), show that if \(3 \nmid n\), then \(n^{2} \equiv 1(\bmod 3)\).
2. Show that \(\sqrt{3}\) is irrational.
3. Is \(\sqrt{4}\) irrational?

Remark \(5.1.30\).

The famous numbers \(\pi=3.14159 \ldots\) and \(e=2.71828 \ldots\) are also irrational, but these examples are much harder to prove than Proposition \(5.1.28\).