Divisibility

Divisibility

Let $a,b$ be two integers, with $b\ne 0$. From the Division Algorithm, we know there exist unique integers $q,r$ such that:

$$a=bq+r,0\le r<|b|.$$

Well, the smallest possible value for $r$ is $0$, we will give a special name for this case.

Definition

Let $a,b$ be integers, with $b\ne 0$. We say $b$ divides $a$ if there exists an integer $q$ such that:

$$a=bq.$$

We denote this by $b\mid a$.

If $b\mid a$, we say $b$ is a divisor of $a$, and $a$ is a multiple of $b$.

Question

Can you spell out the definition for $b\nmid a$?

Example

Let $a=12$ and $b=3$. We have:

$$12=3\times 4.$$

Therefore, $3\mid 12$.

Example

Let $a=12$ and $b=5$. We have:

$$12=5\times 2+2.$$

Therefore, $5\nmid 12$.

Properties of Divisibility

We list the following properties of divisibility, which can be easily proved using the definition of divisibility.

1. For any integer $a$, we have $1\mid a$ and $a\mid a$.
2. For any integer $b$, we have $b\mid 0$.
3. If $b\mid a$, then $b\mid -a$.
4. If $b\mid a$, then $(-b)\mid a$.
5. If $c\mid b$ and $b\mid a$, then $c\mid a$.
6. Divisibility is stable under linear combination: If $c\mid a$ and $c\mid b$, then $c\mid (ax+by)$ for any integers $x,y$.
7. If $b\mid a$ and $a\ne 0$, then $|b|\le |a|$.
8. A nonzero integer $a$ has only finitely many divisors.

Greatest Common Divisor

Since for non-zero integers $a$ and $b$, there are only finitely many divisors, we can define the greatest common divisor of $a$ and $b$. Let’s begin with the example:

Example

Let $a=12$, we can list all its positive divisors:

$$\{1,2,3,4,6,12\}.$$

Let $b=18$, we can list all its positive divisors:

$$\{1,2,3,6,9,18\}.$$

We find the common positive divisors of $a$ and $b$ are:

$$\{1,2,3,6\}.$$

Among them, the greatest one is $6$. Therefore, we say the greatest common divisor of $12$ and $18$ is $6$, denoted as $\gcd (12,18)=6$.

We can formally define the greatest common divisor as follows:

Definition

Let $a$ and $b$ be two integers, not both $0$. The greatest common divisor of $a$ and $b$ is the largest positive integer that divides both $a$ and $b$. We denote it as $\gcd (a,b)$, sometimes also denoted as $\gcd (a,b)=(a,b)$.

Let $d=\gcd (a,b)$. We have the following properties by definition:

1. $d\mid a$ and $d\mid b$.
2. If $c\mid a$ and $c\mid b$, then $c\le d$.
3. $d\ge 1$.

In fact, we can strengthen the second property to be $c\mid d$, we will prove this in the next section.

When the greatest common divisor of $a$ and $b$ is the minimal possible value $1$, we say $a$ and $b$ are relatively prime.

Greatest Common Divisor as Linear Combination

We will use the following property extensively when dealing with linear combinations:

Proposition

Let $x$ be a linear combination of $a$ and $b$, let $y$ be a linear combination of $a$ and $b$. Then linear combination of $x$ and $y$ is also a linear combination of $a$ and $b$.

The proof will leave as an exercise.

In the above example, we found $\gcd (12,18)=6$. We can write this as a linear combination of $12$ and $18$:

$$6=12\times 1+18\times (-1).$$

We will show that this is always possible for any two integers $a$ and $b$ such that $ab\ne 0$. The idea is again similar with the proof idea in the division algorithm.

Theorem

Let $a$ and $b$ be two integers, not both $0$. Then there exist integers $m$ and $n$ such that:

$$\gcd (a,b)=am+bn.$$

Proof of the Theorem

Consider the set:

$$S=\{am+bn\mid m,n\in \mathbb{Z}\}.$$

Let $S_{+}=S\cap {\mathbb{Z}}_{>0}$. We know $S_{+}$ is nonempty, since we can take:

$$m=a,n=b.$$

Therefore, by the Well-Ordering Axiom, $S_{+}$ has a smallest element, denote it as $d_0=a{m}_0+b{n}_0$. We will show that $gcd(a,b)=d_0$.

We need to show the following two things:

1. $d_0\mid a$ and $d_0\mid b$.
2. If $c\mid a$ and $c\mid b$, then $c\le d_0$.

Proof of the First Assertion

The first assertion is symmetric for $a,b$, we only show $d_0\mid a$. Apply the Division Algorithm to $a,d_0$, we have:

$$\begin{array}{rl}a& =d_0\cdot q+r,0\le r<d_0.\end{array}$$

Use above proposition, this implies we can write $r$ as a linear combination of $a$ and $b$. So $r\in S$, but $r<d_0$, and $d_0$ is the smallest element in $S_{+}$, we must have $r\notin S_{+}$. This implies $r\in {\mathbb{Z}}_{\le 0}$, and we know $r\ge 0$, so $r=0$. This implies $d_0\mid a$.

Proof of the Second Assertion

For the second one, let $d_1\mid a$ and $d_1\mid b$. We can write $a=d_1{q}_1$ and $b=d_1{q}_2$. Then we have:

$$d_0=a{m}_0+b{n}_0=d_1(q_1{m}_0+q_2{n}_0).$$

Then this implies $d_1\mid d_0$. Since $d_0>0$, we have $d_1\le d_0$. $■$

Corollaries

From the proof of the theorem, we can see the promised corollary:

Corollary

Let $a$ and $b$ be two integers, not both $0$. Then for any integer $c$ such that $c\mid a$ and $c\mid b$, we have $c\mid \gcd (a,b)$.

Another thing we can prove now is the understanding of the relative prime condition. The following corollary illustrated coprime (synonym for relatively prime) integers has a mutex property for its factors:

Corollary

If $a\mid bc$ and $\gcd (a,b)=1$, then $a\mid c$.

Proof of the Corollary

Since $\gcd (a,b)=1$, we can write $1=am+bn$ for some integers $m$ and $n$. Multiply both sides by $c$, we have:

$$c=acm+bcn.$$

Since $a\mid acm$ and $a\mid bcn$, we have $a\mid c$. $■$