# 5.1: Number Theory- Divisibility and Congruence

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

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

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

This page titled 5.1: Number Theory- Divisibility and Congruence is shared under a CC BY-NC-SA 2.0 license and was authored, remixed, and/or curated by Dave Witte Morris & Joy Morris.