The Division Algorithm
Theorem [ Division Algorithm ]. Given any strictly
positive integer d and any integer a, there
exist unique integers q and r such that
a = qd + r,
and
0≤ r < d.
Before discussing the proof, I want to make some general remarks about what this
theorem really
says, why it says it in what seems at first such a perversely obscure way, and
why it's worth proving
something at all which, as we shall see, actually seems quite obvious.
The Language in Which Mathematics Is Done
Even when talking about day to day life, it sometimes happens that one has a
hard time finding
the words to express one's thoughts. Furthermore, even when one believes that
one has been totally
clear, it sometimes happens that there is a vagueness in one's words that
results in the listener
understanding something completely different from what the speaker intended.
Even the simplest mathematical reasoning is usually more complicated than the
most complicated
things one attempts to discuss in everyday life. For this reason, mathematics
has developed an
extremely specialized (and often stylized) language. To see the value of this ,
one only has to think of
how difficult it would be to solve even the simple quadratic equation x 2 − 5x = 14
if one's calculation
had to be done without symbols, using only ordinary language.
"Suppose that a quantity has the property that when five times that quantity is
subtracted from the product of the quantity times itself then the result is 14.
Determine the possible values of this quantity."
During the middle ages, algebraic calculations were in fact done in this fashion
| except that the
language was Latin, not English. But progress beyond the level of simple algebra
only became possible
with the introduction of modern algebraic notation | which the West learned from
the Arabs.
By combining symbolic notation with very precisely defined concepts and a very
formalized
language, any mathematical proof can be expressed in a way that can be
understood by any
"mathematically mature" reader. One is not dependent on the reader's ability to
"see what is meant."
In principle, at least, every step is described in terms so precise that no
possible misunderstanding can
occur, and anyone can follow the reasoning from one step to the next, provided
only that he is skilled
in making the most basic sort of algebraic, set theoretic, and logical
manipulations. In particular, the
language is so explicit that one never needs reference to illustrative examples
in order to explain the
meaning of what is said. (In practice, it has to be admitted that sometimes even
the experienced
mathematician gets stopped at certain points in the proof
and has to rack his brains for a minute or
two |or even longer| before he says, "Oh, yeah, that's why." Students, of
course, have this
difficulty much more frequently.)
It's important to realize, however, that useful as the language of mathematics
is, it doesn't
represent the way humans normally gain understanding. So even something quite
familiar can
sometimes seem strange when described in a precise , mathematical way.
One might think of the language in which mathematics is done as analogous to
programming
languages. A computer program describes how to perform a given task without
omitting even a single
step, no matter how small, and without any conceivable ambiguity. One might
think that for this
reason, a computer program would be the ideal way to explain a procedure so that
no one could
possibly fail to understand it. But in fact, human beings find computer programs
extremely difficult
to understand.
The language of mathematical proofs is a little more human than that of computer
programs.
Nonetheless, learning to read this kind of language is a formidible challenge
for students. Learning to
write it is even more formidible. The endeavor can be quite worthwhile, however,
since the reward for
success is access to the vast realm of modern mathematics.
With this in mind, take another look at the theorem we started with.
Theorem [Division Algorithm]. Given any strictly positive integer d and any
integer a, there
exist unique integers q and r such that
a = qd + r,
and
0 ≤r < d.
One might be excused for racking one's brains for quite some time to figure out
what this theorem
"really means." And yet it simply describes the process of dividing one integer
a (the "dividend") by
another d (the 'divisor") to get a quotient (q ) and a remainder (r ). For
instance,
In this example, we have a = 1052 and b = 29. The theorem
above states that there exist unique
numbers q and r such that
1052 = 29q + r and 0 ≤r < 29.
The calculation shows that in fact, q = 36 and r = 8.
The dividend a for the Division Algorithm is allowed to be negative . In this
case, the quotient will
also be negative (or possibly 0), but the remainder is still required to be
positive.
This calculuation represents the equation −121 = 29(−5) +
24.
Operational, Procedural, and Notational Definitions
The statement of the division algorithm as given in the theorem describes very
explicitly and
formally what long division is. To borrow a word from physics, the description
of long division by the
two conditions a = qd + r and 0 ≤r < d is operational. Given two numbers, for
instance, 1052
and 29, the conditions give a very explicit way of testing whether or not 36 is
the quotient and 8 the
remainder when the first number is divided by the second.
On the other hand, these two conditions are not procedural: they do not provide
a recipe for
actually finding the quotient and remainder. In fact, until one recognizes what
the theorem is
describing as simply long division, it is not obvious that the theorem is even
true. Good definitions in
mathematics must always be operational (at least in some idealized sense), but
they are often not
procedural.
Analogously, consider the definition of the absolute value function give in many
college algebra
courses:
This definition is both operational and procedural, since
it describes exactly how to compute lxl .
And yet most students find it completely bewildering. (Students who do make some
attempt to make
sense out of it often think it says, "If x is positive, leave it alone, and if
it's negative, make it
negative." They forget that if x is negative, then −x if positive: for instance,
−(−13) = 13. )
Unless I consider a student fairly bright, when he asks me what the above definition of the
absolute value function really means, I usually say, "Just make x positive by
throwing away the minus
sign if it has one." One can say that this second definition ("throw away the
minus sign") is
operational and procedural, since it certainly enables one to easily compute the
absolute value of a
number. So what's the advantage of the first one, which seems so bewildering?
Well, for one thing, the first definition of the absolute value function is stated
in terms of intrinsic
properties of numbers, whereas the second definition is notational: it is stated
in terms of the way
we write numbers down. The second definition works fine when we want to computer
the absolute
value of a concrete number written down specifically, but it's not so useful when
we want to talk
about numbers in generality, or we have a number that's not described in
concrete form. (For
instance, if we say "Let x be the smallest solution of the
equation x2 − x = 5," there's no minus sign
in the way we've named x, even though one can show that it is negative.) Most
important, the first
definition is useful for proving theorems, whereas the second is not.
Nonetheless, I think that giving the first definition in college algebra books is
approaching
mathematics in an overly formalistic way that drives many students away.
By the time a student gets to Number Theory, however, it's time he should begin
to learn the kind
of language that is used in contemporary mathematics.
In general, there are often two approaches to defining a mathematical entity. The
procedural
approach gives a method for actually calculating or constructing that entity.
Alternatively, an entity
can be defined by specifying a set of rules which characterize its "behavior" (as
it were). The
mathematics of the Twentieth Century tends to put emphasis on the rules by which
entities behave, rather on the way they are constructed.
As an example of this modern approach, one might describe the natural logarithm
as a function L
with the properties that L(xy) = L(x) +L(y) for all x and y, and L'(1) = 1. This definition says
nothing about how to actually compute the natural logarithm. In fact, until one
has proved the
appropriate theorem, it is not even clear that this natural logarithm function
even exists. However
once the necessary existence theorem has been proved, this modern definition
enables one to derive all
the important formulas for the logarithm function (including the formulas for
its derivative and
integral) in a very clean manner.
The description of long division given in elementary school is notational. From
a mathematician's
point of view, it doesn't describe what long division really is in an intrinsic
way, as the theorem does.
Furthermore, the elementary school definition would not make any sense to someone
who used Roman
numerals or some other non-standard way of writing numbers. (Although the use of
Roman or
Chinese systems for representing numbers is not of great practical concern,
there is non-decimal
representation of numbers which is of quite great importance| namely the
representation of numbers
in computers. If one were required to write a computer program to do long
division, one would not
want to start from the sixth-grade procedure, although that procedure-suitably
modified-might
provide some useful insight.)
The description of the division algorithm by the conditions a = qd + r and 0 ≤r <
d is complete
without reference to any illustrative example. It's also important to realize,
though, that for us human
beings, simple examples, such as the example of long division given above, are
an important aid in
understanding mathematics. As soon as one gives a simple numerical example for
the Division
Algorithm, the student or the mathematician will almost instantly say, "Aha!"
The example appeals
to a different sort of understanding, which is more natural for human beings.
Unfortunately, in many
advanced mathematical texts the reader has to construct such examples for
himself. (One can be sure,
however, that the author has constructed such examples. It's just that it's
considered a little
amateurish | perhaps insulting to the reader's intelligence | to include them in
an advanced text.)
The Importance of the Division Algorthm
The Division Algorithm talks about the form of division one first learns about in
elementary
school, where one gets both a quotient and a remainder. Later on, after one
learns about fractions , it
may seem like a rather simple-minded way of thinking about division. I know it
seemed like that to
me. In particular, I was always annoyed by getting that damned remainder term.
Somehow having a
remainder made the division process imperfect, and that was inconsistent with my
idea of
mathematics as a subject where things are always exact.
In Number Theory, however, this is the way of looking at division which is most
useful. And in
fact that apparently annoying remainder turns out to be often much more
important than the
quotient. In computer science, and certain parts of mathematics, ones writes
a mod d
to denote the remainder when a is divided by d. For instance, 1052 mod 29 = 8.
Most books on
number theory do not use this notation, but instead write 1052 ≡8 (mod 29).
As a simple example of why this concept might be useful, consider the question,
"If June 21, 1997
is a Saturday, then what day of the week will July 4 come on in the year 2000?"
To answer this, first
calculate, taking into account that the year 2000 will be a leap year, that
there are
13 + 3 *365 + 1 = 1109 days between June 21, 1997 and July 4, 2001. Then divide
1109 by 7 and see
that the remainder is 3, so that 1109 mod 7 = 3. This tells us that there are a
certain number of full
weeks (158, in fact, since 158 is the quotient when 1109 is divided by 7) plus 3
more days from
June 21, 1997 until July 4, 2001. The full weeks don't matter, so July 4, 2000
will be three days later
than Saturday, namely Tuesday.
This example may seem of rather limited value, but similar situations arise in
mathematical
applications quite frequently, since many mathematical entities are cyclical in
the same way as the
days of the week are. For instance, if one were to ask what the 500th digit in
the decimal expansion of
1/13 is, is would be foolish to compute all 500 digits. Since the decimal
expansion of 1/13,
viz .076923076923..., has a cyclic pattern of length 6, one only need note that
500 mod 6 = 2, so that
the 500th digit in this expansion will be the same as the second digit, namely
7.
| Prev | Next |