Read an Excerpt

The Theory of Remainders

Dover Publications, Inc.

Section One

The Black Magic Device

Ah, yes. Some of us haven't yet met. I'm Ant, an Amateur Number Theorist. Gnam, a Game Nut and Magician, ought to be along soon.

I must remember to tell Gnam about Simon Flagg. It seems that Simon had a rather extraordinary experience with the devil. After spending many years trying to either prove or disprove Fermat's Last Theorem, Simon offered his soul to the devil in return for either a proof or a counter-example to the famous conjecture. If the devil couldn't settle the question within 24 hours, then Simon and his wife were assured of wealth, health and happiness for the rest of their days. Otherwise, well, so much for Simon's soul!

Apparently the devil was delighted with the deal (for he is adept at performing quite extraordinary feats) until he realized that it meant he had to do some mathematics. Mathematics belongs to the realm of the devil's nemesis, you know. Nevertheless, he set about his study in a serious manner. He even made trips to other planets to find out how extra-terrestrial beings were coping with the problem.

I think I hear Gnam coming now, so if you would like to know how the tale ends, you can read "The Devil and Simon Flagg" by Arthur Gorges in Clifton Fadiman's Fantasia Mathematica.

"Look at this strange device I have", said Gnam. The device looked like a piece of jewelry. It was round, and in the middle was a pentagonal black onyx prism. The edge was set in a lead ring. The inscriptions on the ring were all in indigo, whereas the inscriptions on the onyx were white. The symbols on the edge reminded me of those Gnam had once shown me in a medieval book on magic.

"A magician friend of mine says that she found this in a collection of black magic devices," continued Gnam. "She claims that it can do mathematics. But how can that be? Black magic is the realm of the devil, you know."

What a coincidence, I thought, as I proceeded to tell Gnam the story about Simon and the devil. Then I asked Gnam how to use the device.

"I am told that if you say Oh Canine of Darkness here is my offering of 2000 that ..."

Gnam never finished the sentence, for at that moment the device became hot, the onyx turned red, and the face of a black toy poodle with the name "Magic" written underneath seemed to glow in the center.

After composing myself, I bravely took the device from Gnam and began experimenting with it. I discovered that if I offered any integer between – 1000 and 1000 to the dark canine, a number (usually different from the one offered) would appear in the center of the device. However, when I offered any other number, the face of the canine would appear.

In case you are interested, here is a list of the numbers I offered the device and the numbers that appeared in the center.

Naturally, I figured out rather quickly what the device was doing. (Have you?) Gnam was impressed, but the device was merely giving the remainder of the number offered when the number is divided by 13, and I am used to thinking in terms of remainders. Gnam didn't understand how the device worked with negative numbers; I promised to explain later.

I decided to experiment a little further with the device, to see if it could add or multiply. So I offered the number 14, and when the number 1 appeared in the center, I then offered "plus 15". Just as I expected, a 3, not a 2, now appeared in the center. "Plus 30" then elicited a 7. Next I offered "times 14" and the 7 remained. Then "times 15" and a 1 now appeared. Gnam was totally confused and asked me to make a list of some of the sequences of numbers I offered.

After studying this list for several minutes, Gnam sighed. "The device is doing some kind of strange arithmetic, which I don't completely understand."

"We'll return to the question of what the device is doing, later. We'll even figure out how to use it to find the remainders of numbers that are larger than 1000 and numbers that are smaller than – 1000. In Section 5, I will teach you techniques useful in solving problems such as ..."

Some Comments on the Significance of Remainders

"It's very strange, Ant, that the Black Magic Device gives remainders but not quotients. (It's the ability to observe even such minor irregularities that separates us magicians from ordinary folk.)"

"Maybe not so strange. For it is remainders, far more than quotients, which provide insight into the behavior of numbers."

Gnam looked skeptical, so I added, "Elementary number theory deals with problems pertaining to the integers. Two integers can be added, subtracted or multiplied and the result is always an integer. But when you divide integers, you are likely to get a nonzero remainder."

Gnam was unimpressed, so I continued. "Most of the problems of number theory involve knowing when certain numbers are factors of other numbers. In fact, number theory might be characterized as the study of divisibility and factorization.

"The method of long division yields both the remainder and the quotient. When the remainder is zero, we know the divisor is a factor of the dividend. However, long division is a tedious way of checking for divisibility because most of the calculation is directed toward finding the quotient."

"How else would you find remainders?"

"You already know how to find remainders without using the long division process when dividing by 2 or 5."

"Or 10 or 20 or any of several other numbers, Ant. But those are rather special cases."

"Maybe not as special as you think. As I will show you later, when armed with a bit of insight into the theory of remainders, you can create remainder tests for divisors of your choice.

"The ancient Greeks discovered some general results pertaining to divisibility which were extended by mathematicians such as Pierre de Fermat and Leonhard Euler in the seventeenth and eighteenth centuries. However, in spite of the obvious connection between remainders and divisibility, the critical significance of remainders was not recognized until the nineteenth century when the mathematical giant Karl Friedrich Gauss used remainders as the central concept in his study of number theory. Instead of proceeding directly to the question of when is one number a factor of another number (that is, when is the remainder 0), Gauss built a theory of remainders by asking questions such as the following.

Given a fixed divisor:

1. When do two numbers have the same remainder?

2. What is the relationship between the remainders of a, b, a + b, a -b, and ab?

3. If a and b have the same remainder, and c and d have the same remainder, do a + c and b + d have the same remainder?

"By investigating these questions, we can develop a perspective that is very powerful in analyzing a variety of problems. The approach we will use is more modern than that devised by Gauss. Instead of studying remainders within the context of ordinary arithmetic, we will create new mathematical systems with new operations and study these. These systems are called modular systems. They are related to the integers, but are easier to study, largely because the modular systems are finite. Furthermore, our insights into the modular systems will enable us to solve a variety of interesting questions pertaining to the integers."

Section Two

The Modular Systems

"Back in Section 1, you promised to explain how the Black Magic Device handles negative numbers. Could it be that you conveniently forgot because you inconveniently don't know?"

"Unlike many nonmathematicians, I don't feel compelled to passively wait until other people explain things to me, Gnam. When an idea puzzles me, I play around with it until I understand. I question things! I suppose I've always known that if one doesn't want to carry around a lot of rubbish in one's head, it's necessary to be skeptical. Even as a child I questioned my teacher when she taught long division as follows:"

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

"She checked her answers in the following way:"

49 = 8 • 6 + 1,153 = 10 • 14 + 13,48 = 3 • 16 + 0,11 = 0 • 12 + 11.

"So I countered with:"

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

"And as proof, I offered the check: 49 = 5 • 6 + 19."

"Did your teacher mark that wrong?" asked Gnam. "My teacher, Mr. Rob, was a Rigid Old (ahem) Being and he would have marked it wrong."

"No, Ms. Far was Flexible and Reasonable. She encouraged me to think through the implications of what would happen if we allowed this. I soon discovered that I could get any quotient I wanted. I could even get a quotient of 0 by letting the dividend itself be the remainder: 49 = 0 • 6 + 49. Then Ms. Far showed me how I could get a negative remainder."

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

"What are you doing, Ant? Remainders aren't supposed to be negative! Nor are they supposed to be larger than the divisor. Everybody knows that!"

"I agree, Gnam. The standard convention requires that the remainder be a nonnegative number less than the divisor. This insures that every long division problem has a unique quotient and a unique remainder."

"My Friend, Mf, comes from a place called Ltac, where people Like to Alter Conventions. In particular, on the first Tuesday of every third month, the Ltacians agree to require all remainders to be greater than or equal to the divisor and less than twice the divisor. So, for example, when 14 is divided by 4, the quotient is 2 and the remainder is 6. The Ltacians arrive at this using repeated subtraction."

"And on the second Wednesday of every fifth month, the remainder interval is the set of integers greater than or equal to the negative of the divisor but less than zero."

"I'm sure that you find this all quite fascinating, Ant. But you have been digressing again from your promise to explain how the device handles negative numbers."

"The point is that the Division Algorithm also holds if the dividend is negative. For example, consider the problem -35 divided by 15:"

[ILLUSTRATION OMITTED]

"If you subtract -3 fifteens from -35, you arrive at 10 which is in the conventional remainder interval."

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

"Since -35 = -3 · 15 + 10 and 0 = 10 < 15, the quotient is -3 and the remainder is 10."

"Now that I understand how the Black Magic Device copes with negative inputs, let's move on to the question of how to use it with very large and very small numbers."

"Patience, Gnam! First I'd like us to investigate a device similar to the Black Magic Device, called the r11 machine. The r11 machine computes the remainder when an integer is divided by 11, but without going through the process of actually dividing by 11. Thus the r11 machine doesn't waste energy computing quotients too. But before I can show you how it works, I need to introduce some relevant notation and concepts.

"If an integer, a, is fed into the r11 machine, the output is denoted by r11(a). You can think of r11(a) as meaning 'what the machine r11 does to a'. For example, if you input the number 12, the notation 'r11(12)' represents the output. Since r11 computes remainders upon division by 11, r11(12) = 1. (This is read as 'r sub eleven of twelve equals one.')"

"Gnam, machines with the property that they spew out something when they're fed something, and do so in a consistent manner (that is, for each acceptable input, there is a unique output) are called functions. r11 is an example of a function from the set of integers (the set of acceptable inputs) onto Z11 (the set of possible outputs)."

"This is incredibly interesting, Ant. Please don't let my yawning disturb you."

"The concept of a function is one of the basic concepts of mathematics. Functions are integral to nearly every area of mathematics."

"You can also ignore my snoring."

"Well wake up, Gnam, because I'm about to introduce an addition on the elements of Z11 called mod 11 addition and denoted by +11. To motivate this definition, let's examine an 11-hour clock."

"An 11-hour clock?"

"Sure. Why not, Gnam? It's the kind of clock that is used on the moon Titan. It looks like this one.

"Now, if it is 8 o'clock on Titan, and 5 moon hours elapse, then it becomes 2 o'clock. That is, 8 + 5 = 2 on an 11-hour clock. We could also express this idea as

8 +11 5 = 2."

"I understand, Ant. But I don't see why the Titan's clocks have a 0 where the 11 belongs. Our 12-hour clock uses a 12, not a 0."

"There is a simple explanation for that," I responded. "Suppose that it is 3 o'clock on earth and 12 hours elapse. Then it's 3 o'clock again, right? In fact, any time t plus 12 is just t again on our clocks. On a 12-hour clock:

t + 12 = t and 12 + t = t.

"In other words, what we label as 12 behaves just like zero. We should have labelled it 0 not 12! The Titans, with their superior intellect, understand this. Hence the 0, rather than an 11 on their 11-hour clocks."

"The completed table constitutes a definition of mod 11 addition. But it is a rather bulky one, for it contains 121 distinct facts. It would be helpful to have a more concise definition."

"I thought of a way to add without using the clock or the table, Ant. A problem like 2 +11 3 is easy, since it has the same answer as in ordinary addition. But to find the answer to a problem such as 9 +11 3 just add like you usually do and then subtract 11. 9 + 3 = 12, but you have to subtract 11, so 9 +11 3 = 1."

"That works for mod 11 addition, Gnam, but ..."

"You can even use my approach to define mod 11 multiplication! For example, 2 · 3 = 6 in both ordinary and mod 11 multiplication. But to find 2 · 11 7 just think 14 and then subtract 11 to get 3. (That's the correct answer since if you make two moves of 7 on an 11-hour clock, you land on 3.)"

"But the answer to 5 ·11 9 isn't 45 - 11 = 34, Gnam. There is no 34 on the 11-hour clock. If, starting at 0 you move 9 five times (that is, move 45), you end up at 1, because 45 is 1 more than 44, a multiple of 11. 1 is the remainder when 45 is divided by 11. Or, as another example, to find 8 ·11 5 on an 11-hour clock, note that if you move 40, you make 3 cycles of 11 and then land on 7. That is, 8 ·11 5 = r11 (8 · 5) = r11 (40) = 7. In general, to multiply (or add) two numbers mod 11, you can just multiply (or add) them regularly and then put the product (or sum) through the r11 machine."

"We're almost ready to develop a remainder test for 11. But we need the help of a very important idea. Suppose that the Black Magic Device gave remainders upon division by 11, rather than 13. So, if you offered it the number 21, it would respond with 10. If you then offered it plus 12, it would respond with 0 since r11 (21) +11r1112) = 10 +11 1 = 0.

---

Excerpted from The Theory of Remainders by Andrea Rothbart. Copyright © 1995 Andrea Rothbart. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

---