# Divisibility

Definition. If a and b are integers with , then a divides b if for some integer n. means "a divides b". In this case, a is a factor or a divisor of b.

The notation 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 .

The requirement that is included to avoid the following annoyance: , so if 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 , means that . But would not mean " " --- in fact, " " cannot be defined in in a manner that's consistent with the definition of .

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

• It's often useful to translate divisibility statements (like ) into equations using the definition.
• Do not use fractions or the division operation in your proofs!

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

1. If and , then .
2. If and , then for all .

Proof. (a) Suppose and . means that for some m; means that for some n. Hence, , so .

(b) Suppose and . means that for some m; means that for some n. Then

An expression of the form is called a linear combination of x and y.

Here are two special cases of part (b):

• If a divides x and y, then a divides .
• If a divides x, then a divides for all b.

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

For example,

are prime. On the other hand,

are composite.

Lemma. If n is composite, then there are integers a and b such that and .

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

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

Suppose on the contrary that . Since , it follows that

Likewise, if , then since , I have

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 .

Lemma. Every integer has a prime factor.

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

Suppose that , 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 and . 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 , 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

Consider the number

When this number is divided by , , ..., , 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 , where .

Lemma. If n is composite, then it has a prime factor p such that .

Proof. First, an earlier lemma show that there are integers a and b such that and . If and , then , which is a contradiction. Therefore, a and b can't both be greater than .

Suppose without loss of generality that . 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 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 . If no such prime divides n, then n is prime.

For example, . By trial, I find that

Since these are all the primes less than , it follows that 163 is prime.

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

• A number is even (divisible by 2) if and only if its units digit is 0, 2, 4, 6, or 8.
• A number is divisible by 5 if and only if its unit digit is 0 or 5.

If is the decimal representation of a number, its digital sum is

That is, is the sum of the digits of x. For example,

• A number is divisible by 3 if and only if its digital sum is divisible by 3.
• A number is divisible by 9 if and only if its digital sum is divisible by 9.

To see this, note that if is the decimal representation of x, then

So

Each term of the form is ( nines), so the right side is divisible by 3 and by 9. Thus, is divisible by 3 and 9, so x is divisible by 3 or 9 if and only if is.

For example, 9183 is divisible by 3, since is divisible by 3. And 725 is not divisible by 9, because 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,

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 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 is the greatest common divisor, , and in particular, must be positive.

Here are some numerical examples:

Example. Show that if n is an integer, then is either 1 or 2.

divides both n and , so it divides any linear combination of n and . In particular,

Now ; the only positive integers which divide 2 are 1 and 2. Therefore, is either 1 or 2.

Notice that both of these cases can occur: If , then , and if , .

Lemma. If for some , then .

Proof. and , so

But , and the only positive integer which divides 1 is 1. Therefore, .

Definition. Let . m and n are relatively prime if .

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 , and 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 and .

The table below shows the values of and for . The result seems plausible based on the evidence.

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

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

This linear combination is equal to 1, so by (a), .

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 of m and n can always be written as a linear combination 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 such that . You'll probably see these results in a course in abstract algebra or number theory; I won't prove them here.