You probably know that division can be defined in terms of
multiplication. If m and n are integers, m
divides n if for some integer k. In this
section, I'll look at properties of the divisibility relation.
I'll begin by discussing the Division Algorithm, which tells you something you've known since grade school --- namely, that you can divide one integer by another. Note that this isn't the long-division algorithm, which tells you how to divide one integer by another. The Division Algorithm follows from the Well-Ordering Axiom for the nonnegative integers.
Well-Ordering Axiom. The positive integers
are well-ordered --- that is,
every nonempty subset of the positive integers has a smallest
element.
Even though your experience with the integers may lead you to think
this is obvious, it's actually an axiom of the positive
integers . It has many important consequences; mathematical induction is one, and the Division
Algorithm is another.
Note that Well-Ordering applies to nonempty subsets of the nonnegative integers as well. If such a subset contains 0, then 0 is the smallest element; if the subset doesn't contain 0, then it consists of only positive integers, and Well-Ordering for the positive integers implies that it has a smallest element.
Example. ( Applying the Well-Ordering Axiom) Show that there is no positive integer less than 1.
In this proof, I'm going to assume familiar facts about inequalities involving integers, since the point is to illustrate how you might use Well-Ordering.
Suppose that there is a positive integer less than 1. Let S be the set of positive integers less than 1. Then S is nonempty, so by Well-Ordering, S has a smallest element.
Suppose that x is the smallest element of S. Now , so multiplying by x, I get
Thus, is a positive integer less than 1 which is
smaller than x. This is a contradiction. Therefore, there is
no positive integer less than 1.
Theorem. ( The Division
Algorithm) Let a and b be integers, with . There are unique integers q and r such that
Of course, q is the quotient and r is the remainder.
Proof. What is division? Division is successive subtraction. Therefore, you ought to be able to find r by subtracting multiples of b from a until the result becomes negative. For example, if you're dividing 23 by 7, you'd do this:
The quotient is 3 --- the last multiple of 7 which gave a nonnegative result. The last nonnegative result is the remainder, which is 2.
To do the proof, I have to take the idea exhibited in this example and write it out in general (with a, b, q, and r instead of specific numbers).
Look at the set of integers
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
both in the range
. Therefore, they have to be less
than b units apart. But the last equation says they are
units apart --- a multiple of b).
The only way r and can be less than b units apart and
a multiple of b units apart is if the multiple in question is 0. That
is,
. Since
, this means that
, or
. If I plug
back into
, I find that
, so
. This proves that r and q are
unique.
Example. ( Applying the Division Algorithm) (a) Find the quotient and remainder when the Division Algorithm is applied to divide 99 by 13.
(b) Find the quotient and remainder when the Division Algorithm is applied to divide -99 by 13.
(a)
The quotient is 7 and the remainder is 8. According to the proof of
the theorem, 8 should be the smallest positive number of the form
. In this case,
Clearly, adding multiples of 13 to will
give numbers larger than 8, whereas subtracting multiples of 13 from
will give negative numbers.
(b)
Note that . I don't write
(even though the equation is correct),
because -8 is not between 0 and 13. The Division Algorithm always
produces a nonnegative remainder.
Definition. If m and n are integers, then m
divides n if for some integer
k.
The notation means that m divides n;
means that m does not divide n.
Remarks. (a) Some people prefer to require
that when you write "
". Note that
if
and
, then
. This means
for some k, so
. So the only divisibility statement you can make of
the form "
" is "
", which isn't that interesting.
This issue is different from the idea that "you can't divide by
0", which means that 0 does not have a multiplicative inverse.
We'll see later that in any commutative ring with
identity, can't be defined (unless the ring is the
zero ring).
The definition of divisibility above makes no reference to multiplicative inverses or an operation of division: It's defined entirely in terms of multiplication.
(b) Be careful not to write " ",
"
", or "
" when you
mean "
"!
" ", "
", and "
" all mean "n divided by m".
Notice that this isn't a statement, since it's not a
complete sentence that can be true or false --- it's an
expression. On the other hand, "
" means "m divides n", which
is a statement.
Example. Apply the definition of divisibility to show that:
(a) .
(b) .
(c) for all
.
(d) for all
.
(a) Since , I have
.
(b) Since , I have
.
(c) Since , I have
for all
.
(d) Since , I have
for all
.
Proposition.
(a) Let . If
and
, then
.
(b) Let . If
and
, then
for all
.
This is often expressed by saying that if m divides two numbers, it divides any integer linear combination of the two numbers.
(c) Let . If
, then
for all
.
(d) Let . If
and
, then
.
This is often expressed by saying that if m divides two numbers, it divides their sum. It's also true that if m divides two numbers, it divides their difference.
(e) If and
, then
.
Proof. The idea in divisibility proofs is
often to translate statements like " " into equations like "
", then work with the equations.
(a) implies
for some k.
implies
for some j. Substituting the first
equation into the second gives
Therefore, .
(b) implies
for some j. And
implies
for some k. Then
Hence, .
(c) Taking and
in (b), I find that
and
implies
(d) Taking in (b), I find that
and
implies
(e) Suppose and
.
implies
for some
; k must be a positive integer, since m and
n are positive integers. Thus,
, and multiplying both
sides of this inequality by m gives
Example. ( Proving a
divisibility property) (a) Give an example of integers m and n
such that and
but
.
(b) Prove that if m and n are positive integers, , and
, then
.
(a) and
, but
.
(b) One approach is to use property (e) of the preceding lemma. Since
m and n are positive integers, implies
, and
implies
. The two inequalities imply that
.
Here's another proof which uses the definition of divisibility.
Since ,
for some
. Since
,
for some
. Hence,
. Since
, I may cancel it from both sides
to obtain
.
a and b are integers, so either or
. But if
, then
, which is impossible since m and n are positive.
Therefore,
, so
.
Example. ( Even and odd
integers) An integer is
even if
. An integer is odd
if it is not even.
(a) Prove that even integers can be written in the form for some
, and odd integers can
be written in the form
for some
.
(b) Prove that if is even, so is
.
If n is even, then , so
for some
.
Suppose n is odd. Use the Division Algorithm to divide n by 2, obtaining a quotient of m and a remainder of r:
Now implies that
or
. If
, the equation says
, which means that n is even. But n was odd, so this
is a contradiction. Therefore,
, and
.
(b) Suppose is even. By (a),
for some
. Then
I've expressed as 2 times an integer, so
is even.
Note: In this proof, I'm only using properties of divisibility and
the definition of "even". So (for instance) I can't stop
with " " and say that "the sum
of even numbers is even", because I haven't proven yet
that the sum of even numbers is even.
Example. Is there an integer n such that and
?
No. Assume that and
for some n. Then 7 must divide any integer linear
combination of
and
, so
This contradiction shows that there is no such n.
Example. Prove that if m is a positive integer
and n is an integers such that and
, then
.
One of the divisibility properties implies that m must divide any
integer linear combination of and
. So the idea is to construct a linear combination of
and
which adds up to 1. If this is to
happen, the n's have to cancel; one way to get this to happen is to
switch the "4" and the "3" and negate one of
them:
Since m is a positive integer which divides 1, I must have .
Copyright 2018 by Bruce Ikenaga