# Divisibility

• means that a divides b --- that is, b is a multiple of a.
• An integer n is prime if and the only positive divisors of n are 1 and n. Prime numbers are important in number theory and its applications.
• The Division Algorithm says that an integer can be divided by another (nonzero) integer, with a unique quotient and remainder.
• The Division Algorithm is a consequence of the Well-Ordering Axiom for the positive integers.

If a and b are integers, a divides b if there is an integer c such that

The notation means that a divides b.

Be careful not to confuse " " with " " or " ". The notation " " is read "a divides b", which is a statement --- a complete sentence which could be either true or false. On the other hand, " " is read "a divided by b". This is an expression, not a complete sentence. Compare "6 divides 18" with "18 divided by 6" and be sure you understand the difference.

Example. , since . And , since .

The properties in the next proposition are easy consequences of the definition of divisibility; see if you can prove them yourself.

Proposition.

(a) Every number divides 0.

(b) 1 divides everything. So does -1.

(c) Every number is divisible by itself.

Proof. (a) If , then , so .

(b) To take the case of 1, note that if , then , so .

(c) If , then , so .

Remark. Under this definition, the only number divisible by 0 is 0. The statement " " is not very interesting, and some people prefer to make the definition of " " only in the case where .

Note that when people say informally that "You can't divide by 0", they mean that 0 does not have a multiplicative inverse. This is a different use of the word "divides" than what we have above. There's nothing about multiplicative inverses in the definition of " ", which is about a being a factor of b.

Definition. An integer is prime if its only positive divisors are 1 and itself. An integer is composite if it isn't prime.

The first few primes are

The first few composite numbers are

Prime numbers play an important role in number theory.

Proposition. Let .

(a) If and , then .

(b) If , , and , then

(c) If and , then .

(In case you were wondering, mathematicians have different names for results which are intended to indicate their relative importance. A Theorem is a very important result. A Proposition is a result of less importance. A Lemma is a result which is primarily a step in the proof of a theorem or a proposition. Of course, there is some subjectivity involved in judging how important a result is.)

Proof. (a) Suppose and . This means that there are numbers d and e such that and . Substituting the first equation into the second, I get , or . This implies that .

(b) Suppose and . This means that there are numbers d and e such that and . Then

To say it in words, if an integer a divides integers b and c, then a divides any linear combination of b and c.

Two important special cases of (b): If and , then

(c) means for some e, and means for some f. Therefore,

Example. Prove that if x is even, then is divisible by 4.

x is even means that .

and implies that by part (c) of the proposition.

and implies that by part (c) of the proposition.

Obviously, .

Then by part (b) of the proposition, so , again by part (b) of the proposition.

Example. Prove that if a divides b, then a divides any multiple of b.

First, here's a proof which uses part (c) of the Proposition.

Assume that . Let be a multiple of b. I want to show that . I observed earlier that 1 divides everything, so . Then and implies by the Proposition, so .

You can also use part (b) of the proposition.

Alternatively, here's a proof that uses the definition of divisibility. Assume that . Let be a multiple of b. I want to show that .

Since , I have for some c. Multiplying both sides by d, I get , i.e. . This equation implies that .

Here is an important result about division of integers. It will have a lot of uses --- for example, it's the key step in the Euclidean algorithm, which is used to compute greatest common divisors.

Theorem. ( The Division Algorithm) Let a and b be integers, with .

(a) There are unique integers q and r such that

(b) .

Of course, this is just the "long division" of grade school, with q being the quotient and r the remainder.

Proof. (a) The idea is to find the remainder r using Well-Ordering. What is division? Division is successive subtraction. You ought to be able to find r by subtracting b's from a till you can't subtract without going negative. That idea motivates the construction which follows.

Look at the set of integers

In other words, I take a and subtract all possible multiples of b.

If I choose (as I can --- there's always an integer less than any number), then , so . This choice of n produces a positive integer in S. So the subset T consisting of nonnegative integers in S is nonempty.

Since T is a nonempty set of nonnegative integers, I can apply Well-Ordering. It tells me that there is a smallest element . Thus, , and for some q (because , , and everything in S has this form).

Moreover, if , then , so

So , but . This contradicts my assumption that r was the smallest element of T.

All together, I now have r and q such that

To show that r and q are unique, suppose and also satisfy these conditions:

Then

But r and are two nonnegative numbers less than b, so they are less than b units apart. This contradicts the last equation, which says they are units apart --- unless . Since , this means , or . In addition, , so . This proves that r and q are unique.

(b) Assuming with , I want to show that .

This shows that q is an integer less than or equal to . Hence, . I have to show that this is actually equality.

Suppose on the contrary that . The next integer larger than q is , and must be at least as big. So

Since , the last inequality gives

This contradicts . Since is ruled out, I must have .

Example. (a) Apply the Division Algorithm to divide 59 by 7.

(b) Apply the Division Algorithm to divide -59 by 7.

(a) The quotient is , the remainder is 3, and . I have

(b) The quotient is , the remainder is 4, and . I have

Example. Prove that if , then does not leave a remainder of 2 or 3 when it's divided by 5.

It is easier to do this using modular arithmetic, but I'll do this using the Division Algorithm as an illustration.

If n is divided by 5, the remainder r satisifies . Thus, . Hence, n can have one of the following 5 forms:

Check each case:

In all cases, dividing by 5 gave a remainder of 0, 1, or 4. I never got a remainder of 2 or 3.

As an illustration, can't be a perfect square, because it leaves a remainder of 3 when it's divided by 5.

Contact information