Divisibility

Definition 1.3

𝑎,𝑏\in \mathbb{Z}

with

𝑎\neq 0

, we say that

𝑎

divides

𝑏

if there exists

𝑐\in \mathbb{Z}

such that

𝑏=𝑎𝑐

. If

𝑎

divides

𝑏

, we also say that

𝑎

is a divisor or a factor of

𝑏

and that

𝑏

is a multiple of

𝑎

If $𝑎$ divides $𝑏$ , we write $𝑎∣𝑏$ , and we write $𝑎∤𝑏$ to mean that $𝑎$ does not divide $𝑏$ .

For example, $2∣6$ and $3∣6$ . But $4∤6$ . In fact, all the divisors of $6$ are $\pm 1$ , $\pm 2$ , $\pm 3$ and $\pm 6$ .

There are a few simple properties.

Proposition 1.10Transitivity

𝑎∣𝑏

and

𝑏∣𝑐

, then

𝑎∣𝑐

Proof

Because

𝑎∣𝑏

, we have

𝑏=𝑎𝑑

for some

𝑑\in \mathbb{Z}

. Similarly, there exists

𝑒\in \mathbb{Z}

such that

𝑐=𝑏𝑒

. Therefore,

𝑐=𝑏𝑒=(𝑎𝑑)𝑒=𝑎(𝑑𝑒)

. Since

𝑑𝑒\in \mathbb{Z}

, by definition,

𝑎∣𝑐

A linear combination of integers $𝑎$ and $𝑏$ is the sum of the form

𝑚𝑎+𝑛𝑏

where $𝑚,𝑛\in \mathbb{Z}$ .

If $𝑐∣𝑎$ and $𝑐∣𝑏$ , then $𝑐$ divides any linear combination of $𝑎$ and $𝑏$ .

Proposition 1.11

Suppose that

𝑎,𝑏,𝑚,𝑛\in \mathbb{Z}

. If

𝑐∣𝑎

and

𝑐∣𝑏

, then

𝑐∣(𝑚𝑎+𝑛𝑏)

Proof

We have

𝑎=𝑐𝑑

and

𝑏=𝑐𝑒

where

𝑑,𝑒\in \mathbb{Z}

. It then follows that

𝑚𝑎+𝑛𝑏=𝑚(𝑐𝑑)+𝑛(𝑐𝑒)=𝑐(𝑚𝑑+𝑛𝑒)

. Thus,

𝑐∣(𝑚𝑎+𝑛𝑏)

The Division Algorithm

Theorem 1.5The division algorithm

Let $𝑎,𝑏\in \mathbb{Z}$ with $𝑏>0$ . Then there exist unique $𝑞,𝑟\in \mathbb{Z}$ such that

𝑎=𝑏𝑞+𝑟

(1.10)

where

0\leq 𝑟<𝑏

In (1.10), we call $𝑎$ the dividend, $𝑏$ the divisor, $𝑞$ the quotient, and $𝑟$ the remainder. The theorem, and the proof below, tells us only that $𝑞$ and $𝑟$ exist. It says nothing about how to find them, so it is technically not an algorithm, though the name says it is. We will show the algorithm later.

Proof

Existence. We want to use the well-ordering principle to yield the existence of such an $𝑟$ . Define $𝑆=\{𝑎-𝑏𝑘:𝑘\in \mathbb{Z}\}\cap \mathbb{N}$ . Note that $𝑆\subseteq \mathbb{N}$ , and that $𝑆$ is nonempty. To see this, consider $𝑥=𝑎-𝑏(-|𝑎|)=𝑎+𝑏|𝑎|$ . Since $𝑏>0$ , and hence $𝑏\geq 1$ , we have

𝑥=𝑎+𝑏|𝑎|\geq 𝑎+|𝑎|\geq 0.

Therefore $𝑥\in 𝑆$ , so $𝑆\neq \emptyset$ . By a variant of the well-ordering principle Proposition 1.1, $𝑆$ has a least element $𝑟$ . By the definition of $𝑆$ , there exists $𝑞\in \mathbb{Z}$ such that $𝑟=𝑎-𝑏𝑞$ . (In fact, these $𝑞$ and $𝑟$ are the ones we want.) Clearly $𝑟\geq 0$ . We need to show that $𝑟<𝑏$ . Assume, on the contrary, that $𝑟\geq 𝑏$ . Then

𝑟-𝑏=𝑎-𝑏(𝑞+1).

Since $𝑟-𝑏\geq 0$ , we have $𝑟-𝑏\in 𝑆$ , which contradicts the fact that $𝑟$ is the least element of $𝑆$ . Therefore $0\leq 𝑟<𝑏$ .

Uniqueness. (As a matter of fact, we have already gained the uniqueness of $𝑟$ and of $𝑞$ from the well-ordering principle, since $𝑟$ is the least element of $𝑆$ . But we may as well prove the uniqueness as follows.) Suppose that there exist ${𝑞}_{1},{𝑞}_{2},{𝑟}_{1},{𝑟}_{2}\in \mathbb{Z}$ such that

\begin{aligned}𝑎 & =𝑏{𝑞}_{1}+{𝑟}_{1}, \\ 𝑎 & =𝑏{𝑞}_{2}+{𝑟}_{2},\end{aligned}

with $0\leq {𝑟}_{1},{𝑟}_{2}<𝑏$ and ${𝑟}_{1}\leq {𝑟}_{2}$ . Subtracting the two equations yields

𝑏({𝑞}_{1}-{𝑞}_{2})={𝑟}_{2}-{𝑟}_{1}.

By the given conditions, $0\leq {𝑟}_{2}-{𝑟}_{1}<𝑏$ . Thus

0\leq 𝑏({𝑞}_{1}-{𝑞}_{2})<𝑏.

Dividing by $𝑏$ ,

0\leq {𝑞}_{1}-{𝑞}_{2}<1.

Since ${𝑞}_{1}-{𝑞}_{2}\in \mathbb{Z}$ , we must have ${𝑞}_{1}={𝑞}_{2}$ and hence ${𝑟}_{1}={𝑟}_{2}$ .

We can use the floor function to express the quotient and the remainder:

𝑞=\lfloor 𝑎/𝑏\rfloor \quad \text{and}\quad 𝑟=𝑎-𝑏𝑞=𝑎-𝑏\lfloor 𝑎/𝑏\rfloor .

To see this, divide both sides of (1.10) by $𝑏$ :

𝑎/𝑏=𝑞+𝑟/𝑏.

Since $0\leq 𝑟/𝑏<1$ ,

𝑞\leq 𝑎/𝑏<𝑞+1,

which implies $𝑞=\lfloor 𝑎/𝑏\rfloor$ .

Exercise 1.3

Let $𝑛\in {\mathbb{Z}}^{+}$ and $𝑥\in \mathbb{R}$ . Show that

\lfloor 𝑥/𝑛\rfloor =\lfloor \lfloor 𝑥\rfloor /𝑛\rfloor .

Proof

By Theorem 1.5, there exist $𝑞,𝑟\in \mathbb{Z}$ such that

\lfloor 𝑥\rfloor =𝑛𝑞+𝑟,

where $0\leq 𝑟<𝑛$ . It then follows that

\lfloor 𝑥\rfloor /𝑛=𝑞+𝑟/𝑛.

Since $0\leq 𝑟/𝑛<1$ , we have

\lfloor \lfloor 𝑥\rfloor /𝑛\rfloor =𝑞.

We still need to show that the greatest integer of $𝑥/𝑛$ is also $𝑞$ .

On the other hand, $𝑥$ can be written as

𝑥=\lfloor 𝑥\rfloor +\{𝑥\}.

Thus

𝑥=𝑛𝑞+𝑟+\{𝑥\}.

Dividing by $𝑛$ ,

𝑥/𝑛=𝑞+(𝑟+\{𝑥\})/𝑛.

(1.11)

We want to show that $0\leq (𝑟+\{𝑥\})/𝑛<1$ . But $0\leq 𝑟<𝑛$ and $0\leq \{𝑥\}<1$ only give $0\leq 𝑟+\{𝑥\}<𝑛+1$ , so we need a tighter bound. We prove it by contradiction. Assume that $𝑟+\{𝑥\}\geq 𝑛$ . Then

𝑥=𝑛𝑞+𝑟+\{𝑥\}=𝑛(𝑞+1)+(𝑟+\{𝑥\}-𝑛).

Note that $0\leq 𝑟+\{𝑥\}-𝑛<1$ , so $𝑟+\{𝑥\}-𝑛$ is the fractional part of $𝑥$ . That is,

\lfloor 𝑥\rfloor =𝑛(𝑞+1)=𝑛𝑞+𝑛>𝑛𝑞+𝑟.

But we already have $\lfloor 𝑥\rfloor =𝑛𝑞+𝑟$ . This is a contradiction, so $𝑟+\{𝑥\}<𝑛$ . It then follows from (1.11) that

\lfloor 𝑥/𝑛\rfloor =𝑞.

This concludes the proof.

We are all familiar with even and odd numbers, maybe starting from kindergarten or elementary school. Ask yourself: what is an even number, and what is an odd number? “Divisible by $2$ ” could be one approach. Then how do we get that an even number has the form $2𝑘$ and an odd number the form $2𝑘+1$ ?

Below we give a clear definition.

Definition 1.4

An integer

𝑛\in \mathbb{Z}

is even if its remainder when divided by

2

0

. And

𝑛

is odd if its remainder when divided by

2

1

We can then answer the $2𝑘$ and $2𝑘+1$ question using the division algorithm Theorem 1.5.

If $𝑛$ is even, then by Theorem 1.5 there exists $𝑘\in \mathbb{Z}$ such that $𝑛=2𝑘$ . On the other hand, the remainder when $2𝑘$ is divided by $2$ is $0$ . Therefore $𝑛$ is even if and only if $𝑛=2𝑘$ for some $𝑘\in \mathbb{Z}$ .

Similarly, $𝑛$ is odd if and only if $𝑛=2𝑘+1$ for some $𝑘\in \mathbb{Z}$ .

Greatest Common Divisors

The concept of the greatest common divisor is crucial in number theory. If integers $𝑎$ and $𝑏$ are not both zero, then at least one of the sets of factors $𝐴$ and $𝐵$ is finite. (The set of factors of $0$ is $\mathbb{Z}$ , which is infinite.) Thus the set of common divisors $𝐴\cap 𝐵$ is finite, and hence it is feasible to take the maximum element of $𝐴\cap 𝐵$ , $\max (𝐴\cap 𝐵)$ , which is the greatest common divisor.

Definition 1.5

Let

𝑎,𝑏\in \mathbb{Z}

, not both zero. The greatest common divisor

𝑑

𝑎

and

𝑏

is the largest integer that divides both

𝑎

and

𝑏

. We write

𝑑=\gcd (𝑎,𝑏)

Here are some examples: $\gcd (4,6)=2$ , $\gcd (3,6)=3$ , $\gcd (4,9)=1$ , $\gcd (4,-6)=2$ , and $\gcd (0,𝑛)=|𝑛|$ for every nonzero integer $𝑛$ .

We are particularly interested in pairs of integers that share no common divisor larger than $1$ . Equivalently, the only common divisors are $\pm 1$ .

Definition 1.6

Let

𝑎,𝑏\in \mathbb{Z}

with

𝑎\neq 0

and

𝑏\neq 0

. We say that

𝑎

and

𝑏

are coprime if

\gcd (𝑎,𝑏)=1

Exercises

Exercise 1.4

Show that

\left\lfloor {\left(2+\sqrt{3}\right)}^{𝑛}\right\rfloor

is an odd number for any

𝑛\in \mathbb{N}

Hint: This is a very interesting exercise in that you need to apply the method of construction. Recall the linear recurrence relation of degree $2$ .

Proof

Let sequences $\{{𝑥}_{𝑛}\}$ and $\{{𝑦}_{𝑛}\}$ be defined by

{𝑥}_{𝑛}={\left(2+\sqrt{3}\right)}^{𝑛}\quad \text{and}\quad {𝑦}_{𝑛}={\left(2-\sqrt{3}\right)}^{𝑛},\quad 𝑛\in \mathbb{N}.

And let

{𝑎}_{𝑛}={𝑥}_{𝑛}+{𝑦}_{𝑛}={\left(2+\sqrt{3}\right)}^{𝑛}+{\left(2-\sqrt{3}\right)}^{𝑛},\quad 𝑛\in \mathbb{N}.

Our goal is to show that $\lfloor {𝑥}_{𝑛}\rfloor$ is odd. A quick observation: $0<2-\sqrt{3}<1$ , and hence $0<{𝑦}_{𝑛}<1$ for all $𝑛\geq 1$ . As $𝑛$ gets larger, ${𝑦}_{𝑛}$ may be neglected. So ${𝑥}_{𝑛}$ mainly contributes to ${𝑎}_{𝑛}$ . In fact, we want to show that ${𝑎}_{𝑛}$ is an integer, and moreover even.

Note that $2+\sqrt{3}$ and $2-\sqrt{3}$ are the two roots of the equation

{\lambda }^{2}=4\lambda -1.

Thus, by Proposition 1.9, the sequence $\{{𝑎}_{𝑛}\}$ satisfies the recurrence

{𝑎}_{𝑛}=4{𝑎}_{𝑛-1}-{𝑎}_{𝑛-2},\quad 𝑛\geq 2.

We may find ${𝑎}_{0}$ and ${𝑎}_{1}$ :

\begin{aligned}{𝑎}_{0} & ={𝑥}_{0}+{𝑦}_{0}=1+1=2, \\ {𝑎}_{1} & ={𝑥}_{1}+{𝑦}_{1}=2+\sqrt{3}+2-\sqrt{3}=4.\end{aligned}

It is easy to show by mathematical induction that ${𝑎}_{𝑛}$ is even for all $𝑛$ .

Since $0<{𝑦}_{𝑛}\leq 1$ , we have

{𝑥}_{𝑛}<\underbrace{{𝑥}_{𝑛}+{𝑦}_{𝑛}}_{={𝑎}_{𝑛}}\leq {𝑥}_{𝑛}+1.

Rearrange the terms:

{𝑎}_{𝑛}-1\leq {𝑥}_{𝑛}<{𝑎}_{𝑛}=({𝑎}_{𝑛}-1)+1.

This exactly says that

\lfloor {𝑥}_{𝑛}\rfloor ={𝑎}_{𝑛}-1.

Since ${𝑎}_{𝑛}$ is even, $\lfloor {𝑥}_{𝑛}\rfloor$ is odd.