Divisibility

Definition. If a and b are integers with $a \ne 0$ , then a divides b if $an = b$ for some integer n. $a \mid b$ means "a divides b". In this case, a is a factor or a divisor of b.

The notation $a \notdiv b$ means a does not divide b.

Notice that divisibility is defined in terms of multiplication --- there is no mention of a "division" operation. The definition agrees with ordinary usage: For example, 12 divides 48, because $12\cdot 4 = 48$ .

The requirement that $a \ne 0$ is included to avoid the following annoyance: $0\cdot 1 = 0$ , so if $a = 0$ is allowed, I'd conclude that 0 is divisible by 0. Taken in and of itself, there's no reason why I can't define "divides" in this way. However, this leads to odd results when you remember that the integers are contained in the rational numbers. In $\rational$ , $12\cdot 4 = 48$ means that $\dfrac{48}{12} = 4$ . But $0\cdot 1 = 0$ would not mean "$\dfrac{0}{0} = 1$ " --- in fact, "$\dfrac{0}{0}$ " cannot be defined in $\rational$ in a manner that's consistent with the definition of $\rational$ .

Here are some things to keep in mind when writing proofs involving divisibility:

Lemma. Let a, b, and c be integers.

  1. If $a \mid b$ and $b \mid c$ , then $a \mid c$ .
  2. If $a \mid x$ and $a \mid y$ , then $a \mid (bx + cy)$ for all $b, c \in \integer$ .

Proof. (a) Suppose $a \mid b$ and $b \mid c$ . $a \mid b$ means that $am = b$ for some m; $b \mid c$ means that $bn = c$ for some n. Hence, $amn = c$ , so $a \mid c$ .

(b) Suppose $a \mid x$ and $a \mid y$ . $a \mid x$ means that $am = x$ for some m; $a \mid y$ means that $an = y$ for some n. Then

$$bx + cy = bam + can = a(bm + cn), \quad\hbox{so}\quad a \mid bx + cy.\quad\halmos$$

An expression of the form $bx + cy$ is called a linear combination of x and y.

Here are two special cases of part (b):

Definition. An integer $n > 1$ is prime if the only positive divisors of n are 1 and n. An integer $n > 1$ which is not prime is composite.

For example,

$$2, 3, 5, 7, 11, 13, \ldots$$

are prime. On the other hand,

$$4, 6, 8, 9, 10, \ldots$$

are composite.

Lemma. If n is composite, then there are integers a and b such that $1 < a, b < n$ and $n = ab$ .

Proof. Since n is composite, it is not prime. Therefore, n has a positive divisor a other than 1 and n. Suppose $n = ab$ . I still have to show that $1 < a, b < n$ .

Note that if $b = 1$ , then $a = n$ (contradiction), and if $b = n$ , then $a = 1$ (contradiction). So a and b are both different from 1 and n.

Suppose on the contrary that $a > n$ . Since $b > 1$ , it follows that

$$n = ab > n\cdot 1 = n.\quad\contra$$

Likewise, if $b > n$ , then since $a > 1$ , I have

$$n = ab > 1\cdot n = n.\quad\contra$$

Now I know that a and b are positive integers which are not greater than n, and neither is 1 or n. This implies that $1 < a, b < n$ .

Lemma. Every integer $n > 1$ has a prime factor.

Proof. I'll use induction, starting with $n = 2$ . In fact, 2 has a prime factor, namely 2.

Suppose that $n > 2$ , and that every integer k less than n has a prime factor. I must show that n has a prime factor.

If n is prime, then n has a prime factor, namely itself. So assume n is composite.

By the last lemma, there are integers a and b such that $1 < a, b < n$ and $n = ab$ . If either a or b is prime, then I have a prime factor of n. Suppose then that a and b are both composite. In this case, since $a < n$ , I know that a must have a prime factor, by induction. But a prime factor of a is a prime factor of n, by transitivity of divisibility. This completes the induction step, and the proof.

The proof of the following result is essentially that given in Book IX of Euclid's Elements.

Theorem. There are infinitely many primes.

Proof. Suppose on the contrary that there are only finitely many primes

$$p_1, p_2, \ldots, p_n.$$

Consider the number

$$p_1p_2\cdots p_n + 1.$$

When this number is divided by $p_1$ , $p_2$ , ..., $p_n$ , it leaves a remainder of 1. Therefore, it has no prime factors. This contradicts the preceding lemma. Hence, there must be infinitely many primes.

The situation changes greatly if you consider primes of a restricted form. For example, it's not known whether there are infinitely many Mersenne primes --- primes of the form $2^n - 1$ , where $n > 1$ .

Lemma. If n is composite, then it has a prime factor p such that $p \le \sqrt{n}$ .

Proof. First, an earlier lemma show that there are integers a and b such that $1 < a, b < n$ and $n = ab$ . If $a > \sqrt{n}$ and $b > \sqrt{n}$ , then $n = ab > (\sqrt{n})(\sqrt{n}) = n$ , which is a contradiction. Therefore, a and b can't both be greater than $\sqrt{n}$ .

Suppose without loss of generality that $a \le \sqrt{n}$ . Then either a is prime or a has a prime factor, by the preceding lemma. In either case, I have a prime less than or equal to $\sqrt{n}$ which divides a, and hence divides n.

Example. The last lemma is the basis of a simple test for primality. To test whether n is prime, divide n in succession by the primes less than $\sqrt{n}$ . If no such prime divides n, then n is prime.

For example, $\sqrt{163} \approx 12.76715$ . By trial, I find that

$$2 \notdiv 163, \quad 3 \notdiv 163, \quad 5 \notdiv 163, \quad 7 \notdiv 163, \quad 11 \notdiv 163.$$

Since these are all the primes less than $\sqrt{163}$ , it follows that 163 is prime.

Example. There are simple tests for divisibility by small numbers based on the decimal representation of a number.

If $a_na_{n-1}\ldots a_1a_0$ is the decimal representation of a number, its digital sum is

$$D(a_na_{n-1}\ldots a_1a_0) = a_n + a_{n-1} + \cdots + a_1 + a_0.$$

That is, $D(x)$ is the sum of the digits of x. For example,

$$D(119) = 1 + 1 + 9 = 11, \quad D(247) = 2 + 4 + 7 = 13.$$

To see this, note that if $x = a_na_{n-1}\ldots a_1a_0$ is the decimal representation of x, then

$$x = a_n\cdot 10^n + a_{n-1}\cdot 10^{n-1} + \cdots + a_1\cdot 10 + + a_0.$$

So

$$x - D(x) = (a_n\cdot 10^n + a_{n-1}\cdot 10^{n-1} + \cdots + a_1\cdot 10 + + a_0) - (a_n + a_{n-1} + \cdots + a_1 + a_0) =$$

$$a_n(10^n - 1) + a_{n-1}(10^{n-1} - 1) + \cdots + a_1(10 - 1).$$

Each term of the form $10^k - 1$ is $999\ldots 9$ ($k - 1$ nines), so the right side is divisible by 3 and by 9. Thus, $x - D(x)$ is divisible by 3 and 9, so x is divisible by 3 or 9 if and only if $D(x)$ is.

For example, 9183 is divisible by 3, since $9 + 1 + 8 + 3 = 21$ is divisible by 3. And 725 is not divisible by 9, because $7 + 2 + 5 = 14$ is not divisible by 9.

Remark. The Fundamental Theorem of Arithmetic states that every positive integer can be expressed as a product of powers of primes, and this expression is unique up to the order of the factors.

For example,

$$720 = 2^4\cdot 3^2\cdot 5.$$

While this result is true, overuse of the Fundamental Theorem in divisibility proofs often results in sloppy proofs which obscure important ideas. Try to avoid it.

Definition. Let m and n be integers, no both 0. The greatest common divisor $(m,n)$ of m and n is the largest integer which divides both m and n.

Example. Observe that 1 is a common divisor of any two integers m and n. Since $(m,n)$ is the greatest common divisor, $(m,n) \ge 1$ , and in particular, $(m,n)$ must be positive.

Here are some numerical examples:

$$(6,8) = 2, \quad (-15,10) = 5, \quad (77,0) = 77.\quad\halmos$$

Example. Show that if n is an integer, then $(n, n + 2)$ is either 1 or 2.

$(n, n + 2)$ divides both n and $n + 2$ , so it divides any linear combination of n and $n + 2$ . In particular,

$$(n, n + 2) \mid (n + 2) - n = 2.$$

Now $(n, n + 2) \ge 1$ ; the only positive integers which divide 2 are 1 and 2. Therefore, $(n, n + 2)$ is either 1 or 2.

Notice that both of these cases can occur: If $n = 1$ , then $(n, n + 2) = (1,3) = 1$ , and if $n = 2$ , $(n, n + 2) = (2, 4) = 2$ .

Lemma. If $am + bn = 1$ for some $a, b \in \integer$ , then $(m,n) = 1$ .

Proof. $(m,n) \mid m$ and $(m,n) \mid n$ , so

$$(m,n) \mid am + bn = 1.$$

But $(m,n) \ge 1$ , and the only positive integer which divides 1 is 1. Therefore, $(m,n) = 1$ .

Definition. Let $m, n \in \integer$ . m and n are relatively prime if $(m,n) = 1$ .

Thus, the last lemma says that if some linear combination of m and n equals 1, then m and n are relatively prime.

Example. Prove that for all $n \in \integer$ , $4n + 3$ and $6n + 4$ are relatively prime.

Two integers are relatively prime if their only (positive) common factor is 1. Thus, this problem says that 1 is the only common factor of $4n + 3$ and $6n + 4$ .

The table below shows the values of $4n + 3$ and $6n + 4$ for $-5 \le n \le 5$ . The result seems plausible based on the evidence.

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & n & & -5 & & -4 & & -3 & & -2 & & -1 & & 0 & & 1 & & 2 & & 3 & & 4 & & 5 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $4n + 3$ & & -17 & & -13 & & -9 & & -5 & & -1 & & 3 & & 7 & & 11 & & 15 & & 19 & & 23 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $6n + 4$ & & -26 & & -20 & & -14 & & -8 & & -2 & & 4 & & 10 & & 16 & & 22 & & 28 & & 34 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

To prove it, I'll use part (a). I want numbers a and b such that

$$a(4n + 3) + b(6n + 4) = 1.$$

Since there are no n's on the right side, I want to choose a and b to make the n's on the left cancel out. One way to do this is

$$3\cdot (4n + 3) + (-2)(6n + 4) = 1.$$

This linear combination is equal to 1, so by (a), $(4n + 3, 6n + 4) = 1$ .

As the example shows, one way of showing that two integers are relatively prime is to find a linear combination of them that equals 1. The converse is true: If two integers are relatively prime, then some linear combination of the integers equals 1.

In fact, more is true: The greatest common divisor $(m,n)$ of m and n can always be written as a linear combination $am + bn$ of m and n. There is an algorithm for finding greatest common divisors; it is called the Euclidean algorithm. An extended version of the Euclidean algorithm finds a linear combination $am + bn$ such that $(m,n) = am + bn$ . You'll probably see these results in a course in abstract algebra or number theory; I won't prove them here.

Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Bruce Ikenaga's Home Page

Copyright 2008 by Bruce Ikenaga