# Divisibility

Definition. If a and b are integers, 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 . It does have the following peculiar consequence: because (for instance) . You may object that "you can't divide by 0", but that is a different use of the word "divide" --- it refers to multiplying by the multiplicative inverse, and it's true that 0 doesn't have a multiplicative inverse in any "reasonable" number system.

If this still troubles you, there's no great harm in adding the condition " " to the definition above.

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

(a) It's often useful to translate divisibility statements (like ) into equations using the definition.

(b) Do not use fractions or the division operation in your proofs!

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

(a) If and , then .

(b) 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 some special cases of part (b):

1. If a divides x and y, then a divides and .

2. If a divides x, then a divides for all b.

In the first case, apply (b) with and (and and ). In the second case, apply (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, the first few primes are

On the other hand, the first few composite numbers are

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

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

I sketched the proof of the following result when I discuss proof by contradiction. Having proved the last two results, the proof is now complete --- but I'll repeat it here. It is essentially the proof 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 .

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

Proof. First, an earlier result shows 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. Use trial division to determine whether 163 is prime.

By the last lemma, 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.

I have . By trial, I find that

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

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

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

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

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

(b) A number is divisible by 5 if and only if its unit digit is 0 or 5.

(c) A number is divisible by 3 if and only if its digital sum is divisible by 3.

(d) A number is divisible by 9 if and only if its digital sum is divisible by 9.

Proof. Suppose is the decimal representation of a positive integer x. Then

All of the results can be proved by using this representation (and where appropriate, the digital sum). For example, here's a sketch of the proof of (a). Note that since ,

Thus, for some integer m,

From this, it follows that if and only if is 0, 2, 4, 6, or 8. I'll let you write out the details.

For (c) and (d), note that

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.

If you're uncomfortable about using the decimal representation of as , you can note that for ,

Hence, .

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 very important, 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, not both 0. The greatest common divisor of m and n is the largest integer which divides both m and n.

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:

You might have been able to see these by factoring. But what if the numbers are too big to be factored? The Euclidean algorithm gives a method for computing the greatest common divisor of two positive integers using only integer division.

Example. Compute .

I'll arrange the computations in a table with two columns. Begin the first column with the larger number first. Divide 271 by 113:

Put the quotient 2 next to the 113 and the reaminder 45 below the 113.

(Note that there is a blank space (marked with a "-") next to 271. This isn't important here, but later you may see a third column added to this table for the Extended Euclidean Algorithm, in which case the blank space is important.)

Continue in the same fashion: Divide 113 by 45:

Put the quotient 2 next to 45 and the remainder 23 below 45.

The table stops when you get an a first column number "divides evenly into" the one above it. The the remainder is 0, and since you can't divide by 0, the process must stop. The last nonzero remainder is the greatest common divisor. So

You can at least see from this example why the process has to stop. When you divide, the remainder is always less that the thing you divided by. So the remainders in the first column are positive numbers that keep getting smaller --- and since the process can't go on forever (reason: the Well-Ordering Axiom for the positive integers), it must end in the only way possible with a remainder of 0.

I won't prove that this algorithm gives the greatest common divisor, but here's the idea: The greatest common divisor of any two consecutive numbers in the first column remains the same. Check it yourself in the table above.

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

Proposition. 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. An extended version of the Euclidean algorithm finds a linear combination such that . You'll probably see this result in a course in abstract algebra or number theory; I won't prove it here.

Contact information