160 Online Text Book

Contents
1 Introduction 5
1.1 Puzzles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Shunting trains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 River crossings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Scales and balances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Numbers and operations 11

2.1 The different types of numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 The basic arithmetic operations . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 The trichotomy law . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.2 Closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.3 Commutativity and associativity . . . . . . . . . . . . . . . . . . . . . 15
2.2.4 The distributive law . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.5 Identity elements and inverses . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.6 The cancellation laws . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.7 The monotone laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Those mysterious negative numbers . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Answers to the questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Introduction to Number Theory 25

3.1 Multiples and divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Quotient and remainder . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.2 Common divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.3 Two important consequences. . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Tests for divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.1 Tests for divisibility by 2 through 13 . . . . . . . . . . . . . . . . . . . 32
2 CONTENTS

3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Common multiples and divisors 39

4.1 Factors and primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.1.1 Factoring an integer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.1.2 The sieve of Eratosthenes . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.1.3 The infinitude of primes . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Finding the gcd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2.1 The prime factorization method for finding the gcd . . . . . . . . . . . 43
4.3 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4 Least common multiples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.5 When there are three or more integers . . . . . . . . . . . . . . . . . . . . . . 49
4.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5 Fractions, decimals, and percentages 53

5.1 Fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.1.1 Operating with the rationals . . . . . . . . . . . . . . . . . . . . . . . 54
5.2 Decimals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2.1 Converting between fractions and decimals . . . . . . . . . . . . . . . 60
5.3 Percentages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.4 Answers to the Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6 Modular Arithmetic 69
6.1 Congruent integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.2 Digital Roots and divisibility tests . . . . . . . . . . . . . . . . . . . . . . . . 76
6.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
7 Linear Diophantine Equations 81

7.1 The single variable case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
CONTENTS 3
7.2 The homogeneous case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

7.3 The linear case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.4 When there are constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.5 When there are more than two variables . . . . . . . . . . . . . . . . . . . . . 91
7.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
8 Number bases 95
8.1 Binary numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
8.2 Base-n blocks and the line abacus . . . . . . . . . . . . . . . . . . . . . . . . . 98
8.3 Addition of base-n numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
8.4 Multiplication of base-n numbers . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.5 Subtraction of base-n numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 105
8.6 Switching bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
8.7 Long division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
8.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5
1 Introduction
1.1 Puzzles
This chapter has a few puzzles for you to try. They are mathematical in nature, but do not
require a deep mathematics background. They do depend upon ingenuity and reasoning, and
usually require more than one attempt to solve. The solutions are within your capabilities
and the puzzles are intended for classroom use, so the answers are not given. The best way
(maybe the only way) to learn mathematics is to do it yourself.
The Die Hard jugs. In the film Die Hard With A Vengeance, the characters John
McClane and Zeus Carver open a briefcase only to discover that in doing so they
have armed a powerful bomb. It will explode in a matter of minutes unless they
can disarm it. Inside the briefcase there is a scale. They have at their disposal two
jugs—one holds exactly 5 gallons and the other holds exactly 3 gallons. To disarm
the bomb, they have to fill the 5 gallon jug with exactly four gallons of water and
place it on the scale. An ounce too much or too little will detonate the bomb. The
water can be obtained from a nearby fountain.
How can they disarm the bomb?
Could they do it if the jugs held exactly 9 and 6 gallons?
McClane and Zeus were able to solve the first part of this entertaining puzzle, but they would
have had a lot more difficulty with the the second part. The reason you cannot accomplish
the task with 9-gallon and 6-gallon jugs is that all transactions involve the addition or
subtraction of quantities that are multiples of 3 gallons, so the resulting quantity must
therefore be a multiple of 3 gallons.
If we use jugs that hold exactly 24 gallons and 30 gallons, then any quantity we could
measure would have to be a multiple of 6 gallons, because 6 is a divisor of 24 and 30. More
to the point, 6 is the largest number that divides both 24 and 30, and we express this by
saying that 6 is the greatest common divisor of 24 and 30. You will learn a lot more
about greatest common divisors in Chapter 4. The Die Hard jug problem has more than
one solution, and you will learn a way to find all solutions to problems like it in Chapter 7.
6 CHAPTER 1. INTRODUCTION
1.2 Shunting trains
Passing Trains. The two trains pictured above have to pass each other. Fortu-
nately, there is a siding, and the cars can be coupled and uncoupled to each other or
to the back of the engines. Unfortunately, there is only room enough on the siding
for one car or one engine, and the engines cannot push or pull cars with their front
ends. How can the trains pass each other?
Can you do it if each train has an engine and two cars?
Train shunting problems were very popular at the beginning of the 20th century. Sam Loyd
(see the references at the end of the these notes) had several, including a version of this
problem with 4 cars per train.
1.3 River crossings

River crossing puzzles are also very popular. The prototype was given by Lewis Carroll
wherein a farmer had to transport a fox, a goose and a bag of corn across a river with a
boat that could only hold the farmer and one other thing. Of course, the goose would eat
the corn if both were left unattended on shore, and likewise the fox would eat the goose.
Here are two more examples. The first is from Ian Stewart’s Another Fine Math You’ve Got
Me Into and is a fairly clear extension of the fox, goose, and corn puzzle.
The lettuce fearing leviathan. A farmer is taking his prize lettuce, lion, llama,
and pet leviathan to market. Unsupervised, leviathans eat lions unless a lettuce is
present. A boat awaits him to cross a river, but he can only take one item at a time.
How can the farmer cross the river, without the llama eating the lettuce, the lion
eating the llama, or the leviathan eating the lion?
1.4. SCALES AND BALANCES 7
The second is by Henry Dudeney, a renowned British puzzler from the early 1900’s.
Getting an army across a river. During the Turkish stampede in Thrace, a

small detachment found itself confronted by a wide and deep river. However, they
discovered a boat in which two children were rowing about. It was so small that
it would only carry the two children, or one grown person. How did the officer get
himself and his 357 soldiers across the river and leave the two children finally in joint
possession of their boat? And how many times need the boat pass from shore to
shore?
1.4 Scales and balances

There are many recreational math puzzles that involve weighing things with either balances
or scales. Here are two fairly well known ones.
A heavy counterfeit. There are eight coins, all identical in appearance. One
is fake and weighs slightly more than the others. Using a balance scale, find the
counterfeit in as few weighings as possible.
The question is asking for the minimum number of weighings in the worst case scenario. If
your strategy is to compare coin #1 against coin #2, then #2 against #3 etc., you may
be lucky enough to find the counterfeit coin in the first weighing, but in the worst case
scenario, this strategy wouldn’t find the fake until you compare coins #7 and #8, so this
method would take 7 weighings. Most people can find a strategy that guarantees that the
fake can be found in three weighings. The appeal of coin weighing problems is that the
optimal solution is better than “obvious” solution. So, can you do better than three?
Sort the tokens. You have 4 tokens weighing 3, 5, 6 and 9 grams. One is red, one
is white, one is blue and the fourth is green, but none of them have their weights
marked. Using a balance scale what is the least number of weighings needed figure
out their weights? You are only allowed to use the tokens themselves.
8 CHAPTER 1. INTRODUCTION
1.5 Exercises
1. Interchange the positions of the red chips and the
blue chips. The rules are as follows:
R R R
• A chip may be moved into an empty space
that is connected to it by a line.
• A chip may jump over one chip of the opposite
colour provided it jumps in a straight line, B B B
follows the lines of the board, and lands in an
empty space.
2. Cups and ball (From Andy Liu and Bill Sands). There are six cups, all upside
down in a line. Hidden under one of them is a precious spherical jewel. The object
of this game is to find the hidden jewel. You are allowed to lift up the cups one at a
time, however, after each time, you must leave the room and the jewel must be placed
beneath a different but adjacent cup. So, for example, if the jewel was beneath cup #
4, it must be placed beneath either cup # 3 or cup # 5.
You are only permitted 12 tries, and you must announce before the game begins the
order in which you will lift the cups.
If there were only two cups, you could win this game in at most two turns: Look under
cup #1 twice. If there were only three cups, look under cup #2 twice. If there were
4 cups, it becomes more interesting.
3. (From Boris Kordemsky’s The Moscow Puzzles.) Place seven dots on a circle. Get 6
coins, and staring with any dot and counting clockwise and place a coin on the third
dot. Then, starting with any dot that is not yet covered, count clockwise and put a
coin on the third dot. Do not skip dots that are covered. Explain how to place the
six coins so that no two are on the same dot.
4. Smith and Smith Pharmacies has received a shipment of children’s vitamin pills. The
pills are coloured red yellow, green, blue and purple. Unfortunately, all of the pills of
a certain colour are defective, while all the rest are safe. The safe pills each weigh 8
grams. The defective ones each weigh 8.1 grams. How can the pharmacy detect the
defective pills in a single weighing on a scale (not a balance).
5. A wholesaler of golfing equipment was swindling his retailers by including one box
of substandard golf balls to every nine boxes of top grade balls he sold them. Each
box contained 6 golf balls, and the external appearance of all the balls was identical.
However, the substandard balls were each 1 gram too light. The retailers were informed
of this discrepancy. The boxes all arrived in packs of ten, each with one substandard
box—but which one?
Phoebe Fivewood, the professional at a prestigious golf course, had just taken delivery
of a large order so needed to sort them out quickly. She soon found a way to do this
using a pair of scales (not pan balances) which required only one weighing on each
1.5. EXERCISES 9
scale for each batch of ten boxes. How did she do it? Note that she did not need to
know what a golf ball should weigh.
6. Three bears and three humans have to take a boat from one island to another island.
One bear is a special bear who can row the boat. The boat can hold no more than
two. There can never be more bears than humans on either island or the human will
be killed. How can this be done?
7. (Found in several places on the web.) Three warlords are on one side of a river. Each
is accompanied by his young son who is not quite ready for battle yet. All six want to
cross the river but there is only one boat to shuttle them back and forth. This boat
can hold at most two people. All three warlords and the eldest young son (four people
altogether) can operate the boat. How do you scuttle them safely across the river?
Leaving a son unattended by his own father in the presence of another warlord in any
situation will result in terrible death for the young one.
8. (From Brian Bolt’s The Amazing Mathematical Amusement Arcade.) A number of
playing cards of the same suit were arranged in a circle on the table in such a way
that the total of the face values of any set of three adjacent cards differed by at most
one from the total for any similar set. The highes and lowest cards on the table were
the 10♦ and 2♦. The 6♦ was also in the circle. What cards were on the table and
what was their order?
9. Crossing the bridge. This has become a classic. Four people are being pursued by
a menacing beast. It is nighttime, and they need to cross a bridge to reach safety. It is
pitch black, and only two can cross at once. They need to carry a lamp to light their
way. The first person can cross the bridge in no less than 10 minutes, the second in 5
minutes, the third in 2 minutes, and the fourth in 1 minute. If two cross together, The
couple is only as fast as the slowest person. (That is, a fast person can’t carry a slower
person to save time, for example. If the 10-minute person and the 1-minute person
cross the bridge together, it will take them 10 minutes.) The person or couple crossing
the bridge needs the lamp for the entire crossing, and the lamp must be carried back
and forth across the bridge (no throwing, etc.)
If they don’t all get completely across in strictly less than 19 minutes, who ever is on
the bridge or left behind will be eaten by the beast. Is it possible for all of them to
get across?
11
2 Numbers and operations

2.1 The different types of numbers
The numbers that we deal with in this course are all subsets of the real numbers. They are
the natural numbers, the integers, the rationals and the reals themselves.
The natural numbers are the numbers 1, 2, 3, . . . .

The integers are . . . , −2. − 1, 0, 1, 2, 3, . . . .
The rational numbers are the numbers that can be written in the form a/b where a
and b are integers and b 6= 0.
The irrational numbers are the real numbers that are not rational numbers.
All natural numbers are integers but not all integers are natural numbers. All integers are
rationals but not all rationals are integers. Similarly, all rational
√ numbers are real numbers,
√
but not conversely—we shall see later that numbers like 2 and 6 are irrational. Because
each set is a subset of the next, it may seem sensible to view the development of the number
system as going from natural numbers to integers to rational numbers to real numbers.
History, however, did not follow this nice logical progression (see the timeline on page 118
in the appendix). By the time written languages appeared, the natural numbers and the
positive fractions were already in use. The natural numbers were needed for counting things
like money or cattle and the fractions were needed to measure and compare things like area
and weight.
Then came the number zero—it popped up at different times in different places, but always
after the development of fractions. Some civilizations never did get around to admitting
zero into their number system. The Romans did not even have a symbol for it.
In The nothing that is: a natural history of zero, Robert Kaplan presents a case that the
zero symbol originated with the Babylonians, was taken up by the Greeks and transported
to India by the armies of Alexander and then to China and Arabia and back to Europe.
Although the Babylonians did have a symbol for zero, the consensus is that zero was never
treated as a number—it was used only as a place holder like the zero in the number 102.
The Babylonians never talked about a zero quantity, but spelled it out verbally: “So-and-so
is owed nothing”.
In 1202 Fibonacci introduced the Hindu-Arabic numerals that we use today: the symbols
from 1 to 9 (which he called figures) and the symbol for zero (which he called a sign rather
than a figure). It took another 300 years before zero was accepted as a member of our
number system. Other civilizations twigged onto the fact somewhat earlier—for example,
by 1200AD in India they had already worked out arithmetic rules for operating with zero
and negative numbers.
12 CHAPTER 2. NUMBERS AND OPERATIONS
By the middle of the 16th century, the number zero was being used more frequently. Negative
numbers were appearing on stage as a necessary part of double entry bookkeeping, and the
number zero became a necessary ingredient in understanding them. Like zero, negative
numbers were slow to be accepted as numbers in their own right. John Napier, the inventor
of logarithms, and the person who popularized our present use of decimal fractions, referred
negative numbers as defectivi at the beginning of the seventeenth century.
From the late fifteenth century through the sixteenth century other changes were happening
to our number system. Decimal fractions were introduced. Also appearing for the first
time were the plus and minus signs as we know them today, the ‘ × ’ for the multiplication
sign, and ‘ = ’ for the equal sign although these were not universally used. (The division
symbol ‘ ÷ ’ first appeared a century later.) In the sixteenth century, people also began
using variables for numbers. At that time, they were still avoiding negative numbers, and the
solutions for quadratic equations would have been broken into special cases: 3x2 −2x−5 = 0
would be transformed into 3x2 = 2x+ 5 and considered to be of the form ax2 = bx+ c rather
than belonging to the general form ax2 + bx + c = 0. Surprisingly, the rules for operating
with negative numbers were known. However, the rules applied only to expressions like
(a − b)(c − d) where the negatives were less than the corresponding positives1 .
To put things in a historical setting, here are a few of the notable events of the sixteenth
century: By 1500, Gutenberg had printed his bibles, Columbus and da Gama had made
their momentous voyages. Da Vinci had painted the Mona Lisa, and Michaelangelo would
soon complete his work in the Sistene Chapel. The Renaissance was underway. A new class
of entrepreneurs was arising—ones who sent other people to buy and sell goods—and this
lead to the creation of double entry bookkeeping mentioned above.
In the sixteenth century the calendar was seriously out of whack. In 1582 a new calendar,
the Gregorian Calendar, was introduced and the discrepancy was fixed by removing the
dates from Oct 5 to Oct 14 for that year2 .
The protestant reformation was underway. By 1534 Martin Luther had translated the Bible
into German. It was not a good time to have unorthodox views—in 1572, 20,000 protestants
were slaughtered on St Bartholomew’s day in Paris. Between 1450 and 1750 about 100,000
witches were killed. The hunt intensified after 1580.
Copernicus died in 1543. He was one of the astronomers who declined an invitation to
participate in the reform of the calendar because he was convinced that it was impossible
to reconcile the discrepancies with an earth-centric approach. His heliocentric theory was
published in the year of his death. Kepler developed his laws for the movements of the
planets by the turn of the century. The telescope was invented in 1608 and Galileo was
imprisoned in 1616.
Further advances in our understanding of the number system occurred in the late eighteenth
1 The rule would say something like this: To find (6 − 4)(5 − 2), multiply the 6 by the 5, add to it 4 × 2,
subtract 4 × 5 and subtract 6 × 2—in other words the negative 4 multiplied by the negative 2 is the positive
4 by 2.
2 The Gregorian calendar is the one we use today, but it was not adopted everywhere at the same time.
Britain adopted it in 1752, Russia in 1917. Even today some religious celebrations are based on the old
Julian Calendar.
2.2. THE BASIC ARITHMETIC OPERATIONS 13
and nineteenth century. The notion of a real number was given a solid foundation, and the
now familiar correspondence between the real numbers and the points on a straight line was
established.
The introduction of numbers to young children generally reflects the historical progression—
first, whole numbers, then fractions, and then the negative numbers. You already have some
familiarity with these concepts, and so it becomes possible to follow the “logical” develop-
ment of the number system—whole numbers, then integers, then rational and irrational
numbers, based on the algebraic rules for dealing with them.
2.2 The basic arithmetic operations
Your favourite number. Everyone has a favourite digit. You can’t have 8 because
that’s mine. The digits that are left form the magic number 12345679. Circle your
favourite digit, perhaps 1, or 2, etc. Jan circled the number 6, and Ali circled number
4. I asked Jan to multiply the magic number by 54 and I asked Ali to multiply the
magic number by 36. They both got a plentiful supply of their favourite digit. What
would you multiply by to get a supply of your favourite digit? Why does this happen?
One of the reasons that mathematicians were hesitant to accept irrationals and negative
numbers as actually being numbers was an incomplete understanding of how they operated.
One of the important things that happened in the nineteenth century was that Algebraists
distilled the rules for operating with real numbers to a very few from which all others
could be derived. This overcame the reluctance and ushered in the modern age of algebra,
for it was soon realized that the rules governing our real numbers also govern many other
mathematical structures—such things as complex numbers, vectors, and a great number of
families of functions. What this meant was that any consequences of the rules told you
things not only about the real numbers, but also about a great many other systems.
The basic rules have had a huge impact on the way mathematics is taught. In this section,
the basic rules are discussed. You will find that they are very familiar, but what might
surprise you is the fact that there are so few of them.
A binary operation is a mathematical operation that applies to two things to produce

a third thing.
A unary operation is an operation that applies to exactly one item.
Addition is a binary operation because it applies to two numbers and the result is another
number. Multiplication, subtraction, and division are also binary operations. Taking the
reciprocal of a number is a unary operation because it applies to exactly one number and
produces another number.
Addition and multiplication are viewed as being more fundamental than subtraction and
division because the latter two operations are usually defined as being the ones that “undo”
the former.
2.2.1 The trichotomy law

We sometimes visualize the real numbers as being orderly strung out along a straight line.
There are number systems where this perception does not work, for we usually do not view
complex numbers in this way. The property of real numbers that gives us this linear ordering
is called the trichotomy law :
The trichotomy law.

For every real number r, either r > 0, r = 0, or r < 0.
By using the binary operation of subtraction, we can extend the trichotomy law to pairs of
real numbers. For real numbers a and b, we define a > b to mean that a − b > 0 and define
a < b to mean that a − b < 0. So the trichotomy law implies that:
Given two real numbers a and b, either a > b, a = b, or a < b.
2.2.2 Closure
For binary operations, the first questions we ask are:
1. Is set of numbers we are dealing with closed under the operation?
2. Is the operation commutative or noncommutative?
3. Is it associative or nonassociative?
A set of numbers is closed under a given operation if the result of applying the operation
always produces another number that is in the set.
Question 2.2.1. Given the following sets of numbers, which are closed under addition?
subtraction? multiplication? division?
(a) The set {1, 2, 4, 8, 16, . . .}. (b) The set {. . . , 81 , 14 , 12 , 1, 2, 4, 8, . . .}.
(c) The set of all integers that are multiples of 3. (d) The set of all odd numbers.
2.2.3 Commutativity and associativity

Because there are several different types of binary operations, we use the symbol “◦” to talk
about them in general.
A binary operation “◦” is commutative if a ◦ b = b ◦ a .

A binary operation, “◦”, is associative if a ◦ (b ◦ c) = (a ◦ b) ◦ c.
The notions of commutativity grew out of our experience with small natural numbers. If
we have five objects in our left hand and seven in our right hand and if we drop them into
an empty basket, we expect that total the number of objects in the basket will be the same
no matter which hand is used first. In other words, 5 + 7 = 7 + 5.
Similarly, our experience with small collection of objects leads to the associative law. If
we have three piles of objects—the first containing 4 things, the second 5, and the third
6—when we gather the objects into one pile we expect the total number to be the same
whether we combine (that is, associate) piles one and two first, or whether we combine piles
two and three first.
For the set of real numbers, addition and multiplication are associative; subtraction and
division are not. For example, how do you evaluate the expression 24/4/2? Division is a
binary operation, so it only applies to two numbers at a time. With 24/4/2, we seem to
have a choice: Either we first compute 24/4 and then divide that result by 2, or we first
compute 4/2 and then divide 24 by that result. The answers are different, so division is
nonassociative.
If an expression only involves addition, associativity allows us to write a + b + c + d without
causing ambiguity. The same is true for multiplication.
Note that when an expression involves two operations, associativity will not hold for the
mixture. For example, a + (b × c) and (a + b) × c are not likely to be the same.
Question 2.2.2. Is there an associative law of addition for four numbers?
Question 2.2.3. If you have a basket of 10 apples and remove 2 with your left hand and
4 with your right hand the result is the same as if you remove 4 with your left hand and 2
with your right hand. Doesn’t this prove that subtraction is commutative?
Precedence
Whenever an arithmetic or algebraic expression is given, we would like to have an agreed
upon way of interpreting it. For example, if we are given the following,
7
+ 3 − 8 ÷ 2 × 5,
9
we would like to be able to actually carry out the computation without complaining that it
is ambiguous.
Note that it is impossible to foresee every possible combination. The way out is to restrict
what an arithmetic expression can be—expressions like 6 + 7 − ÷ + 3 or 5 + (÷3) are simply
considered as being invalid. In computing science, you would probably get a “syntax error”
message if you put either of those expressions in your program.
However, for any valid expression, the rules of precedence are well established:
Rules of precedence
1. Functions are evaluated first.

2. Expressions inside parentheses or brackets are evaluated next.
3. Multiplication and division are next, and are evaluated left to right.
4. Addition and subtraction are last, and are evaluated left to right.
When we say that multiplication and division are evaluated left to right it means that in
the absence of any parentheses, an expression like
12 · 6 ÷ 8 ÷ 3 · 5
is evaluated as
(((12 · 6) ÷ 8) ÷ 3) · 5.
A similar meaning applies to addition and subtraction.
When there are parentheses, the rules of precedence force us to begin with the innermost
ones. In the following expression:

5 − (2 − 1) × 9,
we have to evaluate what’s inside the large parentheses before we multiply by 9, that is, we
have to first evaluate 5 − (2 − 1). But the rules of precedence also apply to 5 − (2 − 1) and
this means that we have to evaluate what’s inside the inner parentheses, and so on.
A similar situation arises with respect to functions. In the expression
p
a + (4 + 4) × 8 ÷ 3 ,
the square root is a function and should be evaluated first. But the input to the square root
function should be a single number, so we have to evaluate (4 + 4) × 8 before we can apply
it.
Question 2.2.4. Evaluate each of the following expressions
(a) 1 + 5 · (4 − 2).
(b) 48 ÷ 4 ÷ 2 · 3 + 4 ÷ 2 − 1.
(c) 48 ÷ 4 ÷ (2 · 3) + 4 ÷ (2 − 1).
7
(d) 8÷2×5− 9 − 3.
2.2.4 The distributive law

The distributive law links addition and multiplication, and it is ultimately leads to such
other laws such as “a negative times a negative is a positive”.
Multiplication distributes over addition: a(b + c) = ab + ac.
For small natural numbers, this law is derived from experience with the meaning of addition
and multiplication. Suppose we are trying to compute 4(3 + 2). The parentheses tell us to
compute this as follows: 4(3 + 2) = 4(5) = 20.
For the natural numbers, most people think of multiplication as being repeated addition.
So another way to interpret the expression is
4(3 + 2) = (3 + 2) + (3 + 2) + (3 + 2) + (3 + 2),
and then using the commutativity and associativity properties of addition, we get
4(3 + 2) = (3 + 3 + 3 + 3) + (2 + 2 + 2 + 2)
= 4(3) + 4(2).
We cannot check all possible combinations of natural numbers, but there is no reason to
expect the distributive law to fail no matter how large the numbers are. By extension from
natural numbers to the integers, to the rationals, and finally to all real numbers, we expect
the distributive to hold there as well.
2.2.5 Identity elements and inverses

When learning about how a set of numbers behaves with respect to a particular binary
operation, we look for identity elements and inverse elements.
Any element that leaves things unchanged when it takes part in the operation is called
an identity element.
Two elements are said to be inverses of each other if the result is the identity when the
binary operation is applied to them.
For addition, the number 0 is the identity element, and it is sometimes called the additive
identity. The numbers 5 and −5 are inverses with respect to addition in the set of integers
and are often called additive inverses of each other.
The number 1 is the multiplicative identity. In the set of rationals, 7/4 and 4/7 are
inverses with respect to multiplication and so they are said to be multiplicative inverses
of each other.
Do you know why you cannot divide by zero? It is a consequence of the fact that no matter
what a is, the product a · 0 must be zero, a fact that almost everyone takes it for granted.
If you ask them why the product is zero, you might get some curious answers. The reason
it that if we want our number system to follow its laws, we have no choice in the matter,
and here is the proof.
Theorem 2.2.5. a · 0 = 0 for every number a.
Proof. We begin by using the fact that 0 + 0 = 0:
a(0) = a(0 + 0) (definition of 0).

= a(0) + a(0) (distributive law)
Now let x denote the additive inverse of a(0), and add it to both sides of the equation.
a(0) + x = (a(0) + a(0)) + x

a(0) + x = a(0) + (a(0) + x) associative law.
0 = a(0) (definition of x)
This completes the proof.
It is this theorem that tells us we cannot divide by zero. Suppose, for example, that 9 could
be divided by zero, and that the result was the number a. Since division is what undoes
multiplication, this means that a · 0 = 9. But we have just seen that for every number a, the
product a · 0 must be zero. So it doesn’t make sense to divide a nonzero number by zero.
What about 0/0? This doesn’t make sense either. If it did, then 0/0 would have to be a
specific number, say x. Then, by definition of division, 0 = 0 · x. But this is true no matter
what x is, so there is no specific number that works.
2.2.6 The cancellation laws

If someone tells you that 5 + x = 5 + 7, almost immediately you would apply the cancellation
law for addition and write x = 7. You can actually prove that this cancellation law is true
by using additive inverses. There is a similar cancellation law for multiplication.
The cancellation laws. If a, x and y are real numbers, then
a+x=a+y =⇒ x = y, for all a.

ax = ay =⇒ x = y, provided a 6= 0.
Question 2.2.6.
(a) In the set of integers, what is the additive inverse of 0?
(b) What members of the set of rationals have multiplicative inverses?
2.2.7 The monotone laws

The final basic properties that we often use are the ones that help us deal with inequalities.
We say that a is greater than b (and we write a > b) if a − b is positive. (Note that ‘ > ’
is a binary relation, not a binary operation.)
The monotone law of addition: If a > b and if c is any number, then a + c > b + c.
The monotone law of multiplication: If a > b and if c > 0 then ac > bc. If c < 0
then ac < bc.
The notation a < b of course is read “a is less than b” and it means exactly the same as
b > a.
The definition of “greater than” implies that −4 > −5. Saying a is greater than b does not
mean that a is farther from 0 than b is. If you display the numbers on a horizontal number
line with the positive numbers to the right of zero, a > b means that a is to the right of b.
The notations a ≥ b and a ≤ b should also be mentioned since they sometimes cause
confusion. ‘Greater than’ and ‘less than’ are binary relations. The notation a ≥ b is read a
is greater than or equal to b, and what it really means is that either a > b or a = b.
Question 2.2.7. For which of the following values of x is the statement x ≤ 5 true?
(a) x = −6, (b) x = 0, (c) x = 4, (d) x = 5, (e) x = 6.
2.3 Those mysterious negative numbers

People often have trouble with negative numbers and will frequently go to great lengths
to avoid using them. In the book Overcoming Math Anxiety, Sheila Tobias has put her
finger on the reasons for the confusion, which is that the negative sign carries with it several
different meanings.
(1) The negative sign represents the binary operation that undoes addition. We are
using this interpretation when we say that 13 − 8 is 5 because 5 is what we have to
add to 8 in order to get 13. People learn this interpretation of the negative sign before
any of the others.
(2) The negative sign is an identification tag, that is, it is used to identify the additive
inverses of the “unsigned” numbers. We are using this meaning when we say that
−8.372 is the additive inverse of 8.372.
(3) To negative sign is a unary operation that means “take the additive inverse” of the
given number. This is close to, but not exactly the same as (2) because here it applies
to all numbers. This interpretation can be also be described by saying that the minus
sign means “take the number with the opposite sign”. This is the meaning that we
are using when we say that −x is the inverse of x, where x represents any number,
positive or negative. For example, if x = −5, then −x is the additive inverse of −5,
which means that −x = 5.
It is no wonder that there is confusion! Here are some examples that may help clarify what’s
happening.
Example 2.3.1. In each of the following cases, identify how the negative signs are be-
ing interpreted, and explain why the equation is true without actually carrying out the
computation.
1. 7 − 5 = 7 + (−5).
2. 6 − (−8) = 6 + 8.
3. (−1)x = −x.
If you can follow the solutions below, you should be equally comfortable with all three
interpretations of the negative sign, and be able to use them with ease.
2.3. THOSE MYSTERIOUS NEGATIVE NUMBERS 21
Solution.
1. The negative sign in 7 − 5 is interpreted as subtraction. The negative sign in 7 + (−5)
is being used as a tag to identify the additive inverse of 5.
The objective is to show that whatever 7 − 5 is, it must be the same as 7 + (−5).
Suppose x = 7 + (−5). Begin by adding 5 to both sides of the equation:
x + 5 = (7 + (−5)) + 5.
x + 5 = 7 + ((−5) + 5) (associative law)
x+5=7+0 (5 and (−5) are additive inverses)
x+5=7 (0 is the additive identity)
x=7−5 (definition of subtraction)
7 + (−5) = 7 − 5 (definition of x)
Note: The important thing here is that we were able to conclude that the expressions
7 − 5 and 7 + (−5) were identical without actually evaluating them.
2. In 6 − (−8) the leftmost negative signs denotes subtraction, the other negative sign is
a tag to identify the additive inverse of 8.
Let x = 6 − (−8). By definition of subtraction, this means that x is the number that
must be added to −8 to get 6:
x + (−8) = 6
(x + (−8)) + 8 = 6 + 8 (Added 8 to both sides)
x + ((−8) + 8) = 6 + 8 (associative law)
x+0=6+8 (8 and (−8) are additive inverses)
x = 6 + 8. (additive identity)
6 − (−8) = 6 + 8. (definition of x)
3. Note that question 3 is really a theorem that shows us that −x can also be interpreted
as (−1)x.
In (−1)x, the negative sign is a tag to identify the additive inverse of 1. In −x the
negative sign is the unary operator that means “take the inverse of the number x”.
The quickest way to prove this is to show that x + (−1)x is always zero:
x + (−1)x = (1)x + (−1)x, (1 is the multiplicative identity)

= (1 + (−1))x, (distributive law)
= (0)x, (1 and (−1) are additive inverses)
= 0, (by Theorem 2.2.5)
2.4 Answers to the questions

2.2.1 set Add’n Subtr Mult Div
(a) Y N Y N
(b) N N Y Y
(c) Y Y Y N
(d) N N Y N
2.2.2 Yes. For example it doesn’t matter how we group the terms, so given an expressionlike
(7 + 6) + (3 + 4) we can
also evaluate this also as (7 + 6) + 3 + 4 or as 7 + (6 + 3) + 4
or as 7 + (6 + 3) + 4 and so on.
2.2.3 No. This says that (10 − L) − R = (10 − R) − L. To be commutative you would have
to say that 10 − (L − R) is the same as 10 − (R − L).
2.2.7 The statement is true for all cases except (e).
2.2.4 (a). 17, (b). 19, (c). 6, (d). 16 92 .
2.2.6 (a). 0, (b). All but the number 0.
2.5 Exercises
1. Which of the following sets are closed under (i) addition, (ii) multiplication, (iii)
subtraction, (iv) division.
(a) The set of all multiples of 5.
(b) The set consisting of the single element 0.
(c) The set consisting of the single element 1.
(d) The set of all negative integers.
(e) The set of all rational numbers of the form n/3, where n is a an integer.
2. Here is one of the very earliest methods for multiplication. (This was the method
used by the ancient Egyptians, which may have been borrowed from Africans living
to the south of Egypt.) To multiply 235 by 13, carry out the following: Successively
multiply by 2 (which can be obtained by adding a number to itself):
by 1 = 235
by 2 = 470 (which is 235 + 235).
by 4 = 940 (which is 470 + 470).
by 8 = 1880 (etc.)
Then, look for the numbers on the left that sum to 13 and then the sum of the
corresponding numbers on the right will be 13 × 235. In this case, 1 + 4 + 8 = 13,
so 13 × 235 = 235 + 940 + 1880. Using the basic rules for the arithmetic operations,
explain why this works for the product 26 × 215 without actually carrying out the
computation.
2.5. EXERCISES 23
3. An archaeologist has commissioned you to settle an argument about some printed

artifacts that are purported to be arithmetic tables of some sort. Some investigators
believe that fragments A, B and C shown below represent parts of addition or multi-
plication tables, while others are not so sure because they do not know if the symbols
even represent numbers.
Can you settle the argument?
; 1 2
: a b c d ' 1 2 3 4
3 4
a d b 1 0 1 2 3
1 1 2 3 4
b d a c 2 y 1
2 D 4 6 8
c b b 3 g
3 3 6 9 C
d c b 4 z x
8 C X
A B C
If you draw a multiplication table (even with numbers missing) you will discover that
fragments A and C don’t have the proper “pattern”, and you could use that to convince
the archaeologist that neither is multiplication. It is much more difficult to see why B
also fails to have a proper “pattern”. but after a bit more work, you may be able to
discover it.
N
4. Erica has a faulty calculator. The symbol for multiplication on her calculator is .
Whenever she multiplies two integers, it always produces N an answer that is 1 larger
than it should be. For example when she calculates
N 4 5 it provides an answer of
21 instead of 20, and when she calculates
N 3 9 the result is 28 instead of 27. In
other words the operation shown as is a mathematical operation, but it is not
multiplication.
N
(a) Is commutative? Explain.
N
(b) Is associative? Explain.
5. Does multiplication distribute over subtraction?
6. Does division distribute over addition?
7. I have a calculator that displays 12 digits. Explain how I can use it to find the product
of 123456 and 246897531. I need an exact answer. (Hint: make use of the distributive
law.)
8. You have a calculator with a defective multiplication button. Since multiplication can
be performed by repeated addition, you can compute 13762 × 5 by repeatedly adding
13762 to itself (13762 + 13762 + 13762 + 13762 + 13762). You need to find 13762 × 134
Show how you can use the calculator to find the product by adding 8 numbers.
9. You have a four-function calculator with a defective multiplication button. (The
addition, subtraction, and division functions all work with high precision). Show how
to find the product of 13762 and 134 using this calculator.
10. Find the quotient and remainder when the fifteen digit number 77756 33312 9099 is
divided by 1234567. Assume that you are using a calculator in which you can enter
up to 12 digits. An exact answer is required.
11. You have a two-function calculator—it can perform additions and subtractions. If you
wanted to find the remainder when 314159 is divided by 89746 you could repeatedly
subtract 89746 from 314159 until the result first became less than 89746 (It would
only take 3 subtractions). Use this calculator to find the quotient and remainder
when 314159 is divided by 2718? (It should take less than 10 subtractions).
12. (a) Using the rules of precedence outlined in this chapter, compute 7 − 2 + 4 × 5.
(b) Insert parentheses in such a manner that the computation conforms exactly to
the rules of precedence.
(c) Find all possible different values that can be obtained by using parentheses to
override the rules of precedence. Keep the numbers and signs in the same order.
Make sure that the parentheses only change the precedence and do not introduce
any extra operations. For example, inserting parentheses into 5 − 6 + 1 to get
5−(6+1) just changes the precedence while 5(−6+1) introduces a new operation.
13. Using four 4’s and only the four arithmetic operations and parentheses, make as many
of the integers from 1 to 10 as you can. For example:
44 4 4 4+4+4
= 1, + = 2, = 3.
44 4 4 4
Note: exponentiation is not allowed and all four 4’s must be used.
14. Identify the meaning of the negative signs and explain why (−5)(−4) = 20.
15. Identify the meaning of the negative signs and show that (−a)b = −(ab).
25
3 Introduction to Number Theory
The locker problem. There are 1000 lockers numbered in order from 1 to 1000
along a hall. At any given point, each locker is in one of two possible states—either
its door is open or its door is closed. To begin with, all of the of the locker doors are
closed. You are given the following step by step instructions:
1. Change the state of all of the lockers.

2. Change the state of every second locker.
3. Change the state of every third locker.
..
.
999. Change the state of every 999th locker.
1000. Change the state of every 1000th locker.
Your problem is to determine which lockers will be open and which will be closed.
Here is how you can try to solve the problem: Take several slips of paper, say about 20. On
one side write the numbers from 1 to 20, and on the other side do the same but circle the
numbers. A circled number will indicate that it is an open locker. Put the pieces of paper
in a row with the circled numbers down. Now follow the instructions (you change the state
by turning the slip of paper over). Can you make an educated guess about which lockers
are open? Can you explain why your guess is correct?
3.1 Multiples and divisors
If n can be obtained from an integer d by multiplying d by another integer, we say that

n is a multiple of d. For example, 15 and −25 are both multiples of 5.
We also express the same thing by saying that n is divisible by d, or that d divides n,
or that d is a divisor of n or that d is a factor of n.
The following statements all mean the same thing:

“12 is a multiple of 4.” “12 is divisible by 4.” “4 divides 12.” “4 is a divisor of 12.”
“4 is a factor of 12.”
26 CHAPTER 3. INTRODUCTION TO NUMBER THEORY
A vertical bar is used to denote divisibility: d | a is read “d divides a”. That’s a vertical
bar, not a forward (/) or backward (\) slash, and take note of the order: if you want to
state that 7 divides 21, you write “ 7 | 21 ” not “ 21 | 7 ”. When a does not divide b, we
write a6 | b.
Note that if d divides n then so does −d. For example, the divisors of 6 are ±1, ±2, ±3, ±6.
However, in many cases we are only interested in the positive divisors.
Question 3.1.1. Write down all the positive divisors of the integers 8 through 15. Which
of these integers has the greatest number of positive divisors?
Question 3.1.2. What integers divide all other integers.?
Question 3.1.3. What integer is a multiple of every positive integer?
When you are trying to list all positive divisors of a number n, keep in mind that if d is
a divisor, then so is n/d. You can cut your work significantly by using this. For example,
with 24, as soon as we discover that 3 is a divisor we also know that 8 is also a divisor.
In general, when trying to find all positive divisors
√ of an integer n, you only need to check
those integers that are less than or equal to n as Theorem 3.1.4 shows.
√
Theorem 3.1.4. Every √ positive divisor of n that is greater than n must be paired with
one that is less than n.
Proof. To prove this, all you need to know is that when you multiply an inequality by a
positive quantity, it keeps the
√ sense of the inequality. Here’s how the proof
√ goes. Suppose
d is a divisor of n with d > n. Multiply both sides of the inequality by n/d:
√ √
n √ n
d· > n· .
d d
√ n
Then carry out the multiplication to get n> .
d
Example 3.1.5. Find all divisors of 1092.
√
Solution. Since 1092 < 34, we need only test the integers from 1 to 33. Here are the
divisors, paired as indicated:
d= 1 2 3 4 6 7 12 13 14 21 26 28
1092/d = 1092 546 364 273 182 156 91 84 78 52 42 39
3.2. DIVISIBILITY 27
3.2 Divisibility
Theorem 3.2.1 (Basic properties of divisibility).
1. If d | b and b | c then d | c. (This is also phrased by saying that divisibility is transi-
tive.)
2. If d | b then d | nb for any integer n.
3. If a = b + c, and if d divides any two of a, b, and c, then d also divides the third one.
Proof. We will prove statement 3 and leave the rest as exercises.

Suppose that d divides a and b. We want to show that d divides c, which means that we
have to show that c = kd for some integer k. Since d divides a and b we know that a = nd
for some integer n and that b = md for some integer m. Since a = b + c, we know that
c = a − b. Substituting nd and md for a and be we get
a = nd − md = (n − m)d.
Since n and m are integers, so is n − m, so we have shown what we wanted.
Question 3.2.2. Use the basic properties of divisibility to explain the following.
(a) If x | 17 then x | 34.

(b) 7 | 161x for every integer x.
(c) If x, y and z are integers with x + 4y = 12z, then 4 | x.
Recall that cancellation law states that if a 6= 0 and ax = ay, then x = y. This is useful
when dealing with divisibility.
Example 3.2.3. Given that 3x is divisible by 12, explain why x is divisible by 4.

Solution. Since 12 | 3x, we have 3x = 12n for some integer n, that is, 3x = 3(4n). The
cancellation law now tells us that x = 4n, so 4 | x by definition.
Example 3.2.4. Given that a, b and c are three positive integers, and that the integer x
is larger than 1 and is divisor of abc + 1, explain why x must be different than a, b, or c.
Solution. Let y = abc + 1. We are told that x | y. If x were one of a, b, or c, then x | abc.
Since y = abc + 1, it would now follow from statement 3 of Theorem 3.2.1 that x | 1. But
this cannot be, because x > 1.
Example 3.2.5. I am thinking of two different single digit numbers. Neither is divisible
by 8, but both their sum and difference are. What are the digits.
Solution. Let the numbers be x and y. We are told that x + y and x − y are divisible by
8. So when we add and subtract x + y and x − y, then the results (2x and 2y) must also
be divisible by 8. So x and y must be divisible by 4. Since x is divisible by 4, the only
possibilities for x are −8, −4, 0, 4, 8. Since x is not divisible by 8, this rules out −8, 0, and
8. So x is either 4, or −4, and since y is not the same as x, it follows that the two numbers
are 4 and −4.
3.2.1 Quotient and remainder

So far we have been investigating what happens when one number divides another. What
happens if a and b are positive integers and b does not divide a? Elementary students know
the answer: if you attempt to divide a by b, you get a nonzero remainder.
Recall the terminology about division: The number you are dividing by is called the divisor 1 ,
the number your are dividing into is called the dividend, the integer part of your answer is
called the quotient and what’s left over is called the remainder.
For our purposes, we can write this as:
dividend = quotient · divisor + remainder
For example, when we divide 895 by 46, we write 895 = 19 · 46 + 21.
Remainders
In Number Theory, the remainder is usually far more important than the quotient. However,
we have to be a little careful with the meaning of the word “remainder”. Given integers a
and d, with d > 0, there are infinitely many values of q and r for which a = q · d + r. For
example, here are several possible values of q and r that satisfy 26 = q · 7 + r:
q = 1 , r = 19 that is 26 = 1 · 7 + 19
q = 2 , r = 12 26 = 2 · 7 + 12
q = 3, r = 5 26 = 3 · 7 + 5
q = 4 , r = −2 26 = 4 · 7 − 2
q = 5 , r = −9 26 = 5 · 7 − 9
Although each of the above statements is true, only the the third one yields the correct
quotient and remainder when 26 is divided by 7.
1 A little unfortunate—in mathematics there are two different meanings for the word divisor. We will use
it primarily in the former sense as on page 25. The context will make it clear.
3.2. DIVISIBILITY 29
When an integer a is divided by a positive integer d, the remainder is the smallest

nonnegative number that satisfies a = q · d + r. In this case, the integer q is called the
quotient.
There is a theorem that tells us that r is always smaller than the divisor d.
Theorem 3.2.6 (The Division Algorithm). If a and d are integers and d > 0, then
there are unique integers q and r such that a = qd + r, with 0 ≤ r < d.
We have to be careful when the integer a is negative. For example, when 27 is divided by 4
the remainder is 3. When −27 is divided by 4 the remainder is 1, not −3. The reason for
the last statement is that the remainder has to be nonnegative.
Example 3.2.7. Find the quotient and remainder when −54 is divided by 7.
Solution. We are looking for r so that −54 = q · 7 + r. If we use a calculator, we get
−54/7 = −7.714. . . . A common error is to conclude that q = −7, but this would lead to
a negative remainder, which is not allowed—remember that a remainder is defined to be
nonnegative. The quotient in this case is actually −8. Here’s the comparison between the
two values for q:
−54 = (−7)7 − 5, (q = −7 and r = −5).

−54 = (−8)7 + 2, (q = −8 and r = +2).
The remainder is 2 and the quotient is −8.
3.2.2 Common divisors
Given integers a and b, any integer d that divides both a and b is called a common
divisor of a and b. The largest of all common divisors is called the greatest common
divisor of a and b, and is denoted gcd(a, b).
There are several ways to find the greatest common divisor of two integers. For now, we
will use the most obvious one, which is to simply list the divisors of both numbers and by
comparison find the greatest common one.
Example 3.2.8. To prepare a classroom display, Ms. Jesse wants to cut a piece of red
poster board into equal sized squares without any material left over. The poster board is
242 cm by 110 cm. What are the largest squares that she can cut?
Solution. If the squares were d cm along each side, then to avoid any waste, d would have
to divide 242 and 110. So what we are looking for is the largest number that divides both
242 and 110, that is, we want to find gcd(242, 111).
The divisors of 242 are: 1, 2, 11, 22, 121 242.

The divisors of 110 are: 1, 2, 5, 10, 11, 22, 55, 110.
The common divisors are 1, 2, 11, and 22, so gcd(242, 110) = 22. The largest squares that
can be cut from the poster board are 22 cm by 22 cm.
Question 3.2.9.
(a) What is gcd(0, 4)?
(b) What is gcd(21, −14)?
(c) What can you deduce about a and b if gcd(a, b) = b?
NEED a PROBLEM HERE
The next theorem tells us that we can always reach gcd(a, b) no matter what a and b are.
Theorem 3.2.10 (The Linear Divisibility Theorem). Given positive integers a and b,
the smallest positive value of ax + by is d where d is the greatest common divisor of a and
b.
The proof is in appendix A — It is not constructive, which means that it does not tells you
how find x and y. That is the subject of the chapter on Linear Diophantine Equations. At
this point, all we need to know is that there is a solution.
3.2.3 Two important consequences.

Apart from telling us that there must indeed be a solution to XXXXXX Euclid’s general
problem, Theorem 3.2.10 has two very important consequences.
In general, if d1 and d2 are common divisors of a and b, there is not much that we can
conclude about the relationship between d1 and d2 . However if one of them is the greatest
common divisor of a and b, then it must be a multiple of the other. As an illustration,
consider the numbers 60 and 72. Their greatest common divisor is 12, the other common
divisors are 1, 2, 3, 4, 6, and 12; and all of them divide 12.
The proof that this always happens follows very quickly from the Linear Divisibility Theo-
rem:
3.3. TESTS FOR DIVISIBILITY 31
Theorem 3.2.11 (The Common Divisor Theorem). If d is a common divisor of a and

b, then d | gcd(a, b).
Proof. By Theorem 3.2.10, there is some value of x and y such that ax + by = gcd(a, b). By
the basic properties of divisibility every divisor of a and b also divides ax + by.
For the second consequence we need the following concept:
Two positive integers a and b are said to be relatively prime if gcd(a, b) = 1.
Theorem 3.2.12 (The Relatively Prime Divisor Theorem). Suppose gcd(d, a) = 1

and that d | ab. Then d|b.
Proof. By Theorem 3.2.10, there are integers x and y such that dx + ay = 1. If we multiply
the equation by b we get dbx + aby = b. Now d | dx and d | aby, so by the basic properties of
divisibility, d must also divide b.
Example 3.2.13. Show that if 4 | c and 9 | c, then 36|c.

Solution. Since 4 | c, we have c = 4a for some integer a. This means that 9 | 4a, and since
gcd(4, 9) = 1 we can conclude that 9 | a. Then a = 9b for some integer b, so
c = 4a = 4(9b) = 36b,
showing that 36 | c.
3.3 Tests for divisibility

It is sometimes very handy to be able to determine quickly if certain small numbers are
divisors of larger integers. With the almost universal availability of electronic calculators,
one may wonder if we actually need any tests for divisibility—why not simply try it out on
the calculator.
Is 713459 divisible by 2, 5, or 10? I’ll bet that you did not use your calculator to answer
this. The reason you didn’t is that you know a test for divisibility by the numbers 2, 5, and
10.
Is 9172812 is divisible by 3? The answer is yes. Some people will find this out by using a
calculator, but many will not need one because they know that a number is divisible by 3 if
and only if the sum of its digits is divisible by 3. In this case, 9 + 1 + 7 + 2 + 8 + 1 + 2 = 30,
and since 30 is divisible by 3, so is 91712812.
Is 123456789012345 divisible by 7? Even with a calculator it looks like this is going to take
some work. There is a test for divisibility by 7 that will enable you to use your calculator
to answer this question fairly rapidly.
3.3.1 Tests for divisibility by 2 through 13

All of the divisibility tests have the feature that to settle the question “Is x divisible by d?”
the number x is replaced by a much smaller number.
Divisibility by 2, 5 and 10:

A positive integer is divisible by 2 iff its last digit is even.
A number is divisible by 5 iff it ends in a 5 or 0 (that is, iff its unit digit is divisible by 5).
A number is divisible by 10 iff it ends in a 0.
Divisibility by 2, 4, 8, etc:
An integer is divisible by 2 iff its last digit is divisible by 2.
An integer is divisible by 4 iff the number formed by its last two digits is divisible by 4.
An integer is divisible by 8 iff the number formed by its last three digits is divisible by 8.
Examples.
145764 is divisible by 4 because 64 is divisible by 4.
145794 is not divisible by 4 because 94 is not divisible by 4.
21824 is divisible by 8 because 824 is divisible by 8.
555668 is not divisible by 8 because 668 is not divisible by 8
Divisibility by 3 and 9:
An integer is divisible by 3 or by 9 iff the sum of its digits is divisible by 3 or by 9 respectively.
Example. Test 123456654321 for divisibility by 3.
Solution. 1 + 2 + 3 + 4 + 5 + 6 + 6 + 5 + 4 + 3 + 2 + 1 = 42, so the original number is divisible
by 3 iff 42 is divisible by 3. Now, 4 + 2 = 6 which is divisible by 3 so 42 is divisible by 3, so
123456654321 is divisible by 3.
Divisibility by 11:
An integer is divisible by 11 iff the alternating sum of its digits is divisible by 11.
Example. Test 123456 and 7719822 for divisibility by 11.
Solution. For 123456 the alternating sum is 1 − 2 + 3 − 4 + 5 − 6 = −3. Since −3 is not
divisible by 11, it follows that 123456 is not divisible by 11.
For 771982 we have 7 − 7 + 1 − 9 + 8 − 2 + 2 = 0. Since 0 is divisible by 11, it follows that

7719822 is divisible by 11.
Remark: Note that it doesn’t matter whether we start with a negative or a positive digit.
That is, to test 123456 we could use either 1 − 2 + 3 − 4 + 5 − 6 or −1 + 2 − 3 + 4 − 5 + 6,
because one sum is just the negative of the other.
Divisibility by 7, 11, and 13:

There are several tests for divisibility by 7, none of which is as “clean” as the above ones.
One of the easiest ones happens also to be a test for divisibility for 11 and 13. Here it is:
Partition the integer into groups of 3 beginning at the right (that is, where the commas
would appear). Alternately add and subtract these groups. The result is divisible by 7 (or
11, or 13) iff the original number is divisible by 7 (or 11, or 13).
Example. Test the number 12,345,678,982 for divisibility by 7, 11 and 13.

Solution. The groups of 3 are 12, 345, 678, 982. So we compute the alternating sum:
12 − 345 + 678 − 982 = −637. By using a calculator, we find that 637 is divisible by 7 and
13, but not by 11.
Example. Is the number 917,312,985,105,846 divisible by 7, 11, or 13?

Solution. We have 917 + 985 + 846 − (312 + 105) = 2331 and applying the test once more:
2 − 331 = −329, which is divisible by 7, but not by 11 or 13. So, the original number is
divisible by 7 but not by either 11 or 13.
Divisibility by 6 and 12: An integer is divisible by 6 iff it is divisible by 2 and 3.

An integer is divisible by 12 iff it is divisible by 4 and 3.
Proofs.
There are several special cases on which the proofs are based.
The first special case says that 2n always divides 10n , so 2|10, 4|100 8|1000, and so on. The
reason for this is clear: 10n = (2 · 5)n = 2n · 5n , so by definition, 2n | 10n .
Proof of the divisibility test for 5 and 10, and for 2, 4, 8, etc. In each of these cases,
the proof uses a similar idea. For example, to verify that the test for divisibility by 4 works,
observe that a number uvwxyz (where u, v, etc. are the digits of the number) is the same
as uvwx00 + yz. Now uvwx00 = (uvwx) · (100) which is divisible by 4. Hence, 4 | uvwxyz
if and only if 4 | yz.
Proof of the divisibility tests for 3 and 9. The proofs for 3 and 9 are the same. To
verify the test for 3, let us suppose that the number is wxyz. This is the number
1000w + 100x + 10y + z.
Rewrite this as
(999w + w) + (99x + x) + (9y + y) + z.
Rearrange it as follows:
(999w + 99x + 9y) + (w + x + y + z).
The number in the first set of parentheses is always divisible by 3. So the entire number is
divisible by 3 if and only if (w + x + y + z) is divisible by 3.
Proof of the divisibility tests for 6 and 12. The proofs of these follow from Theorem
3.2.13.
Proof of the divisibility tests for 11. There are certain numbers that are easily seen to
be divisible by 11:
The integers composed of an even number of 9’s are divisible by 11. This is easy to check:
99 = 11 · 9
99 99 = 11 · 909
99 99 99 = 11 · 90909
99 99 99 99 = 11 · 9090909, etc.
There is also another useful set of numbers that are divisible by 11, namely the integers
1 00 1, 1 00 00 1, 1 00 00 00 1, etc. These are the numbers that begin and end with the
digit 1 with an even number of zeros between the two 1’s
This is also easy to check:
1 00 1 = 990 + 11
1 00 00 1 = 99990 + 11
1 00 00 00 1 = 9999990 + 11
1 00 00 00 00 1 = 999999990 + 11, etc.
To check the test for 11, let us suppose that the number is uvwxyz. Write this as
100000u + 10000v + 1000w + 100x + 10y + z.
Rewrite this as
(100001u − u) + (9999v + v) + (1001w − w) + (99x + x) + (11y − y) + z.
and then rearrange it to get
(100001u + 9999v + 1001w + 99x + 11y) + (−u + v − w + x − y + z).
Now each of the numbers 100001, 9999, 1001, 99, and 11 is divisible by 11, so the number
(100001u + 9999v + 1001w + 99x + 11y) is divisible by 11. Consequently, the entire number
is divisible by 11 if, and only if (−u + v − w + x − y + z) is divisible by 11.
Proof of the divisibility tests for 7, 11, and 13. The proof for this resembles the proof
for the divisibility test for 11. Let’s consider the integer ab,cde,f gh,ijk, where the letters
are the digits of the integer. We want to show that this is divisible by 7, 11, or 13 if and
only if (−ab + cde − f gh + ijk) is divisible by 7, 11, or 13 respectively.
As we learned from the 1001 card trick, the integer 1001 is the product of 7, 11, and 13. We
begin by observing that the numbers 999,999, 1,000,000,001, and so on are all divisible
by 1001. The table explains why:
1,001 obviously
999,999 because 999,999 = 1,001,000 − 1,001
1,000,000,001 because 1,000,000,001 = 999,999,000 + 1,001
999,999,999,999 because 999,999,999,999 = 1,000,000,001,000 − 1,001
Except for the number 1,001, each number on the left is obtained by multiplying the one
above it by 1000 and adding or subtracting 1001. This means that the numbers in question
are all divisible by 1001.
Now let’s get back to the integer ab,cde,f gh,ijk. Write this as
ab,cde,f gh,ijk = 1,000,000,000ab + 1,000,000cde + 1000f gh + ijk.
Rewrite this as
(1,000,000,001ab − ab) + (999,999cde + cde) + (1, 001f gh − f gh) + ijk.
Rearrange to get
(1,000,000,001ab + 999,999cde + 1, 001f gh) + (−ab + cde − f gh + ijk).
The integer (1,000,000,001ab+999,999cde+1, 001f gh) is divisible by 1001, and so is divisible

by 7, 11, and 13. Thus the whole quantity is divisible by 7, or 11, or 13 if and only if
(−ab + cde − f gh + ijk) is also divisible by 7, or 11, or 13.

3.1.1 integer divisors integer divisors
8 1, 2, 4, 8. 13 1, 13.
9 1, 3, 9. 14 1, 2, 7, 14.
10 1, 2, 5, 10. 15 1, 3, 5, 15.
11 1, 11. 16 1, 2, 4, 8, 16.
12 1, 2, 3, 4, 6, 12. 17 1, 17.
The integer 12 has six divisors.
3.1.2 The integers 1 and −1 are the only ones.
3.1.3 The number zero is a multiple of every positive integer, and it is the only integer with
that property. (In case you were wondering, infinity is not an integer.)
3.2.2 (a) x | 17 and 17 | 34, so x | 34 by statement 1 of Theorem 3.2.2.
(b) Since 161 = 7 · 23, so 7 | 161 and it follows from statement 2 that 7 | 161x.
(c) 4 | 4 and 4 | 12 so 4 | 4y and 4 | 12z by statement 2. Since x + 4y = 12z, statement
3 implies that 4 | x.
3.2.9 (a) 4, because 4 | 0 and 4 is the largest divisor of 4. (b) 7. (c) b | a.
3.5 Exercises
1. Which of the following statements are true?
(a) 3 | 6, (b) 1 | 5, (c) 6 | 3, (d) 2 | 0, (e)0 | 2.
2. Prove statements 1 and 2 of Theorem 3.2.1
3. Show that if a | b and c | d then ac | bd.
4. Show that if a divides both b and c, then a divides (b + c).
5. Is it true that if b and c both divide a then bc also divides a? Explain.
6. Classify each of the following as true or false, and if the statement is false, give an
example showing it is false or explain why it is false.
(a) If positive integer is divisible by a and by b, then it must be divisible by a · b.
(b) If a number is divisible by 8, then it is also divisible by 4.
3.5. EXERCISES 37
(c) If a 6 | b and a 6 | c, then a 6 | (b + c).
7. List all divisors of x and y, circle the common divisors, and find the gcd(x, y).
(a) x = 108, y = 144. (b) x = 132, y = 0. (c) x = 17, y = 38.
8. When asked to check whether 28 divides 14 · x, a student says yes it does and gives
the following reason: 28 = 2 · 14 and since both 2 and 14 divide 14 · x, then 28 must
also divide 14 · x. What is wrong with the reasoning?
9. Use the Linear Divisibility Theorem to show that if gcd(p, q) = d, then p/d and q/d
are relatively prime.
10. (a) When a certain positive integer is divided by 6, my calculator showed that the
part to the right of the decimal point was .666667. What is the actual remainder?
(b) When I divided a certain negative number by 7, my calculator gave the answer
as −xxxxx.28571429, where the x’s represent other digits (not necessarily all the
same). What is the actual remainder?
11. Use the divisibility test for 3 to determine what possible values of x would make
1234x51234 divisible by 3.
12. (From Boris Kordemsky’s The Moscow puzzles) Find the integer t and the digit a
which makes the following equation valid:
2
3(230 + t) = 492a04.
13. (a) Make up and prove a test for divisibility by 15.

(b) For what pairs of digits x and y is the number 411xy divisible by 15?
14. Which of the following numbers are divisible by 77? By 91?

(a) 3,400,927,788,104
(b) 999,876,543,209,544
(c) 40,454,565,676,707
15. Take any two digit number, say ab. Repeat the digits four times, producing the
number abababab. Divide this number by 137. Divide that result by 101. Divide that
result by your original number. What’s the answer? Explain.
39
4 Common multiples and divisors

4.1 Factors and primes
Inspector Prime. Detective Inspector Prime is a forensic acoustics specialist. He

has been asked to help with a garbled recording of a conversation between two
members of a gang. The gang has at least 100 members, and if the message is
properly deciphered, it will tell the authorities exactly how many members there
are. After several hours, Inspector Prime was able to obtain the following portion of
the conversation.
“Yeah, well yesterday we collected a total of $25393 from all the guys. Everybody
in the gang gave exactly the same amount, and the only coins we got were loonies
and twonies.”
This didn’t quite tell the cops what they wanted. Or did it? Help Inspector Prime.
How many gang members were there?
4.1.1 Factoring an integer

Sometimes we have to write an integer as a product of other integers all of which are greater
than 1.
Example 4.1.1. Write 252 as the product of three integers all greater than 1.
Answer. There are several possible answers, some of which are:

252 = 4 · 7 · 9 ,
252 = 3 · 6 · 18 ,
252 = 3 · 4 · 21 .
The usual way to find such an answer is to first factor 252 into the product of two integers
and then factor one of the two integers. For example,
252 = 4 · 63 and 63 = 7 · 9, so 252 = 4 · 7 · 9 .
Sometimes we have to continue the process, obtaining more than three factors:
252 = (4)(63) = (2 · 2)(7 · 9) = (2 · 2)(7 · 3 · 3) = 2 · 2 · 7 · 3 · 3 .
40 CHAPTER 4. COMMON MULTIPLES AND DIVISORS
We can go no farther. The numbers 2, 3, and 7 do not yield any more factors. Such numbers
are called prime numbers.
An integer p is called a prime number, or simply, a prime, if it is positive and if it has

exactly two different divisors, the divisors being 1 and the number itself.
An integer is called a composite number if it has more than two divisors.
The number 3 has two divisors: 3 and 1, so 3 is a prime. The number 4 has three divisors:
1, 2, and 4, so 4 is a composite number prime. What about the number 1? The definition
excludes the number 1 as being either a prime or composite number because the number 1
has only one divisor.
When we write a number as the product of its prime factors, the result is called the prime
factorization of the number. If you use two different methods to find the prime factorization,
the result will always be same, except for the order of the primes. For example, we could
have taken a different road to find the prime factorization of 252:
252 = (12)(21) = (2 · 2 · 3)(3 · 7) = 2 · 2 · 3 · 3 · 7.
Theorem 4.1.2 (The Fundamental Theorem of Arithmetic). Every positive integer

greater than 1 has a prime factorization. No matter how we find the prime factorization,
the result will always be the same, except for the order of the primes.
The usual practice is to arrange the factors in ascending order, raising any repeated primes
to the appropriate power:
252 = 22 · 32 · 7 .
The proof of the Fundamental Theorem is in Appendix A. Although the Fundamental

Theorem tells us that every integer greater than 1 has a prime factorization, neither the
theorem nor its proof tells us how to find the factors. For smaller integers, we can make use
of the divisibility tests to see whether the number has one of the primes 2, 3, 5, 7, 11, or 13
as one of its factors. It is also useful to have a table of primes available, and a table of the
first 30 primes is included below.
The first 30 prime numbers

2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
4.1. FACTORS AND PRIMES 41
Example 4.1.3. Find the prime factorization of the following numbers.

(a) 126 (b) 10000 (c) 1547.
Solution.
(a) The tests for divisibility show that 126 is divisible by 2 and 9, so we get
126 = (2)(9)(7) = 2 · 32 · 7.
(b) 10000 = 104 = (2 · 5)4 = 24 · 54 .

(c) A quick examination reveals that 1547 is not divisible by 2, 3, or 5. It is divisible by
7, so 1547 = 7 · 221. So now we ask is 221 divisible by 7, and a quick tests reveals that
it is not. So now we try 11—does 11 divide 221? The answer is no. What about 13?
The answer is yes: 221 = 13 · 17 and since 17 is a prime, the complete factorization of
221 is 7 · 13 · 17.
Example 4.1.4. Find the prime factorization of the following numbers:

(a) 122 · 263 (b) 487.
Solution.
(a) Sometimes we’re lucky and half the job is done for us. We have
122 · 263 = (22 · 3)2 (2 · 13)3 = 24 · 32 · 23 · 133 = 27 · 32 · 133 .
(b) 487 is not divisible by 2, 3, 5, or 7. so we keep testing by dividing by successive primes

until we find a factor, or until it becomes obvious that the number does not√have
any smaller prime factors. We only have to test primes less than or equal to 487.
Dividing by 13, 17, and 19 we find no factors, and since 232 > 487 we conclude that
487 is a prime.
Part (b) of Example 4.1.4 illustrates the simplest test to see whether a positive√ integer n
is a prime: If n is not prime, it will have a prime
√ factor less than or equal to n. So try
divding n by the primes less than or equal to n. Although the test is simple, it loses it
appeal when n is a very large number.
4.1.2 The sieve of Eratosthenes

The first 30 prime numbers are listed in the table on page 40. How can we obtain more?
There is no known mathematical “formula” that generates only prime numbers, but we can
obtain as many as we like by using a process that has been around since the time of the
ancient Greeks.
Suppose we want to find all the primes up to 200. Make a list of all the integers from 1 to
200. The sieve of Eratosthenes is a method that filters out all the non-prime numbers and
leaves only the primes.
1. Cross out number 1, because it is not a prime.
2. Circle the smallest number that has not been crossed-out and then cross out all other
multiples of that number. In this case, the circled number is 2 and all other multiples
2 are crossed-out. The crossed out numbers cannot be primes.
3. Circle the smallest number that is not crossed out. (It is a 3.) Now cross out all other
multiples of that number. The newly crossed out numbers cannot be primes.
4. Circle the smallest remaining number that is not crossed out. Then cross out all other
multiples of that number. The newly crossed out numbers will not be prime.
Keep doing this until all numbers are either circled or crossed out. The circled numbers
are the primes, the crossed-out numbers are the composite numbers (except for the
number 1).
You will best understand this if you actually carry it out. The first part of your list should
look like this, where the numbers are boxed rather than circled:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
If you actually carried out this procedure on the numbers from 1 to 200 you will have noticed
that after you circled the prime number 13, you did not cross out any new numbers. The
reason for this is that the first multiple of any prime p that is not already crossed out (other
than p itself) is p2 . We explain this using the prime number 7:
The multiples of 7 that are less than 72 are:
2 · 7, 3 · 7, 4 · 7, 5 · 7, 6· 7.
But, these have already been crossed out for the following reasons:
2 · 7, because all multiples of 2 have been crossed out;
4 · 7, because all multiples of 4 are multiples of 2 and have been crossed out;
6 · 7, because all multiples of 6 are multiples of 2 and have been crossed out.
In general, by the time you are ready to circle prime p, the multiples 2p, 3p, 4p, . . . , (p−1)p
have already been crossed out.
4.2. FINDING THE GCD 43
4.1.3 The infinitude of primes

If we carry on with the Sieve of Eratosthenes for the infinite list of integers do we ever reach
a point beyond which all remaining integers are crossed out? In other words do we ever run
out of prime numbers? The answer is no. A proof was given by Euclid in about 300 BCE.
Theorem 4.1.5. There are infinitely many prime numbers.
Proof. Let p be any prime number. We will show that there is a prime larger than p, which
means that there is no largest prime. Take the product of all the primes up to p and add 1,
to form the number
n = 2 · 3 · 5 · 7 · · · p + 1. (4.1)
Then, n cannot be divisible by any prime q less than or equal to p. Suppose, for a contradic-
tion, that this were the case. Then since q is one of the primes 2, . . . , p, it would follow that
in equation (4.1), q divides both n and the product 2 · 3 · 5 · 7 · · · p. By the basic properties
of divisibilty q would have to divide 1, which is clearly impossible.
Since n is not divisible by any of the primes from 2 to p, it follows that n is either a prime
or else is a composite number with prime factors that are larger than p. In either case, we
have shown that there is a prime larger than p.
4.2 Finding the gcd

The notion of the greatest common divisor was introduced in section 3.2.2, where we found
the greatest common divisor by listing all of the divisors of both integers. There are two
other methods that are more commonly used: the prime factorization method, and the
Euclidean Algorithm.
4.2.1 The prime factorization method for finding the gcd

In this method we first complete the prime factorization of each and then pick up the gcd
by examining the factorizations.
Example 4.2.1. Find gcd(242, 110).

Solution. The prime factorizations of the two integers are:
242 = 2 · 112
110 = 2 · 5 · 11
The greatest common divisor is the product of the lowest power of the prime factors that
appear in both factorizations. In this case, the primes 2 and 11 are the only ones that
appear in both. The lowest power of 2 that occurs in both is 21 . The lowest power of 11 is
111 . So gcd(242, 110) = 2 · 11 = 22.
Here is why this method works: If d is any divisor of both 242 and 110, then any prime
factor p of d must also be a prime factor of both 242 and 110. So p must be either 2 or 11.
This means that the prime factorization of d only contains 2’s and 11’s, so must be of the
form 2x · 11y .
Since 2x divides both 2 · 112 and 2 · 5 · 11, then the maximum value of x is 1. Similarly, the
maximum value of y is 1, so the gcd is 21 · 111 .
Here is another example using the prime factorization method, with the solution expressed
in a slightly more systematic way.
Example 4.2.2. Use the prime factorization method to find gcd(a, b) if
a = 23 · 72 · 133 · 232 and

2 3 4
b = 3 · 7 · 13 · 23 ,
Solution. The primes involved are: 2, 3, 7, 13, and 23. So the greatest common divisor will
be an integer of the form
2a · 3b · 7c · 13d · 23e .
where a, b, c. etc., are the smallest of the powers in each number.
The value of a is the smaller of 3 and 0, so 2a = 20 .
The value of b is the smaller of 0 and 2, so 3b = 30 .
The value of c is the smaller of 2 and 3, so 7c = 72 .
The value of d is the smaller of 3 and 4, so 13d = 133 .
The value of e is the smaller of 2 and 1, so 23e = 231 .
Consequently, gcd(a, b) = 20 · 30 · 72 · 133 · 231 .
Since 20 and 30 are both 1, and since 231 = 23,we write this as gcd(a, b) = 72 · 133 · 23.
Warning: To use the prime factorization method, the numbers must be factored into
powers of primes. For example, 122 · 132 has not been factored into primes, because 12 is
not a prime number.
4.3 The Euclidean Algorithm

The prime factorization method is quick and useful for finding the greatest common divisor of
integers with a few small prime factors. It is not so good when there are many prime factors,
or when the prime factors are large. With the prime factorization method a systematic
approach often means that you might have to test for the prime factors 2, 3, 5, 7, 11, . . . .
There is no known method for quickly factoring large numbers, and it is one of the out-
standing problems in mathematics. There is, however, a fool-proof way to find the greatest
common divisor of two integers, and it has been known for thousands of years. It is called
the Euclidean Algorithm, and it uses the familiar fact that if a + b = c and if d divides any
two of a, b, and c, then d must also divide the third one. (For example, if x + 33 = 48y,
since 3 divides both 33 and 48y then 3 must also divide x.) A useful consequence is:
4.3. THE EUCLIDEAN ALGORITHM 45
Lemma 4.3.1 (The Euclidean Lemma). If a, b, q and r are positive integers with
a = bq + r , (4.2)
then gcd(a, b) = gcd(b, r).
It may be easier to comprehend when actual numbers are used: Consider the following
equation:
78 = 30 · 2 + 18.
The Euclidean lemma tells us that gcd(78, 30) = gcd(30, 18).
Proof of the Euclidean Lemma. Suppose that d divides a and b. Then d divides both a
and bq in equation (4.2). Then d must also divide r. On the other hand, if d divides b
and r, then in equation (4.2) d divides bq and r, and so divides a. It now follows that
gcd(a, b) = gcd(b, r).
Suppose we want to find gcd(272, 56). Dividing 272 by 56 we get

272 = 56 · 4 + 48.
The Euclidean Lemma tells us that gcd(272, 56) = gcd(56, 48). This allows us to replace
the problem of finding gcd(272, 56) with the easier problem of finding gcd(56, 48).
We can continue farther. Dividing 56 by 48, we get
56 = 48 + 8.
The Euclidean Lemma now tells us that gcd(56, 48) = gcd(48, 8). We recognize that
gcd(48, 8) = 6, so putting everything together, we have:
gcd(272, 56) = gcd(56, 48) = gcd(48, 8) = 6,
and we have found the greatest common divisor of 272 and 56.
That’s it — that’s the Euclidean Algorithm!
Note: Instead of writing the division result in the form a = bq + r, some prefer to write
a − bq = r. This has a few advantages later on, and this is what is done in the next example.
Example 4.3.2. Find gcd(468, 168) using the Euclidean Algorithm.

Solution.
468 − 2 · 168 = 132 so gcd(468, 168) = gcd(168, 32).
168 − 132 = 36 so gcd(168, 132) = gcd(132, 36).
132 − 3 · 36 = 24 so gcd 132, 36) = gcd(36, 24).
36 − 24 = 12 so gcd(36, 24) = gcd(24, 12).
24 − 2 · 12 = 0 so gcd(24, 12) = 12.
So gcd(468, 168) = 12.

The next example shows that the Euclidean Algorithm works well for larger numbers.
Example 4.3.3. Find gcd(7956, 13500).
Solution.
13500 − 7956 = 5544

7956 − 5544 = 2412
5544 − 2 · 2412 = 720
2412 − 3 · 720 = 252
720 − 2 · 252 = 216
252 − 216 = 36
216 − 6 · 36 = 0.
So, gcd(7956, 13500) = 36.
4.4 Least common multiples
A problem of tarts. The bakery shop had prepared 16 dozen tarts, but before
they could be put on the display shelf, a few were sold. When the baker tried to
arrange them in rows of four, there were two left over. He tried placing them in rows
of five, but again there were two left over. Then he tried six and still there were two
left over. Finally, when he tried putting them in rows of seven, none were left over.
How many tarts were sold?
The solution to this depends upon the notion of common multiples. Common multiples live
in partnership with common divisors, and in fact common multiples are probably used more
frequently.
Given integer a and b, any integer that is a multiple of both a and b is called a common
multiple of a and b. The least common multiple which is defined to be the smallest
positive common multiple, is denoted by lcm(a, b).
Two positive integers have only a finite number of common divisors, but they have infinitely
many common multiples. One way to find the greatest common divisor is to examine all
4.4. LEAST COMMON MULTIPLES 47
divisors of both a and b. You cannot use exactly the same strategy to find the lcm(a, b).
However, since the least common multiple cannot be greater than ab, you only need to list
common multiples up to ab. A more reasonable approach is to proceed as follows: consider
the positive multiples of a one by one, and at each stage test whether the multiple is divisible
by b.
Example 4.4.1. Find lcm(144, 4812).

Solution. The multiples of 4812 are
1 · 4812 = 4812 (not divisible by 144)

2 · 4812 = 9624 (not divisible by 144)
3 · 4812 = 14436 (not divisible by 144)
4 · 4812 = 19248 (not divisible by 144)
5 · 4812 = 24060 (not divisible by 144)
6 · 4812 = 28872 (divisible by 144);
so lcm(144, 4812) = 28872.
Question 4.4.2. Is there a similar strategy to increase the efficiency of the list method for
finding the gcd?
Question 4.4.3.
(a) What can you say about a and b if lcm(a, b) = b?
(b) What is lcm(−21, 7)?
(c) Why can’t we specify what lcm(0, 4) is?
The prime factorization method

The lowest common multiple of 150 and 6860 is 102900, and 102900 = 15 · 6860. If you
use the list method, you will have to take 15 successive multiples of 6860 before you find
the least common multiple. The list method is even worse for 169 and 289, whose lowest
common multiple is 169 · 289. You would have to list 169 multiples of 289 before discovering
lcm(169, 289). A better option is to use the prime factorization method. The following
example shows how it is done.

Solution. First, obtain the prime factorizations of 6860 and 150.
6860 = 22 · 5 · 73
150 = 2 · 3 · 52 .
Then take the highest power of each prime that appears. In this case, the primes involved
are 2, 3, 5, and 7. The highest powers of each are: 22 , 3, 52 and 73 . The lowest common
multiple is the product of these:
lcm(6860, 150) = 22 · 3 · 52 · 73 = 102900,
The reason this works is as follows: The result, 22 · 3 · 52 · 73 , is a multiple of the two numbers
because it is divisible by every prime power of both integers. It is easy to understand why
there is no smaller common multiple: the prime factorization of any multiple cannot contain
a power of 2 that is less than 22 , and the same reasoning applies to all other prime factors.
Using the gcd to find the lcm

Returning to the previous example, let us identify the prime powers that we used to find
lcm(6860, 150):
6860 = 22 · 5 · 73
150 = 2 · 3 · 52 .
Note that if we use the factorization method to find the gcd, we take the lowest powers of
each prime. So in the above, we would select the unboxed prime powers. Together, the gcd
and lcm contain all of the factors of both 6860 and 150. This means that
lcm(6860, 150) · gcd(6860, 150) = 6860 · 150.
In general, if a and b are two positive integers, we always have the following relationship:
Theorem 4.4.5.
ab
lcm(a, b) · gcd(a, b) = ab, or, equivalently lcm(a, b) = .
gcd(a, b)
When using this method to find the lcm, you can find the gcd in any manner that you want.
92·172 92·172
Solution. We find gcd(92, 172) = 4, so lcm(92, 172) = gcd(92,172) = 4 = 3956 .
4.5. WHEN THERE ARE THREE OR MORE INTEGERS 49
4.5 When there are three or more integers

Example 4.5.1. A group of students visited a candy factory. The factory manager gave
them each an identical bag of jelly beans. The bags were made by distributing 260 yellow
beans, 195 red beans, and 234 black beans among the bags. What is the maximum number
of bags that could be made assuming that there were no beans left over, and how many
beans of each colour are in the bags?
If there were d bags, then d | 260, d | 195, and d | 234, so we are looking for gcd(260, 195, 234).
A little experimentation will lead you to the answer. The objective here is to find a system-
atic way of finding the greatest common divisor of three or more integers, and to understand
why it works.
Theorem 4.5.2. Let e = gcd(b, c). Then gcd(a, b, c) = gcd(a, e).
Proof. If the positive integer d divides e, then it divides b and c, and so if d divides a and
e it must be a common divisor of a, b, and c. On the other hand, if d is a common divisor
of a, b, and c, then by the Common Divisor Theorem it certainly divides e = gcd(b, c), and
so is a common divisor of a and e.
It follows that the greatest common divisor of a, b, and c is the same as the greatest common
divisor of a and e.
This tells us how to solve the candy factory question and others like it.
Solution to the candy factory problem. Recall that we are trying to find gcd(260, 195, 234).
Now, gcd(195, 234) = 39 (by whatever method you use). So, by the theorem,
gcd(260, 195, 234) = gcd(260, 39) = 13.
So it is possible to make 13 bags. In each bag there will be 20 (= 260/13) yellow beans,
15 (= 195/13) red beans, and 18 black beans.
Similar results hold for least common multiples, and we state them without proof.
Theorem 4.5.3.
1. Every common multiple of a and b is a multiple of lcm(a, b).
2. lcm(a, b, c) = lcm(a, lcm(a, b)).
Example 4.5.4.
1. Use Theorem 4.5.3 to find lcm(4, 5, 6, 9).
2. Use the prime factorization method to find lcm(4, 5, 6, 9).

Solution.
1. lcm(4, 5, 6, 9) = lcm(lcm(4, 5), lcm(6, 9)) = lcm(20, 18) = 180.
2. 4 = 22 , 5 = 5, 6 = 2 · 3, 9 = 32 , so lcm(4, 5, 6, 8) = 22 · 32 · 5 = 180.

4.4.2 Yes. Instead of listing the divisors of both a and b, only list those of, say, a. Then,
beginning with the largest divisor of a, and working your way backwards, find the
largest divisor of a that is also a divisor of b.
4.4.3 (a) b | a.
(b) 21.
(c) lcm(a, b) has to be positive by definition, but the only multiple of 0 is 0 which is
neither positive nor negative.
4.7 Exercises
1. Find the prime factorizations of the following numbers.
(a) 5040 (b) 299 (c) 33000
(d) 499 (e) 123123 (f) 8437
2. Use the sieve of Eratosthenes to find all the primes up to 200. (It serves somewhat as
a visual check if you put the integers in rows that contain a multiple of 6 elements.)
3. Alice is using the sieve of Eratosthenes to find all primes up to 500. She has eliminated
all multiples of 2, 3, 5, 7, 11, 13, 17, and 19. The next lowest number that has not
been eliminated is 23. Does she have to continue eliminating numbers, or has she
already found all of the primes below 500? Explain.
4. Gerry is trying to factor the number 704791. By testing all primes in succession, she
has found that the smallest prime that divides 704791 is 89. The square root of 704791
is approximately 839.5, so at first she thinks that she still has a way to go. Then she
realized that she didn’t need to go any farther, and she was correct. Why?
5. People sometimes argue that the number n provided by equation (4.1) must always
be a prime number. Show that this is not the case by finding a prime factor of
2 · 3 · 5 · 7 · 11 · 13 · 17 + 1.
6. (From Brain Bolt’s Mathematical Funfair ). A computer programmer worked the prod-
uct of her age in years, the age of her cat in years, and the number of her house. Given
that the product was 17654, how old was she?
7. Find the greatest common divisor of 564 and 180.
4.7. EXERCISES 51
8. Find the greatest common divisor of 60, 72, and 90.
9. Find all common divisors of 168 and 420.
10. There are three ways of finding the greatest common divisor of two positive integers,
namely, by
(a) listing the divisors of each number
(b) finding the prime factorization of both numbers,
(c) the Euclidean Algorithm.
Show how each of these can be used to find gcd(92, 36)
11. Find the gcd and lcm of (17)2 · (18)3 · (19)4 and (15)3 · (16)2 · (17)3 by using prime
factorizations.
12. (a) Use the Euclidean Algorithm to find gcd(3915, 825).

(b) Use the answer from the previous part to find lcm(3915, 825).
13. If a, b, x and y are integers such that ax + by = 6, can gcd(a, b) be equal to

(a) 1? (b) 3? (c) 5? (d) 6? (e) 12?
14. Jen claims that in order to find all common divisors of a and b, she just needs to find
all the divisors of gcd(a, b). Explain why she is correct.
15. We know that gcd(a, b) · lcm(a, b) = a · b. Is it also true that gcd(a, b, c) · lcm(a, b, c) =
a · b · c? Explain why or give a counter-example.
16. (a) Use the Euclidean Algorithm to find gcd(3915, 825).

(b) Use the answer from the previous part to find lcm(3915, 825).
17. The sailors from two navy vessels are to be combined to march in a military tattoo.
The smaller unit, which has 408 sailors, will be at the front. The larger, which has
578 sailors, will follow right behind. The two units must have the same number of
columns. What is the greatest number of columns that they can have?
18. (from Martin Gardner’s Aha! Insight. Originally from a Hindu arithmetic book of
the seventh century) A lady is carrying a basket of eggs. She drops the basket and
all the eggs break. When asked how many eggs she had, she says that she is poor in
arithmetic but remembers that when she counted the eggs by twos, threes, fours and
fives she had remainders of 1, 2, 3, and 4 respectively. What’s the smallest number of
eggs that she could have had in the basket?
19. Pat pressed a button that started two bells ringing. The first bell rings for 4 seconds
at the beginning of every 36 minutes and the second rings for four seconds at the
beginning of every 40 minutes. Pat pressed the button at midnight and both bells
rang together.
(a) When was the next time that both bells rang together?
(b) If this continues forever, what is the shortest possible time between the beginning
of two consecutive rings? Explain.
20. First, 40 pupils are separated into teams, with each team having the same number of
pupils. Later, 24 more pupils are distributed equally to the teams, with no one left
over. What is the greatest number of teams possible?
21. An elementary art teacher has 3 art classes with 21, 35, and 28 students, respectively.
The teacher wants to order some equipment that can be used by equal-sized groups
in each class. What is the largest number of students in a group in each class so that
each group has the same number of students?
22. Jane is planning a party at which she expects 16, 24, or 12 guests. Because she is
unsure of the number of guests but wants to have available an equal number of hors
d’oeuvres for each guest with none left over, how many should she order?
23. Before checking with the caterer, a cook cuts a cake into 35 equal pieces and an
identical cake into 42 equal pieces. The caterer, however, insists that the cakes be cut
exactly alike, that is, the caterer wants each piece to have the same volume. Into how
many pieces must each cake now be cut?
53
5 Fractions, decimals, and percentages

We learn about fractions, decimals, and percentages in elementary school, but evidently not
all that well. Many have difficulty switching between fractions, decimals, and percentages.
Some have learned methods for switching but do not understand why they work.
5.1 Fractions
The set of positive integers is closed under multiplication but not under division. The
inclusion of the positive fractions solves the problem. Despite this bit of serendipity, it is
not the reason fractions were introduced—as mentioned in Chapter 2 they were introduced
to enable people to measure things like weight and area. Fractions were not called numbers;
instead, they were magnitudes, and before the middle of the sixteenth century number and
magnitude were considered to be different. The word number invariably meant what we
mean now by “positive integer”. The rest of the (positive) numbers were called magnitudes.
The distinction was based on the anticipation of what each would be used for: numbers were
for discrete “indivisible” things, magnitudes were for measuring “continuous” quantities.
The word “fraction” is related to “fracture”, meaning to break apart, and that is close to
original meaning of “fraction”. Colloquially, here is what a fraction is:
Suppose p and q are positive integers. To get the fraction p/q, take an object
and divide it into q equal parts, and then take p of those parts.
The notation p/q can cause confusion when fractions are first introduced. Just as the
negative sign has different meanings, so does the division line. Before, the division symbol
represented a binary operation: 8/6 meant divide 8 by 6. Now the division symbol seems
to mean something different.
The notation makes sense as soon as you consider concrete examples. If you divide a cake
into 5 equal pieces, the combined measure of two of those pieces is denoted 2/5. The
combined measure of ten pieces is denoted 10/5, and 10 pieces is the same as 2 cakes. The
fraction 8/5 the same as 1 cake plus 3 additional pieces. That is also what you get when
you divide 8 by 5, so it really does make sense to use the division line when representing
fractions.
Today we use the words “rational number” instead of “fraction”, and the rational numbers
include negative fractions as well as the positive ones. Here is the formal definition.
A rational number is one that can be expressed in the fractional form p/q where p and
q are integers and q is nonzero. Then integer p is called the numerator and q is called
the denominator.
The word “rational” is to remind us that a rational number is the “ratio” of two integers.
Although it is possible to develop the properties of rational numbers directly from the
54 CHAPTER 5. FRACTIONS, DECIMALS, AND PERCENTAGES
definition, it is better to stick closer to the historical perspective. The definition of rational
numbers occurred many years after they had been in use. It is a goal to be achieved, not a
starting point.
5.1.1 Operating with the rationals

Equality
Interpreting rationals as numbers that are used to measure things also makes it easier to
give a concrete meaning to the arithmetic operations on rational numbers. But first, you
need to know about equality of rationals. A quick picture should convince you that if you
divide a pie into 4 equal pieces and take 3 of them you get the same amount as if you divide
it into 8 equal pieces and take 6 of them. In other words, 3/4 and 6/8 should be considered
as being the same rational number even ’though they are written differently. Also, as far
as division goes, it is doesn’t matter whether we divide 10 by 2 or 20 by 4, or 30 by 6—the
answer is always 5. So the rational numbers 10/2, 20/4, and 30/6 should all be the same.
Equality of rational numbersIf b is nonzero then

a c
= if and only if a = c.
b b
a ka
= for every nonzero integer k.
b kb
0
= 0.
b
The second statement provides the basis for several properties of rational numbers. For
example, it implies that
a c
= if and only if ad = bc.
b d
To see why, we note that
a ad c bc
= and = ,
b bd d bd
and therefore the two rationals are equal if and only if ad = bc.
−a a
Another consequence is that = . This can be checked by noting that
b −b
−a −1 · (−a) a
= = .
b −1 · b −b
−a a
It will also turn out that = − but before we can justify that statement we need to
b b
know more about the arithmetic operations on rationals
5.1. FRACTIONS 55
Multiplication
This is the easiest of the operations to learn. If you have, say, 4/7 of a cake, and you take
2/3 of it, then how much cake do you have? To do this pictorially, divide the 4/7 into three
equal pieces and take two of them. Each of the 1/7 pieces is divided into three equal parts,
and each of these parts is then 1/21 of the cake. Here’s what we get:
4/7
(2/3) of (4/7) = 8/21 = (2.4)/(3.7)
So, once we understand that “of” means multiply, we have:
Multiplication of rational numbers

a c ac
· = .
b d bd
Question 5.1.1.
(a) Is the set of rationals closed under multiplication?
(b) Is multiplication of rationals commutative?
(c) Is multiplication of rationals associative?
(d) With the above definitions, what is the multiplicative identity?
(e) What is the multiplicative inverse of p/q?
Division
Dividing by a number is the same as multiplying by the inverse of that number.
Division of rational numbers

c a c a d
If 6= 0, then = × .
d b d b c
To explain division of rationals, use the fact that division is the operation that undies
multiplication. So when trying to divide 3/4 by 2/5 we ask what do we have to multiply
a
2/5 by in order to get 3/4 ? If we let be the rational number we are looking for, we would
b
have
a 2 3
· = .
b 5 4
5
We can solve this by multiplying both sides of the equation by , and we get
2

a 2 5 3 5
· = ·
b 5 2 4 2

a 2 5 3 5
· = ·
b 5 2 4 2
a 3 5
= · .
b 4 2
Addition, subtraction, and comparison of rationals

Adding and subtracting rational numbers is more complicated than multiplying and dividing
them. When two rationals have the same denominator a concrete model leads quickly to the
fact that a/c + b/c = (a + b)/c. When the denominators are different, the notion of equality
lets us substitute equivalent rationals with a common denominator. So when adding a/b
and c/d we replace a/b with ad/bd and replace c/d with bc/bd. The results are summarized
as follows:
Addition and subtraction of rational numbers

a b a+b a b a−b
+ = , − = .
c c c c c c
a c ad + bc a c ad − bc
+ = − = .
b d bd b d bd
−a a a
The first statement implies what we said earlier, namely that = − . The notation −
b b b
a −a a
denotes the additive inverse of , so all we have to do is check that + = 0, and this
b b b
follows from the first statement above.
We use the idea in the second statement when comparing rational numbers, that is, we bring
things to a common denominator.
5.2. DECIMALS 57
Example 5.1.2. Compare the rational numbers 7/17 and 15/37.

Solution. Bring the fractions to a common denominator and compare the numerators.
7 7 × 37 15 17 × 15
= , and = .
17 17 × 37 37 17 × 37
Since 7 × 37 = 259 and 15 × 17 = 255, we see that 15 × 17 < 7 × 37, we conclude that
17/37 < 7/15.
We can generalize the previous example:
Comparison of positive rational numbers

a c
< if and only if ad < bc.
b d
Note that the preceding comparison test may fail if the rationals are not positive: For
a 5 c −6 a c
example if = and = , then ad = 35 and bc = 42, but > .
b −7 d 7 b d
5 −6
Question 5.1.3. Explain why >
−7 7
5.2 Decimals
Decimal numbers were introduced by Simon Stevin towards the end of the sixteenth century.
The current notation, where a period is used to separate the integer and fractional parts,
was devised by John Napier at the beginning of the seventeenth century. The notation was
rapidly adopted, and it provides a clear picture of the relative sizes of numbers.
Finite decimal expansions

If a decimal number only has a finite number of digits after the decimal point, it represents
the rational number p/q where p is the integer that you get when you remove the decimal
point, and q is a 1 followed by as many 0’s as there are decimal places. For example,
461789
46.1789 = .
10000
Napier would have described this by saying that
1789
46.1789 = 46 .
1000
Actually, its a little bit more complicated than that. The number a.d1 d2 d3 d4 d5 . . ., where
a is an integer and the di ’s are digits, is defined to be
d1 d2 d3 d4 d5
a+ + + + 4 + 5 + ··· .
10 100 1000 10 10
So, using the previous example,
1 7 8 9
46.1789 = 46 + + + + .
10 100 1000 10000
However, by bringing everything to the common denominator 10000 we end up with what
we had before
460000 1000 700 80 9 461789

46.1789 = + + + + = .
10000 10000 10000 10000 10000 10000
The advantage of the more complicated expression is that it enables us to define what we
mean by an number with an infinite number of digits after the decimal point.
Infinite decimal expansions

When first learning about decimals, a common question is “As you add more and more
decimal digits to a number, doesn’t the number get bigger and bigger?” The answer is “Yes
it does, but you can’t make the number get really big.”
Suppose we have the number 0.129847346d1d2 d3 d4 d5 . . . , where the dn ’s are digits that
we are going to add. The question is, “By adding those digits, how much larger than
0.129847346 can we make the number?” The answer is “Not very much.”
It is certainly true that
0.129847346d1d2 d3 d4 d5 . . . > 0.129847346.
But it is also true that when we replace the 6 by a 7 no matter what we substitute for the
dn ’s
0.129847347 > 0.129847346d1d2 d3 d4 d5 . . . .
So, no matter what we use for the dn ’s, the number is somewhere between 0.129847346 and
0.129847347. To put it another way, adding those extra digits will not increase the number
by more than 0.000000001.
Suppose we had an infinite decimal number. Using the same reasoning, if we approximate
it by truncating it after its first 10 decimals, then the rest of the decimals can’t increase
the approximation by more than 1/1010. If we use the first 100 decimals, then the rest of
the decimals can’t increase the approximation by more than 1/10100. And so on. Adding
more and more decimals just makes the approximation more and more accurate. So it is
reasonable to believe that an infinite decimal actually does represent a number. We no
longer try to prove this, but now accept it as an axiom.
By using the fact that you get better and better approximations as you take more and
more decimal places, you can effectively deal with infinite decimals. For example to find
12 × 0.412412412 . . . where the block of digits repeats forever, you get better and better
5.2. DECIMALS 59
approximations by computing
12 × 0.412 = 4.944
12 × 0.412412 = 4.948944
12 × 0.412412412 = 4.948948944
and it is pretty clear that the answer is 4.948948948 . . ., where the 948 block repeats forever.
If an infinite decimal has a repeating block of digits, indicate the repeating block by putting
a bar over it: 0.412 and 4.948. So the approximations that we carried out show that
12 × 0.412 = 4.948.
Note: The example above used an infinite decimal with a repeating block of digits. It is
not the case that all infinite decimals have a repeating block like this—we will see in the
next two sections that any decimal that ends in a block of digits that endlessly repeats must
actually be a rational number.
Question 5.2.1.
(a) How many decimal places should you keep if you want an infinite decimal number
to be approximate to within 0.00001? (Consider the number as being truncated, not
rounded.)
(b) If two numbers with infinite decimal expansions are truncated after the third decimal
place, what can you tell about the accuracy of the decimal digits when the two numbers
are multiplied? (Try some examples!)
The next example is related to a “debate” that appears with astonishing regularity. The
debate is about whether there is any difference between the number 1 and the number
0.99999 . . . , where the 9’s repeat forever. Once you accept the axiom that every infinite
decimal expansion represents a number, there is really no debate.
Example 5.2.2. Show that 0.9 = 1.0.

Solution. It is clear that 0.9 is not larger than 1.0, so let’s compute the 1.0 − 0.9. We will
use the approximations 1.0 − 0.9, 1.0 − 0.99, 1.0 − 0.999, and so on.
1.0 − 0.9 = 0.1
1.0 − 0.99 = 0.01
1.0 − 0.999 = 0.001
..
.
1.0 − 0.9999999999 = 0.0000000001 (There are ten 9’s here)
At this point where we have taken an approximation that uses ten 9’s, we see that the dif-
ference between 1 and the approximation is 1/1010. This means that the difference between
1 and 0.9 is also less than 1/1010. If we used one thousand nines in the approximation,
the difference would be 1/101000 . If we used a google 9’s, the difference would be 1/10google
and that’s quite a small number1 . The point is, that if we agree that 0.9 is a number, then
it differs from the number 1.0 by some nonnegative number that is less than any positive
number we can think of. But the only such number is the number 0. So the difference
between 1.0 and 0.9 is 0, and the two numbers must be the same.
5.2.1 Converting between fractions and decimals

Turning a rational into a decimal
Everyone knows how to do this—you simply carry out long division. The calculations for
43/25 and 19/44 are shown
.4318
1.72 (b) 44 19.00000
(a) 25 43.00 17 6
25
14 0
18 0 13 2
17 5
80 (∗)
50 44
50
360
0 352
8 (∗∗)
You can verify that 43/25 = 1.72 by multiplying both sides of the equation by 25. In
example (b), the remainder of 8 appears in line (∗) and then reappears in line (∗∗). Once
a remainder reappears, the digits start repeating. So 19/44 = 0.4318. You can verify that
19/44 = 0.4318 by multiplying both sides of the equation by 44. However, you have to use
approximations:
44 × 0.4318 = 18.9992, 44 × 0.431818 = 18.999992, 44 × 0.43181818 = 18.99999992 .
As we take more and more of the repeated blocks, the difference between the product and
19 becomes numerically smaller than any number we can think of, so we can say that
44 × 0.4318 = 19.
Example 5.2.3. When you divide another integer by 44, how many different remainders
can appear?
Solution. The possible remainders are 0, 1, 2, . . ., 43. So there are only 44 possible remain-
ders.
1A google is the number 1 followed by one hundred zeroes.
5.2. DECIMALS 61
If divide another integer by 44, and if the long division process does not terminate, then
at each step in the division the remainder must be 1, or 2, or, . . ., or 43. So after at most
43 steps we are guaranteed to encounter a remainder that has already appeared, and then
we obtain a repeating decimal. This same reasoning works no matter what integer we are
dividing by.
Theorem 5.2.4. Every rational number can be expressed in decimal form, and the decimal
form either terminates or ends in a repeating sequence of digits.
The repeating cycle in the number .4318 consists of two digits, so we say that the cycle has
period 2. The argument that we gave above shows that when the rational p/q is expressed
in decimal form, the length of the repeating cycle is at most q − 1. There is no formula for
predicting exactly what the length will be—for example the repeating cycle in the decimal
expansion for 1/44 has period 2, while the repeating cycle for 1/7 has period 6.
Turning a decimal number into a rational number

We now turn our attention to showing that the converse of Theorem 5.2.4 is true, namely
that every number whose decimal expansion is either finite or eventually repeating must be
the decimal representation of a rational number. A few examples, although not a rigorous
proof, will show why this is true.
Example 5.2.5. Express 31.70532 a rational in fractional form.
Solution. There is no mystery to this, for we encountered it when we introduced the decimal
notation on page 57.
3170532
31.70532 =
10000
Example 5.2.6. Express 31.719 as a rational in fractional form.
Solution. Let x = 31.719. Then multiplying x by 10 and by 1000 we get
1000x = 31719.19
10x = 317.19
And subtracting one from the other we get
990x = 31402,
31402
x= .
990
In both of the above examples, it is customary, although not necessary, to reduce the fraction
to a form p/q so that p and q have no common divisor. So 3170532 10000 would be reduced to
792633 31402 15701
2500 , and 990 to 495 . Since the denominators are typically of the form 100 . . . 0 or
99 . . . 900 . . . 0 they are not too difficult to factor, and the reduction is usually fairly simple.
The two examples demonstrate how to turn a decimal that terminates or repeats into a
fraction. Combining this with Theorem 5.2.4 we can describe what numbers are rational by
their decimal expansions.
Theorem 5.2.7. A number is rational if and only if its decimal expansion either terminates
or ends with a repeating cycle of digits.
Irrational numbers
Theorem 5.2.7 makes it easy to produce a whole slew of irrational numbers—just make up
an infinite decimal number which does not end in a repeating cycle. Here are two examples:
0.101001000100001000001000000100000001 . . .
0.12345678910111213141516171819202122 . . .
The fact that the rationals are closed under addition and multiplication is frequently useful
when trying to decide whether a given number is rational or irrational.
Example 5.2.8. Given that π is irrational, explain why π/2 is also irrational.
Solution. Let x = π/2. Then π = 2x. If x were rational, then π would also have to be
rational since it is the product of two rational numbers.
The product of a nonzero rational and an irrational is always an irrational number.
Example 5.2.9. The number e is perhaps even more ubiquitous than π. The decimal
expansion of e begins with 2.71828182845904523 . . ., and, like π, the number e is also known
to be irrational. Use this fact to show that (e + 2)1/3 is also irrational.
Solution. Let x = (e + 2)1/3 . Then x3 = e + 2. If x were rational, then x3 would also be
rational, and so e + 2 would be rational. Then (e + 2) − 2 would also be rational. But this
is not the case, so we have to conclude that x is irrational.
Sometimes the Fundamental Theorem of Arithmetic is used to show that a number is irra-
tional.
5.3. PERCENTAGES 63
√
Example 5.2.10. Show that 3 is irrational.
√
Proof. The proof is by contradiction. Suppose that 3 were rational. We will show that
this assumption leads to a logical contradiction, and so the assumption must be incorrect.
√ √
Assuming that 3 is rational, then 3 = p/q for some integers p and q where q 6= 0 and
where p and q have no common factor. Squaring both sides of the equation and rearranging
it we get p2 = 3q 2 , which means that p2 is divisible by 3. Since 3 | p2 it follows that 3 | p
(Theorem 3.2.12), so p = 3m, and p2 = 32 m2 = 3q 2 .
This means that 3 | q 2 and so 3 | q.
Consequently, we have shown that p and q both have 3 as one of their prime factors.√But
this contradicts the fact that they have no common factor. So we must conclude that 3 is
not rational.
5.3 Percentages
The word “cent” is French for 100, and it forms parts of some English words like “percent”,
“century”, and “centennial” So “percent” means “per hundred” or “out of a hundred”.
When we say that 15% of the needles from the Spindle and Spool company are defective,
we mean that on the average, 15 out of every 100 needles are defective.
California style. In 1990, a group of California education authorities issued the

following claim: “Although in the seventies test scores were down by nearly sixty
percent, they have since rebounded by over seventy percent!” Is this good news or
what?
—from A.K.Dewdney’s 200% of Nothing
People have enormous difficulties with percentages. Most of us understand how to turn a
decimal number into a percentage: just multiply by 100. So the numbers 0.342 and 34.2%
are exactly the same as are 4.2 and 420%. And to turn a percentage into a decimal fraction
we just reverse the process and divide by 100. So what’s the problem? The problem is that
a percentage conceals the base population.
This is very handy when you are comparing the results for collections of different sizes as
in Example 5.3.1 below. On the other hand, the hidden base can cause percentages to be
misleading as in the California style example.
Example 5.3.1. Out of 1872 cars from the Red Onion plant we found that 712 had defective
tires, and that 871 out of 2541 cars from the Green Frog factory had defective tires. A new
factory—the Blue Water company—started up and 529 out of 1263 Blue Water cars had
defective tires. Which plant had the better record?
Solution. In this case the base populations are 1872, 2541, and 1263 which makes it awkward
to compare in fractional form. However, converting to decimal fractions or percentages
provides a quick comparison:
712
= 0.380 = 38.0%
1872
871
= 0.343 = 34.3%
2541
529
= 0.419 = 41.9%
1263
So the Green Frog factory is slightly better than the other two.
Percentages may be very deceptive when the base populations shift. This is what happened
in “California Style”. A similar effect happens when you have to combine discounts and
surcharges.
Example 5.3.2. The Whitestar Superlimo dealer normally charges $1580.00 for a new
heater for their limousines. Whitestar also charges an additional 40% of the cost of the item
for installation. There was a sale and the heaters were reduced by 40%. Since the forty
percents cancel each other, I ended up buying my heater and had it installed for a total of
$1580.00. This was a good deal—I saved the installation fee of $632.00. Any comments?
Solution. This is a case where the base shifts in a sneaky way. The reduction in price is
based on a cost of $1580.00, but the installation is based on the purchase price, which,
because of the discount is considerably less than $1580.00. Here is the actual computation:
Purchase price: 1580.00 − 1580.00 × 40% = 948.00
Installation: 948.00 × 40% = 379.20
Total cost: 948.00 + 379.20 = 1327.20
So in fact, I paid $252.80 too much!
It is easy to make mistakes or to deliberately abuse percentages. There are no “rules of

thumb” for dealing with percentages. Sometimes you have to add them, sometimes you
have to multiply them, sometimes you have to average them — it all depends upon the
situation. You can avoid the pitfalls if you understand what percentage means, but you still
have to be very careful. When in doubt, use sample numbers for the base population.
5.4. ANSWERS TO THE QUESTIONS 65
Example 5.3.3. On the markdown table at the Bay department store, items are displayed
under a sign that says “40% off.” A weekend sale advertises “Receive an additional 25%
off on all already reduced merchandize.” This sometimes confuses customers. What total
discount will you receive if you purchase an item from the markdown table.
Solution. Many customers add the discounts and expect a total reduction of 65%, but this
is not what they will receive. How much should you expect to pay for an item from the
markdown table whose original price was $100.00? The markdown price will be $60.00 and
you will have that price reduced by a further 25%, that is by $15.00. So you will pay $45.00
and the total reduction is $55.00. Your total discount is therefore 55%, not 65%.
Another problem occurs when we talk about percentage increases or decreases. Again, using
a sample base population may help spot the error.
Example 5.3.4. Last Sunday, after the visit by a well known evangelist, 17% of the resi-
dents of the town attended church as compared to the usual 8%. The represents an increase
of over 200%. This seems right—17/8 is more than 200%. Comment.
Solution. Suppose the population of the town were 1000. Then 80 normally attend church.
Last Sunday 170 attended. That’s an increase of 90 people. The base is 80, so the increase
is 90/80 or 112.5%. That’a a big increase, but it’s not more than 200%.
This sort of error, where the word “increase” is used instead of “difference” may not appear
to be very serious. But consider a a small business whose sales were $80000.00 in July and
$96000.00 in August. If the head of sales reports an “increase of 120%”, the business owner
might believe that sales in August were $96000.00 more than July’s. This could lead to a
bad business decision.
5.4 Answers to the Questions

5.1.1 (a) Yes. (b) Yes. (c) Yes. (d) 1. (e) q/p.
5.2.1 (a) Truncate it after the fifth decimal place.

(b) The accuracy of the approximation of the products depends upon the size of the
original numbers. For example, consider the numbers 1/3 and 2/3. Truncating
the decimal expansions after 3 decimal places gives the following approximation
for (1/3)(2/3):
0.333 × 0.666 = 0.221778,
and the first two decimal places are accurate (2/9 = 0.2). Truncating the decimal
expansions for 100/3 and 200/3 after three places gives
33.333 × 66.666 = 2222.177778,
and none of the decimal digits are correct (20000/9 = 2222.2).

5.1.3 Bring both to a common denominator:
5 5·7 35 −35
= = = .
−6 −6 · 7 −42 42
−6 −6 · (−6) 36 −36
= = = .
7 −6 · 7 −42 42
−35 −36
Since −35 > −36, we have > .
42 42
5.5 Exercises
1. Assume that distributive law for integers holds, show that the distributive law also
holds for rational numbers with addition and multiplication as defined above. That
is, show that
p a c p a p c
+ = · + ·
q b d q b q d
2. Express each of the following as finite or repeating decimals.
(a) n/11 for n = 1, 2, 3.

(b) 17/12.
(c) n/9 for n = 1, 2, . . . , 8.
3. (a) Find all n for 2 ≤ n ≤ 50 for which the decimal expansion of 1/n is finite.
(b) Conjecture (without proof) which positive integers n are such that 1/n has a
finite decimal expansion.
4. Find the reduced fractions corresponding to the following decimal expansions:
(a) 0.3143.
(b) 2.03123.
(c) 0.1006100.
5. Suppose that x is a rational number and that y is irrational. Explain why x + y must
also be irrational. What about xy?
5.5. EXERCISES 67
√
6. In decimal form, 2 is 1.41421356 . . . . If we drop the integer part of the decimal ex-
pansion the resulting number is 0.41421356 . . . . Is that number rational or irrational?
Explain.
√ p√
7. We know that 2 is irrational. What about 2? Explain your answer.
p √
8. Show that 1 + 2 is irrational.
√
9. Show that 6 is irrational.
√
10. Show that 15 is irrational.
11. Show that the cube root of 2 is irrational.
12. Give an example of two irrational numbers a and b such that ab is rational.
13. The golden ratio is the positive real number φ which satisfies the equation φ2 − φ = 1.
(a) Use the quadratic formula to find φ.
(b) Show that φ is irrational.
14. Explain why φ and φ2 have the same decimal part. (Hint: Use the equation that
defines φ which is given in the previous question.)
15. (From Edward MacNeal’s Mathsemantics.) Express the following items as percentages
to the nearest whole percent.
7 3
(a) (b) 0.814 (c) 12 ÷ 3 (d) (e) .9 .
10 5
(Note: Edward MacNeal was a consultant for the American airline industry, and this
question appeared on a quiz for prospective secretarial and clerical employees for his
firm. One hundred and ninety-six people took the quiz. The percentages of people
who got the correct answers were (a) 48%, (b) 35%, (c) 25%, (d) 48%, (e)43%. The
figures so alarmed him that throughout the book he used expressions like “84 out of
196” rather than “43 percent”.)
16. (From Sheila Tobias’ Overcoming Math Anxiety.)

(a) What is 25% of 24?
(b) 6 is what percent of 24?
(c) 6 is 25% of what?
(Note: Sheila Tobias anticipates that (b) and (c) would cause anxiety for a consider-
able proportion of the general population.)
17. Comment on the following statement, and give a more accurate comment than the
minister.
Podunk University authorities are concerned. They found that thirty per-
cent of the male students and twenty percent of the female students have
cheated on an exam at one time or another. The minister of education said
“We will no longer fund an institution where 50 percent of the students are
cheaters.”
69
6 Modular Arithmetic
The Keystone Kidnapper. The police of Keystonia had a crack swat team. Their
mission was to rescue the prime minister’s daughter, but they have run into a prob-
lem. Through a sequence of blunders, they enabled the kidnapper to capture them.
He has herded them and the young lady into a room containing seven caskets.
“You’re puny intellect amuses me,” said the kidnapper. “You have one hour to figure
out how escape from this room. Sixty minutes after I leave, six of the seven caskets
will disintegrate releasing venomous snakes. The other casket contains the key to
the door. Find the key before the hour is up and you can escape. I’ll give you a
clue—the key is in casket number 54321. And I’ve done you a favour. The caskets
are not locked.”
“But,” said the team leader, “The caskets are numbered from 1 to 7. None of them
is numbered 54321.”
“I’ll give you another clue: Start counting,” and the kidnapper showed them how.
Casket 1 was 1, casket 2 was 2, and so on until casket 7 which was 7. Then the
kidnapper started counting backwards: casket 6 was number 8, casket 5 was number
9, and so on until casket 1 which was number 13. Then the count reversed once
more, and casket 2 was 14, casket 3 was 15. “You get the idea,” said the kidnapper,
“Goodbye,” and he left them in the locked room.
“Well,” said the team leader, “let’s start counting.”
“Hold it,” said the young lady. “We have less than 60 minutes—that’s 3600 seconds,
and my calculator says that 54321 divided by 3600 is about 15. We would have to
count 15 caskets per second and not make a mistake.”
The prime minister’s daughter figured it out. Which casket contained the key?
Modular arithmetic is the arithmetic of remainders. It is a simple but powerful tool. You
have already worked a bit with remainders, so some of what is done here will seem familiar.
70 CHAPTER 6. MODULAR ARITHMETIC
6.1 Congruent integers
Two integers are said to be congruent modulo m if any one of the these three conditions
hold:
1. Both integers have the same remainder when divided by m.

2. The difference between the integers is divisible by m.
3. The two integers differ by a multiple of m.
The example below should convince you that the three statements are mathematically equiv-
alent. Any one of them may be taken as the definition of congruence.
The notation for congruence is “ ≡ ”, and the symbolism is
a ≡ b (mod m).
which is read “a is congruent to b modulo m”.
Example 6.1.1. Use each of the three definitions to verify the following statement.
16 ≡ 28 (mod 6).
Solution.
1. 16 = 2 · 6 + 4, and 28 = 4 · 6 + 4, so both 16 and 24 have remainder 4 when divided

by 6.
2. 16 − 28 = −12, and −12 is divisible by 6.
3. 16 − 28 = (−2) · 6, that is 16 and 28 differ by a multiple of 6.
Example 6.1.2. Describe all the integers that are congruent to 7 modulo 3.
Solution. What we want is all of the integers that differ from 7 by a multiple of 3. We can
write this in two ways:
( . . . , −5, −2, 1, 4, 7, 10, 13, 16, . . .) (6.1)
or
{ 7 + 3k : k = 0, ±1, ±2, . . . } (6.2)

6.1. CONGRUENT INTEGERS 71
Residue classes
Given a positive integer m, and a fixed integer x (which may be positive or negative), the
set of all integers that differ from x by a multiple of m is called a residue class modulo
m, or a congruence class modulo m. We denote the congruence class containing x by
the symbol [x]. The set in the previous example is the congruence class [7] modulo 3. It
is also the congruence class [1], the congruence class [4], the congruence class [10] and so
on. It is very common to use the smallest nonnegative member n of the congruence class to
denote it, so usually we would use [1] instead of [7].
Example 6.1.3. List all of the congruence classes mod 5.
Solution. The classes are:
[0] = ( . . . , −10, −5, 0, 5, 10, . . . )

[1] = (..., −9, −4, 1, 6, 11, . . . )
[2] = (..., −8, −3, 2, 7, 12, . . . )
[3] = (..., −7, −2, 3, 8, 13, . . . )
[4] = (..., −6, −1, 4, 9, 14, . . . )
Properties
Congruency is what is known as an equivalence relation. This means that it has the three
basic properties of equality—reflexivity, symmetry, and transitivity:
Reflexivity: a ≡ a (mod m). In words, every integer is congruent to itself.
Symmetry: If a ≡ b (mod m), then b ≡ a (mod m).
Transitivity: If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m)
Algebraically, congruences are handled very much like equations. Recall that you can add
equations, multiply equations by a nonzero constant, and so on.
If a≡b (mod m)
and c≡d (mod m)
then a + c ≡ b + d (mod m)
and ac ≡ bd (mod m)
The preceding could be summarized by saying that if you select any x from [a] and any y
from [c] then x+y always in in the congruence class [a+c] and xy is always in the equivalence
class [ac]. Because of this consistency, we can conceive of adding and multiplying equivalence
classes as shown in the table on the next page.
+ [0] [1] [2] [3] [4] × [0] [1] [2] [3] [4]
[0] [0] [1] [2] [3] [4] [0] [0] [0] [0] [0] [0]
[1] [1] [2] [3] [4] [0] [1] [0] [1] [2] [3] [4]
[2] [2] [3] [4] [0] [1] [2] [0] [2] [4] [1] [3]
[3] [3] [4] [0] [1] [2] [3] [0] [3] [1] [4] [2]
[4] [4] [0] [1] [2] [3] [4] [0] [4] [3] [2] [1]
Addition and Multiplication tables for “mod 5” Arithmetic
A useful technique
One of the consequences of the previous properties is that if we have a congruence like
a+b≡c (mod m)
then we can replace a with any number from the congruence class [a], we can replace b with
any number from the congruence class [b], and we can replace c with any number from the
congruence class [c]. Everyone who works with congruences exploits this technique.
Example 6.1.4. Find all nonnegative x with x < 6 that satisfy
13 + 10x ≡ −9 (mod 6). (6.3)
Solution. The six equivalence classes modulo 6 are
[0] = ( . . . , −12, −6, 0, 6, 12, . . . )

[1] = ( . . . , −11, −5, 1, 7, 13, . . . )
[2] = ( . . . , −10, −4, 2, 8, 14, . . . )
[3] = (..., −9, −3, 3, 9, 15, . . . )
[4] = (..., −8, −2, 4, 10, 16, . . . )
[5] = (..., −7, −1, 5, 11, 17, . . . )
The integer 13 belongs to the congruence class [1], the integer 10 belongs to [4], and the
integer −9 belongs to [3]. So the values of x that satisfy the congruence (6.3) also satisfy
the congruence
1 + 4x ≡ 3 (mod 6),
or, equivalently,
4x ≡ 2 (mod 6).
This is now easily solved by substituting x = 0, 1, 2, 3, 4, 5 and seeing which values satisfy
the equation: the solution is x = 2 and x = 5.
A congruence of the form ax ≡ c (mod m) is called a linear congruence. If x = b is a

solution for the congruence, then so is x = b + m, b + 2m, and so on.
Example 6.1.5. Given that in 2002, Halloween fell on a Thursday, what day of the week
will Halloween fall on in 2102?
The strategy is to count the number of days from October 31, 2002 to October 31, 2102
and divide by 7. If the remainder is 0, then Halloween 2102 will fall on Thursday, if the
remainder is 1, it will fall on Friday and so on.
The fact that some years have 366 days instead of 365 adds a minor complication. The
Gregorian Calendar, the one that we currently use, determines leap years according to
the following rules:
A year is a leap year if it is divisible by 4, unless it is a century, in which case it

is not a leap year unless it is divisible by 400.
The Gregorian Calendar assumes that a year is exactly 365.2425 days, and the leap days are
necessary to correct for the .2425. In fact the year is closer to being 365.24219 solar days
long, and because of this the year 2800AD should not be a leap year. In other words, to
correct the Gregorian calendar we need to omit a leap year for every year that is divisible
by 2800. (So in 2800, the Gregorian calendar will incorrectly add a leap day. No doubt we
will have switched to the corrected calendar by the time.)
Solution for Example 6.1.5. There are 100 years from Oct 31, 2002 to Oct 31, 2102, so there
are 365 × 100 days plus a number of leap days. A leap day is added in each of the years 2004,
2008, . . . , 2096, but not in 2100. The number of leap days is therefore (2096 − 2004)/4 + 1,
or 24. So, we want to find the smallest nonnegative x such that
x ≡ 365 × 100 + 24 (mod 7).
Since 100 ≡ 2, and 365 ≡ 1, and 24 ≡ 3, this is the same as finding x such that
x≡1×2+3 (mod 7),
So x = 5 and so Halloween falls on a Tuesday in 2102.
Finding remainders when the dividend is large

Example 6.1.6. Find the remainder when 2835 is divided by 3.
Solution. We are really trying to find the smallest positive x so that 2835 ≡ x (mod 3). We
note that 28 ≡ 1 (mod 3), that is, the integer 1 is a member of the equivalence class mod 3
that contains 28. So, since 28 ≡ 1 (mod 3),
we have 2835 ≡ 135 (mod 3)
35 35
and since 1 = 1 we have 28 ≡1 (mod 3)
which means the the remainder is 1

Solution. We are really trying to find the smallest positive x so that 2635 ≡ x (mod 9). We
have
26 ≡ −1 (mod 9)
=⇒ 2635 ≡ (−1)35 (mod 9)
35
=⇒ 26 ≡ −1 (mod 9)
≡ 8 (mod 9)
So the remainder is 8.

Solution. We have
27 ≡ 2 (mod 5)
=⇒ 272 ≡ 22 (mod 5)
≡ 4 ≡ −1 (mod 5).
17
Now 2735 = 27 · 2734 = 27 272 . We have
272 ≡ −1 (mod 5)
17
=⇒ 272 ≡ (−1)17 ≡ −1 (mod 5)
Now multiply the congruence by 27 to get:

17
27 272 ≡ 27(−1) ≡ 2(−1) ≡ −2 ≡ 3 (mod 5),
so the remainder is 3.
Note that 27(−1) was replaced by 2(−1) because 27 ≡ 2 (mod 5), that is, 2 is in the
congruence class that contains 27.

Solution. Since 14 ≡ 3 (mod 11), this is the same as asking what the remainder is when
3567 is divided by 11. We solve this by taking successive powers of 3, all the while reducing
everything modulo 11.
3=3
32 = 9
33 = 3 · 32 ≡ 3 · 9 ≡ 27 ≡ 5
34 = 3 · 33 ≡ 3 · 5 ≡ 15 ≡ 4
35 = 3 · 34 ≡ 3 · 4 ≡ 12 ≡ 1
Now 3567 = 32 · 3565 = 32 (35 )113 , so continuing from 35 ≡ 1, we have:
32 (35 )113 ≡ 32 (1)113 ≡ 9
So the remainder is 9.
So you see the general procedure: to find the remainder when xn is divided by m, first
replace x by the remainder, r, when x is divided by m. This works because xn ≡ rn
(mod m). (If r = m − 1, replace x by −1 instead, and then use the fact that xn ≡ (−1)n .)
Now start taking powers of r, all the time reducing the result modulo m. Keep doing this
until you get a result of m − 1, m, or 0.
This method cannot always be followed exactly. The following example shows how the ideas
can be adapted.
Example 6.1.10. Find the last three digits of 373135 .

Solution. In this problem we want to find the remainder when 373136 is divided by 1000. In
this case we use a calculator. First we have to get something reasonable. About the largest
power of 373 that my calculator can handle is 3733 and 3733 ≡ 117 (mod 1000), so carrying
on farther, we get
3737 = 373(3733)2 ≡ 373 · 1172 = 5105997 ≡ −3 (mod 1000)
so
373136 = 3737·19 3733 ≡ (−3)19 117 (mod 1000).
Now,
(−3)19 = −1162261467 ≡ 533 (mod 1000),
so
373136 ≡ 533 · 117 = 62361 ≡ 361 (mod 1000),
so the last three digits are 361.

Solution. Since 19 ≡ 6 (mod 13), this is the same as finding the remainder when 6567 is
divided by 13. In the following, all calculations are modulo 13, so the “(mod 13)” has been
omitted for each line.
6≡6
62 ≡ 6 · 6 ≡ 36 ≡ 10
63 = 6 · 62 ≡ 6 · 10 ≡ 60 ≡ 8 (6.4)
4 3
6 = 6 · 6 ≡ 6 · 8 ≡ 48 ≡ 9
65 = 6 · 64 ≡ 6 · 9 ≡ 54 ≡ 2
66 = 6 · 65 ≡ 6 · 2 ≡ 12 ≡ −1 .
Then, break down 6567 into as many powers of 66 as we can: 6567 = 63 (6564 ) = 63 (66 )94
Now use the fact that 66 ≡ −1 and raise both sides of the congruence to the 94th power:
(66 )94 ≡ (−1)94 ≡ 1
and multiplying by 63 :
63 (66 )94 ≡ 63 ≡ 8 by the congruence (6.4).
so the remainder is 8.
In many of the previous examples with small numbers we were always able to find some
power that was congruent to 1 or to −1. This is not always possible, but usually a pattern
emerges that lets you solve the problem. (See Exercise 8.)
6.2 Digital Roots and divisibility tests

Many of the tests for divisibility that were done in Chapter 3 can be justified more neatly
using congruences. Here is a theorem that contains the test for divisibility by 9:
Theorem 6.2.1. If n is a positive integer, then n is congruent modulo 9 to the sum of its
digits.
This theorem says that if we have a number abcde, where a, b, etcetera, are the digits of the
number, then
abcde ≡ a + b + c + d + e (mod 9).
This is more powerful than the divisibility test itself, but the proof is not much different.
Proof of Theorem 6.2.1. The number abcde is 10000a + 1000b + 100c + 10d + e and we have
10000a+1000b+100c+10d+e = 9999a+999b+99c+9d+a+b+c+d+e ≡ a+b+c+d+e (mod 9).

Solution. The remainder is the same as when 1 + 7 + 6 + 4 + 5 + 9 + 8 + 8 + 3 (= 51) is
divided by 9 which is the same as when 5 + 1 is divided by 9 which is 6.
Given a positive integer, sum its digits to get another positive integer. If the new integer
has two or more digits, sum the digits again. Keep doing this until you end up with a single
digit. If the single digit is 9, replace it by 0. The single digit that you end up with is called
the digital root of the original number. The previous example shows that the digital root
of 176459883 is 6.
6.2. DIGITAL ROOTS AND DIVISIBILITY TESTS 77
A better way to find the digital root is to cast out nines as you add the digits: sum the
digits from left to right, and as soon as the sum exceeds 9, subtract 9 from the sum (this is
what is meant by casting out a nine). The single digit that you end up with must be the
digital root. For example with the number 176459883 we have
1 + 7 = 8,
8+6=5 (A 9 has been cast out.)
5+4=0 (Another 9 has been cast out.)
Continue in this fashion. What you are actually doing is just adding the digits modulo 9 as
you go along.
Example 6.2.3. Without actually doing the calculation, show that 163168632818 cannot
be the product of 317177 and 514434.
Solution. The digital roots of 163168632818, 317177, and 514434 are, respectively, 8, 8, and
3. This means that
317177 ≡ 8 (mod 9)
514434 ≡ 3 (mod 9)
so by the properties of congruence
317177 × 514434 ≡ 8 × 3 ≡ 6 (mod 9) ,
but since
163168632818 ≡ 8 (mod 9)
163168632818 and 317177 × 514434 are not congruent modulo 9, so they cannot be the same
number.
Before the advent of calculators, bookkeepers used digital roots as a quick check of the
accuracy of their arithmetic. Note that this does not catch all errors, and if a calculation
passes the digital root test it is not necessarily correct. (However, since bookkeepers were
“good with sums”, that together with the digital root test meant there was a high probability
that the computation was correct.)
6.3 Exercises
1. (a) How many leap days are there between Jan 1, 2003 and Jan 1, 2503?
(b) Given that Jan 1, 2003 was a Wednesday, what day of the week is Jan 1, 2503?
2. (a) Assuming the more correct calendar is used, (that is, the one where 2800 is not
a leap year) how many leap days are there in the period from Jan 1, 2003 and
Jan 1, 3003?
(b) What day of the week does Jan 1, 3003 fall on.
3. The difference in time between Vancouver and Beijing is 9 hours. The international
dateline passes through the Pacific ocean between Vancouver and Beijing.
(a) What time and day is it in Vancouver when it is 7 am Friday in Beijing?
(b) What time and day is it in Vancouver when it is 7 pm Tuesday in Beijing?
(c) The flying time from Beijing to Vancouver is 10 hours. If you leave Beijing at
4pm Monday (Beijing time) at what time will you arrive in Vancouver (Vancouver
time)?
4. The multiplication table for “mod mod 7

mod 5
5” arithmetic is shown on the
right. In it you can see that 2 and × 1 2 3 4 × 1 2 3 4 5 6
3 are inverses of each other (that 1 1 2 3 4 1 1 2 3 4 5 6
is 2 · 3 ≡ 1 (mod 5)). Complete 2 2 4 1 3 2 2 4 6 5
the multiplication table for “mod 3 3 1 4 2 3 3 6 2 5 1
7”, and from it deduce what the 4 4 3 2 1 4 4
inverses of 2, 3, 4, 5, and 6 are. 5 5
6 6
5. If the integer a in the congruence ax ≡ c (mod m) has an inverse in the sense of

question 4, then the congruence can be solved by multiplying by the inverse of a.
For example, in modulo 9 arithmetic, the integer 5 has the inverse 2, so we can solve
5x ≡ 7 (mod 9) by multiplying by 2:
2(5x) ≡ 14 (mod 9)
Since 2(5) ≡ 1 (mod 9), then x ≡ 14 ≡ 5 (mod 9). So the solution is the congruence
class [5].
Use the inverses from Exercise 4 to solve each of the following congruences:
(a) 3x ≡ 2 (mod 5). (b) 4x ≡ −3 (mod 7). (c) 37x ≡ 12 (mod 5).
6.3. EXERCISES 79
6. In ordinary arithmetic, if the product of two numbers is 0, then at least one them
must be 0.
(a) Is this true in “mod 3” arithmetic? (The easiest way to answer this is to check
all products xy where x and y are positive integers less than 3.)
(b) Is this true in “mod 6” arithmetic?
(c) Is this true in “mod 7” arithmetic?
(d) Is this true in “mod 9” arithmetic?
(e) For which positive integers m is the statement true in “mod m” arithmetic?
7. Find all possible values of x from 0 to 7 that satisfy the congruences

(a) 18x + 35 ≡ 29 (mod 8).
(b) 24x ≡ 4 (mod 8).
8. Find the remainder when 823 is divided by 6.

9. Find the remainder when 8 · 9 · 10 · 11 · 12100 is divided by 7.
10. Find the remainder when 435 + 1956 is divided by 15.
11. Using digital roots show that 1765 × 3227 6= 5705655.
12. Using digital roots, what can you conclude about the correctness of 1765 × 3227 =
5695565?
13. In this question, dr(x) denotes the digital root of x.
(a) Given x = 30986 and y = 443092 find dr(x + y) and dr(dr(x) + dr(y)).
(b) Using modular arithmetic, explain why dr(x + y) = dr(dr(x) + dr(y)) for all
positive integers x and y.
(c) Using digital roots show that 123456 + 87876 + 450993 6= 662825.
14. Given a positive integer x, rearrange its digits to form another integer y. Explain why
x − y is divisible by 9.
15. Using Modular arithmetic show that abcdef and −a + b − c + d − e + f have the same
remainder when divided by eleven. Note: The alternating plus and minus signs are
arranged so that the last or rightmost digit is added. For example, the remainder when
7113156 is divided by 11 will be the same as the remainder when 7−1+1−3+1−5+6
is divided by 11.
81
7 Linear Diophantine Equations
Karate Frog. Euclid the frog lives at the end of a line of lily pads. He has to visit
his doctor whose office is on the next lily pad.
Euclid would like to hop right over there.

He can hop back and forth along the line of lily pads, but he was injured in a karate
contest and can only hop with one leg at a time. (That’s why he wants to see his
doctor.) If he hops with his right leg, he always lands exactly 9 lily pads away. If he
jumps with his left he always lands exactly 7 lily pads away.
If he hops 9 forward and 7 backward, he just misses the doctor’s lily pad by 1. If he
hops 7 forward twice and 9 backward he misses the doctor’s lily pad by 4.
How can Euclid hop to his doctor’s lily pad?
This is one puzzle that is completely solved here, so if you want to try it yourself, do it now
before reading further.
One strategy that works is to do forward jumps of 9 and backward jumps of 7, (so long as
Euclid doesn’t back up beyond his own lily pad). Labelling Euclid’s pad as 0, the doctor’s
pad as 1, etc, Here’s what happens:
jumps lands at
Forward 9 9
back 7 2
forward 9 11
back 7 4
forward 9 13
back 7 6
forward 9 15
back 7 (two jumps) 1
What happens if he uses forward jumps of 7 and backward jumps of 9?

82 CHAPTER 7. LINEAR DIOPHANTINE EQUATIONS
jumps lands at
Forward 14 (two jumps) 14
back 9 5
forward 7 12
back 9 3
forward 7 10
back 9 1
In the first case Euclid made a total of 4 forward jumps and 5 backward jumps. He could
have combined all forward jumps and all backward jumps and the equation for this becomes:
9 · 4 + 7 · (−5) = 1.
In the second case, there are 4 forward jumps of 7 and three backward jumps of 9 and the
equation becomes:
9 · (−3) + 7 · 4 = 1.
Other solutions are possible, for example, 11 forward jumps of 9 and 14 backward jumps of
7, which gives the equation:
9 · 11 + 7 · (−14) = 1.
In general we want a solution in integers to the equation

9x + 7y = 1.
A Diophantine equation is one where the coefficients and variables are all integers.
The Diophantine equation a1 x1 + a2 x2 + · · · + an xn = c is called a linear Diophantine
equation in n variables x1 , x2 , . . . , xn , where the coefficients a1 , a2 , . . . , an are not
all 0.
7.1 The single variable case

The case where there is only one variable, where ax = c, is almost too easy.
Example 7.1.1. 1. Solve 3x = 6. 2. Solve 4y = 7.

Solution.
1. The solution is x = 2.
2. If this were an algebraic equation the only solution would have been y = 7/4. However,
since 7/4 is not an integer, there is no solution.
There is a solution to ax = c if and only if a|c, and the unique solution is x = c/a. It is far
more interesting when there are two variables, as in 9x + 7y = 1.
7.2. THE HOMOGENEOUS CASE 83
7.2 The homogeneous case

When the constant term c is zero, a linear equation is called homogeneous and we discuss
that case first.
Example 7.2.1. Find a solution in integers for 3x = 5y.

Solution. Just as is the case with ordinary algebra, we expect that are many different values
of x and y that satisfy the equation. There is an obvious solution (x, y) = (0, 0).1 This is
called a trivial solution and it is rarely of interest.
If we look at the equation 3x = 5y from an algebraic viewpoint, we can imagine the solutions
being generated as we plug in different values for x. Let us try the same idea from a
“Diophantine” viewpoint. In this case, the variables can only be increased or decreased by
integral values.
Increasing x by 1 increases the left side of the equation by 3. To keep it balanced the right
side of the equation would also have to increase by 3. But this is impossible because the
right side can only change by multiples of 5.
So we try increasing x by 2, 3, and so on, and the first success occurs when we increase
x by 5—in this case the left side of the equation increases by 15, and the balance can
be maintained by increasing y by 3. This yields a second solution (x, y) = (5, 3). If we
increase x by an arbitrary multiple of 5, we can balance the equation by increasing y by the
corresponding multiple of 3. The same goes if we decrease the variables instead of increasing
them. It follows that all solutions are in the family (x, y) = (5k, 3k), where k is an arbitrary
integer.
Note: The solution (x, y) = (5k, 3k), where k = 0, ±1, ±2, . . ., is called the general solu-
tion, or simply, the solution of the equation 3x = 5y. If a specific numerical value of k is
used, the result is called a particular solution. For example if we set k equal to 1, the
result, namely (x, y) = (5, 3), is a particular solution.
Example 7.2.2. Solve 4x + 6y = 0.

Solution. Using Example 7.2.1 as a template, it appears that the family of solutions is
(x, y) = (6k, −4k). However, this misses the solution (x, y) = (3, −2). Why did that
happen? The reason is that 6 and 4 are not relatively prime. We should first divide by 2
(the gcd of 6 and 4) and reduce the equation to 2x + 3y = 0. Then (x, y) = (3k, −2k) is the
correct solution.
From these two examples, we see that to solve the equation ax + by = 0, we should first
check if gcd(a, b) = 1. If this is not so, divide the equation by the greatest common divisor
to obtain a new one for which this is the case.
1 The notation “(x, y) = (a, b)” means x = a and y = b.

Theorem 7.2.3. If gcd(a, b) = 1 then the complete family of solutions to ax + by = 0 is

(x, y) = (bk, −ak), k = 0, ±1, ±2, . . . .
Proof. To fully justify the theorem, we have to show that

(a) (x, y) = (bk, −ak) is a solution for all k = 0, ±1, ±2, . . . , and that
(b) every solution is of this form.
To verify (a), just substitute (x, y) = (bk, −ak) into the equation and check that the equation
balances.
To verify (b), suppose that (x, y) = (x0 , y0 ) is a solution. We will show that there is some
k such that x0 = bk and y0 = −ak.
Since (x0 , y0 ) is a solution, we have ax0 = −by0 .
Then, ax0 and −by0 are the same number, so what ever divides one of them must also divide
the other. Since b |(−by0 ), this means that b |(ax0 ). But since gcd(a, b) = 1, this means that
b | x0 . In other words, x0 = bk for some integer k. So now the equation becomes
abk = −by0 ,
and solving this for y0 gives y0 = −ak. This completes the proof.
Question 7.2.4. Is it possible for a linear homogeneous Diophantine equation to have
(a) no solutions?
(b) a unique solution?
(c) exactly two solutions?
(d) exactly fifty solutions?
(e) infinitely many solutions?
7.3 The linear case

Solution. The numbers involved are relatively small, and by inspection we can pick out the
particular solution (x, y) = (−2, 2). We can obtain other solutions by incrementing x as
before. Rewrite the equation in the form 5y = 4 − 3x. If we increase x by 5, then the right
side of the equation is decreased by 15. To maintain balance, we must decrease y by 3. This
leads to the general solution (x, y) = (−2 + 5k, 2 − 3k).
7.3. THE LINEAR CASE 85
Note that (x, y) = (−2, 2) is a particular solution to 3x + 5y = 4 while (x, y) = (5k, −3k)
is the complete solution to the homogeneous equation 3x + 5y = 0. When we add the
corresponding components of both solutions, we get the complete solution for the original
equation. This illustrates the typical approach in solving a linear Diophantine equation:
First find a particular solution and then obtain the general solution by incorporating the
general solution for the homogeneous case.

Solution. Since the greatest common divisor of 9 and 15 is 3, 9x + 15y is a multiple of 3
whatever integer values x and y may assume. Fortunately, 12 is also a multiple of 3. In
fact, we may as well cancel out the common factor 3 and reduce the equation to 3x + 5y = 4
which is solved as in Example 7.3.1.
Example 7.3.3. Solve 3x − 6y = 2.

Solution. This equation has no integer solutions. Since the greatest common divisor of 3
and 6 is 3, 3x − 6y is a multiple of 3 whatever integer values x and y may assume. However,
2 is not a multiple of 3, and we cannot have 3x − 6y = 2.

Solution. Since gcd(4, 6) = 2, and since 2 divides 12, we know there is a solution.
So first we find a particular solution to 4x+6y = 2. We see by inspection that (x, y) = (−1, 1)
is a particular solution.
So, 4(−1)+ 6(1) = 2, and multiplying by 6 we get 4(−6)+ 6(6) = 12, so a particular solution
to the initial equation is (x, y) = (−6, 6).
Since gcd(4, 6) = 2, as in Example 7.2.2 we have to shift x and y by multiples of 6/2 and
−4/2 respectively to get the general solution:
(x, y) = (−6 + 3k, 6 − 2k).
Here is the same solution presented in a different way to emphasize the role of the homoge-
neous components.
A particular solution to the equation 4x + 6y = 2 is
(x0 , y0 ) = (−6, 6).
The complete solution to the homogeneous equation 4x + 6y = 0 is
(x1 , y1 ) = (3k, −2k).
The general solution for 4x + 6y = 2 is obtained by adding the two solutions:
(x, y) = (x0 + x1 , y0 + y1 ) = (−6 + 3k, 6 − 2k).

Some people prefer to solve Example 7.3.4 by first dividing the equation 4x + 6y = 12 by
gcd(4, 6) obtaining the new equation 2x + 3y = 6. This is the approach that we used in
Example 7.3.2. It introduces an extra step, but it does work. The drawback to solving
the equation this way is that it is not necessary to do so, and there are equations like
247x + 221y = 78 where it is not obvious what gcd(247, 221) is.
These examples suggest the following general method for solving the Diophantine equation
ax + by = c.
1. Find a particular solution as follows.
(a) Determine the greatest common divisor d of a and b.

(b) If d does not divide c, the Diophantine equation has no solutions and we are
finished.
If d divides c, find a particular solution x = u and y = v to ax + by = d.
(c) Multiply u and v by c/d to obtain a particular solution to ax + by = c.
2. Next find the general solution.
(a) Let a′ = a/d, b′ = b/d. Note that the greatest common divisor of a′ and b′ is 1.
(b) The family of solutions is given by (x, y) = (u+b′ k, v−a′ k) where k is an arbitrary
integer. Note that we must use a′ and b′ instead of a and b, otherwise we will
miss some solutions.
So far, we have found particular solutions “by inspection”, which is just a fancy way of
saying we tried a few different values for the variables until we found some that worked. It
is not always easy to obtain a particular solution in this manner. Fortunately, the Euclidean
Algorithm will always rescue us:
Example 7.3.5. Solve 143x + 105y = 3.
Solution. We first determine the greatest common divisor of 143 and 105 by the Euclidean
Algorithm.
143 − 105 = 38
105 − 2(38) = 29
38 − 29 = 9
29 − 3(9) = 2
9 − 4(2) = 1 (7.1)
2 − 2(1) = 0
Since gcd(143, 105) = 1 there is a solution to 143x + 105y = 3.

7.3. THE LINEAR CASE 87
Stepping backwards through the Euclidean algorithm, beginning with equation (7.1) we
solve 143x + 105y = 1. The computations are shown below.
1 = 9 − 4(2)
= 9 − 4(29 − 3(9)) = 13(9) − 4(29)
= 13(38 − 29) − 4(29) = 13(38) − 17(29)
= 13(38) − 17(105 − 2(38)) = 47(38) − 17(105)
= 47(143 − 105) − 17(105) = 47(143) − 64(105).
So (x, y) = (47, −64) is a particular solution of 143x + 105y = 1. Multiplying by 3, we get

a particular solution (x, y) = (141, −192) for 143x + 105y = 3.
Then, the general solution is (x, y) = (141 + 105k, −192 − 143k).
Example 7.3.6. Solve 4757x − 3763y = 142.

Solution. We first determine the greatest common divisor of 4757 and 3763 using the Eu-
clidean Algorithm.
4757 − 3763 = 994
3763 − 3(994) = 781
994 − 781 = 213
781 − 3(213) = 142
213 − 142 = 71
142 − 2(71) = 0
The algorithm reveals that gcd(4757, 3763) = 71 and since 71 | 142 we conclude that the
equation has a solution. The next step is to solve 4757x − 3763y = 71. Stepping backward
through the Euclidean algorithm, we get
71 = 213 − 142
= 213 − (781 − 3(213)) = 4(213) − 781
= 4(994 − 781) − 781 = 4(994) − 5(781)
= 4(994) − 5(3763 − 3(994)) = 19(994) − 5(3763)
= 19(4757 − 3763) − 5(3763) = 19(4757) − 24(3763)
A particular solution for 4757x − 3763y = 71 is therefore (x, y) = (19, 24). Multiplying by
142/71, we get a the particular solution for 4757x − 3763y = 142, namely (x, y) = (38, 48).
Dividing the coefficients 3763 and 4757 by 71, we get 3763/71 = 53 and 4757/71 = 67, so
the general solution is
(x, y) = (38 + 53k, 48 + 67k).
Note the signs in the general solution for Example 7.3.6 are positive due to the negative
coefficient in the Diophantine equation.
7.4 When there are constraints

Example 7.3.1 actually provides all possible solutions to the Die Hard Jugs problem. Here
is how the equation 3x + 5y = 4 is connected to the problem. Think of the jugs as being a
“system” to which we can add or discard water. Initially there are 0 gallons of water, and
the objective is to end up with exactly 4 gallons in the system. The only actions that can
be performed are:
1. Fill an empty jug completely from the fountain.
2. Empty a jug (not into the other jug).
3. Pour everything from one jug into the other leaving the first jug empty and partially
filling the second jug.
4. Pour enough from one jug into the other to fill the second jug, leaving some contents
in the first jug.
Only the first two actions change the amount of water in the system, so all we are really
doing is adding and subtracting multiples of 5 and 3 in order to end up with 4. In other
words, we are trying to solve the linear Diophantine equation 3x + 5y = 4.
The constraint on this puzzle is that at any given time you cannot have more than 3
gallons in the 3 gallon jug or more than 5 gallons in the 5 gallon jug. When there are
constraints there is still some work to be done to apply the solution of the Diophantine
equation to the original problem. Let us pick some particular solutions from the general
solution (x, y) = (−2 + 5k, 2 − 3k) and see how each solves the jug problem.
Case 1: k = 0. Here x = −2, y = 2, which says fill the 5-gallon jug twice and empty the
3-gallon jug twice. In order to do this, of course, we have to transfer water from the 5-gallon
jug to the 3-gallon jug as needed. It goes like this: Fill the 5-gallon jug and empty it into
the 3-gallon jug, then empty the 3-gallon jug. This leaves the system with 2 gallons in the 5
gallon jug. Pour the 2 gallons into the 3-gallon jug, then fill the 5-gallon jug. We now have
7 gallons in the system. Using the five gallon jug, top up the 3-gallon jug and then empty
the 3-gallon jug. We are left with 4 gallons in the system.
Case 2: k = 1. Then x = 3, y = −1, which says fill the 3-gallon jug three times and empty
the 5-gallon jug once. We leave the details as an exercise.
Case 3: k = −1. Then x = −7 and y = 5. This tells us to fill the 5-gallon jug 5 times and
empty the 3-gallon jug 7 times, transferring water from the 5-gallon jug to the 3-gallon jug
as needed.
The Karate Frog problem also has constraints because the hopping has to be arranged so
that the frog always lands on a lily pad with number 0 or more (there are no lily pads with
negative numbers). In this case it is relatively easy to satisfy the constraints: Do all the
forward hops before any of the backward hops.
7.4. WHEN THERE ARE CONSTRAINTS 89
Here is a problem where there are constraints on the values of variables in the Diophantine
equation that arises.
Example 7.4.1. A person has a collection of silver coins of two different types. One type
is worth 4 dollars, the other is worth 7 dollars. She wants to use the coins to pay a debt of
29 dollars. The person she is paying cannot make change. Can she pay off her debt with
the silver coins?
Solution. It is quite easy to find a solution by trial an error: 2 of the four dollar coins plus
3 of the seven dollar coins will total 29. However, for other problems, it may not always be
as easy to find a solution, so let us proceed in a more systematic way.
We begin by writing the corresponding Diophantine equation.
4x + 7y = 29. (7.2)
Since the person who is owed the money cannot make change, both x and y must be
nonnegative integers. That is, the constraints are x ≥ 0, and y ≥ 0.
We will solve the equation using the method outlined on page 86. Since gcd(4, 7) = 1, there
will be a solution. Following usual procedure in dealing with an equation like ax + by = c,
we replace c by the greatest common divisor of a and b and first solve the equation ax+ by =
gcd(a, b). In this case we want to solve
4x + 7y = 1. (7.3)
Either by inspection or by using the Euclidean Algorithm, we see that (x, y) = (2, −1) is a
particular solution for equation (7.3). If (x, y) satisfies equation (7.3), then (29x, 29y) will
satisfy equation (7.2). So to obtain a particular solution for equation (7.2) we multiply the
solution for equation (7.3)
by 29. In other words, a particular solution for equation (7.2) is
(x, y) = 29(2), 29(−1) = (58, −29).
To obtain the general solution, we incorporate the general solution for the homogeneous
equation 4x + 7y = 0, which is (x, y) = (7k, −4k). The general solution for equation (7.2) is
(x, y) = (58 + 7k, −29 − 4k).
Now we want a particular solution that fits the constraints of the original problem. We
must have −29 − 4k ≥ 0 and 58 + 7k ≥ 0. The first constraint implies that k cannot be
larger than −8 and the second constraint means that k cannot be smaller than −8. So, k
must be −8, and then

(x, y) = 58 + 7(−8), −29 − 4(−8) = (2, 3).
This shows that the person can pay off her debt using the strange silver coins but in one
and only one way.
The following problem frequently appears in puzzle books and it illustrates more realistically
the need for our formalized method. Note that again there are constraints on the values of
the particular solution.
Example 7.4.2. When Mrs. Brown cashed her pay cheque, the absent-minded teller gave
her as many cents as she should have dollars, and as many dollars as she should have cents.
Equally absent-minded, Mrs. Brown left with the cash without noticing the discrepancy. It
was only after she spent 5 cents that she noticed now she had twice as much money as she
should. What was the amount of her cheque?
Solution. Let x be the number of cents in the amount of the cheque, and let y the number
of dollars. Note that the constraints on x and y are that 0 ≤ x < 100 and 0 ≤ y < 100.
The amount of the cheque in cents is 100y + x (we choose cents to avoid decimals).
The amount of cash Mrs. Brown left with is 100x + y, and after her expenditure, she had
100x+y−5 left. Since this is double 100y+x, we have our equation 100x+y−5 = 2(100y+x),
which simplifies to 98x − 199y = 5. Using the Euclidean Algorithm to find the gcd we get
199 − 2(98) = 3
98 − 32(3) = 2
3−2 = 1.
So, gcd(199, 98) = 1, and this means that there is a solution. Back-stepping through the
algorithm, we get a particular solution to 98x − 199y = 1:
1=3−2
= 3 − (98 − 32(3))
= 33(3) − 98
= 33(199 − 2(98)) − 98
= 33(199) − 67(98).
So x = −67 and −y = 33, and a particular solution to 98x − 199y = 1 is (x, y) =

(−67, −33). Multiplying by 5 gives a particular solution for 98x − 199y = 5, namely
(x, y) = (−335, −165).
Clearly, this particular solution is not the correct one, and we will have to look among the
family of all solutions to find it. The general solution is
(x, y) = (199k − 335, 98k − 165).
For the solution to make sense, we must have 0 < x < 100. From 0 < 199k − 335 < 100,
the only possible integer value is k = 2. Hence (x, y) = (63, 31). Note that this also satisfies
the constraint on the variable y, so that Mrs. Brown’s cheque was for $31.63.
7.5. WHEN THERE ARE MORE THAN TWO VARIABLES 91
7.5 When there are more than two variables

We end this chapter with two examples showing how to handle a linear Diophantine equation
in three variables.
Example 7.5.1. Solve 2x + 3y − 5z = 1.

Solution. We let w = 2x + 3y so that the equation becomes w − 5z = 1. Solving this first,
we have (w, z) = (6 + 5ℓ, 1 + ℓ).
Solving 2x + 3y = 1, we have (x, y) = (−1 + 3k, 1 − 2k), so that the solutions of 2x + 3y = w
are (x, y) = (−w + 3k, w − 2k). It follows that the solutions of 2x + 3y − 5z = 1 are
(x, y, z) = (−6 − 5ℓ + 3k, 6 + 5ℓ − 2k, 1 + ℓ).
Example 7.5.2. Solve 60x + 51y + 32z = 121.

Solution. Note that gcd(60, 51) = 3. Hence we let 3w = 60x + 51y to guarantee that
the “constant term” 3w is divisible by gcd(60, 51) . Making the substitution, the original
equation becomes
3w + 32z = 121.
We first solve this equation. We have gcd(3, 32) = 1 = 11(3) − 32, so that 121 = 1331(3) −
121(32) = 19(3) + 2(32). The family of solutions of 3w + 32z = 121 is
(w, z) = (19 + 32ℓ, 2 − 3ℓ).
We now return to the equation 3w = 60x + 51y, which may be rewritten as 20x + 17y = w.
We have gcd(20, 17) = 1 = 6(20) − 7(17) from which we get
(x, y) = (6w + 17k, −7w − 20k).
It follows that the family of solutions of the original equation is

(x, y, z) = 6(19 + 32ℓ) + 17k, −7(19 + 32ℓ) − 20k, 2 − 3ℓ .
The last two examples shows how our method for solving linear Diophantine equations with
two variables can be extended to solve those with more variables. With two variables, the
solution family has a single parameter which we call k. With three variables, the solution
family has two parameters k and ℓ. The number of parameters in the solution family is
always one less than the number of variables.
7.6 Exercises
1. Are there any solutions of the following linear Diophantine equations? In each case
give reasons.
(a) 5y = 3;
(b) 3x + 5y = 3;
(c) 6x + 4y = 3;
(d) 8x + 4y = 28;
(e) 12x + 18y = 3?
2. Find integers x and y such that 8x + 3y = 1 and

(a) x is positive and y is negative,
(b) x is negative and y is positive.
3. Given the Diophantine equation 6x + 14y = 110.

(a) Find the general solution.
(b) Find all solutions subject to the constraints x ≥ 0, y ≥ 0
4. You have collection of 25 and 40 gram weights. Show how to weigh a 5 gram marble
using an accurate pan balance.
5. Solve the Diophantine equation 71x + 97y = 1.
6. You have collection of 25 and 40 gram weights. Show how to weigh a 5 gram marble
using an accurate pan balance.
7. Solve the Diophantine equation 605x − 132y = 22.
8. Complete the solution to the Die Hard Jug problem for case 2 on page 88.
9. In the Die Hard Jug problem, something strange happens when we try to use the
particular solution for case 3 on page 88. What is strange about it?
7.6. EXERCISES 93
10. Karate frog again. Euclid the frog wants to visit his friend Sammo, who lives on
lily pad #5 (Read about Euclid on page 81.)
Euclid can hop back and forth along the line of lily pads but he is not allowed to get
his injured leg wet. This time if he hops with his right leg, he always lands exactly 11
lily pads away. If he jumps with his left he always lands exactly 7 lily pads away.
How can Euclid hop to Sammo’s lily pad?
(a) Write the linear Diophantine equation that describes the puzzle, and explain how
the equation relates to the problem.
(b) Find the family of all solutions.
(c) Find two different particular solutions and explain how these solve the puzzle.
11. A pet shop owner bought an even number of hamsters at $2 each, and the same number
of parakeets at $1 each. Each pet was marked up 10%, and when all but seven of them
had been sold, the original cost had been recovered. What was the potential profit,
as represented by the retail value of the remaining pets?
12. Mrs. Kalinski has a collection of two types of ceramic tiles. One type measures 14 × 5
cm, the other, 8 × 5 cm. She wishes to tile the top of a small table that is 96 cm wide
by 125 cm long. She realizes that 125 is a multiple of 5, so she could tile it with 25
rows if she could find a way to fit a mixture of the 14 cm and 8 cm tiles that fit in
each row. Can she do this? A typical row of the table might look something like this:

5 cm ...
The tiling pattern does not have to be periodic.
13. Cuisenaire rods are coloured sticks of lengths measuring from 1 cm to 10 cm that
represent the integers from 1 through 10. They are sometimes used to help teach
arithmetic. When several rods are placed end to end the result is called a train. For
what values of n can a train of 6-rods differ from a train of n-rods by exactly one
4-rod?
14. The admission fee for a year-end banquet was $35.00 for professors and $27.00 for
students. The admission fees totalled $1432.00. How many of each attended?
95
8 Number bases
You are so familiar with how we represent numbers that it can disguise the problems that
youngsters have with simple arithmetic. You know how to multiply and divide multi-digit
numbers, but if you are pressed for an explanation you might be forced to say “Because
that is the way it is done”.
Numbers and the symbols that represent them are not one and the same. The number
“fifteen” can be written “15”, or “F ”, or “XV”—the first uses decimal digits, the second is
a hexadecimal representation, and the third uses Roman numerals. The method that we use
to represent numbers does not affect their basic properties: 15 + 12 is the same as 12 + 15;
F + B is the same as B + F ’, and XV + XII is the same as XII + XV.
There is a big difference, however, between the first two representations and the Roman nu-
meral system. Decimal and Hexadecimal numbers are positional systems; Roman numerals
are not.
The Romans represented the numbers 1 through 15 as follows:
I II III IIII V VI VII VIII VIIII X

(1) (2) (3) (4) (5) (6) (7) (8) (9) (10)
XI XII XIII XIIII XV XVI XVII XVIII XVIIII XX

(11) (12) (13) (14) (15) (16) (17) (18) (19) (20)
The use of IV and IX to represent 4 and 9 did not occur until the middle of the dark
ages. In the Roman system, the symbols I, V, and X have very specific meanings and do
not depend upon where they occur in the number. They are, in effect, the “atoms” of the
Roman numbering system.
The Roman numeration system has two serious defects. First, as the numbers get larger
and larger more and more symbols have to be introduced. The second and most obvious
defect is that Roman numerals are very inconvenient for calculations, so cumbersome, in
fact, that the Romans did not use Roman numerals for calculations! Roman numerals were
primarily for recording numbers. A Roman mathematician would use a counting board
or an abacus to do arithmetic calculations. The Roman numeral representation would be
transformed to beads or pebbles on a counting board, the computation would take place
by moving the beads or pebbles, and the result would be transformed back into Roman
numerals. By using an abacus, the Romans were effectively converting their numbers to a
positional system before doing the arithmetic.
A positional system overcomes both defects. In a positional system, the numbers are rep-
resented by a string of digits but the meaning of the digits depends upon where they occur
in the number—91 and 19 are not the same number. With a positional system there is
no need for a welter of symbols. Every positive integer can be represented using only a
finite number of digits. Moreover, positional systems possess the amazing property that it
is possible to use them directly for calculating. The rules for computing with a positional
96 CHAPTER 8. NUMBER BASES
system actually reflect exactly what you would do on an abacus, and as people became more
and more skilled with the decimal system this eventually led to the decline of the abacus.
Our number system uses ten digits. There are positional systems that use a different number
of digits. The base-2 system uses two digits, 0 and 1. Base-six numbers use six digits, 0, 1,
2, 3, 4, and 5. A system that uses n digits is called a base-n system.
In this chapter we will learn how to perform the basic arithmetic calculations using different
bases. Your inexperience with these bases will likely cause some confusion, the same sort of
confusion that youngsters have—when children start learning math, they are as unfamiliar
with base-ten numbers as you are with base-five or base-twelve numbers. In fact, you have
a decided advantage: you already have base-ten as a model; the children have nothing as a
model.
8.1 Binary numbers
A mind reading trick.
1 3 5 2 3 6 4 5 6 8 9 10
7 9 11 7 10 11 7 12 13 11 12 13
13 15 14 15 14 15 14 15
A B C D
Each of the numbers from 1 through 15 appear on one or more of the cards shown
above. A spectator chooses a number, and tells you which cards contain the number.
For example, if the secret number is 11, the spectator will say that the number is on
cards A, B, and D. Then you immediately tell the spectator what the chosen number
is.
This is one of the oldest mathematical tricks. The secret is to add the numbers in the upper
left hand corners of the named cards. The numbers on cards A, B, and D are 1, 2, and 8,
so the number 11 must have been chosen. If you repeat the trick enough times, eventually
everyone you show it to will know the secret. But knowing how it is done doesn’t explain
what numbers should be on what cards.
8.1. BINARY NUMBERS 97
The distribution of the numbers is determined by using their binary expansions. Every
number from 1 to 15 can be written as a sum of the numbers 1, 2, 4, and 8. In fact every
positive integer can be written in a unique way as the sum of powers of 2. The following
example is not a proof, but it should convince you that the preceding statement is true:
Example 8.1.1. Express 221 as the sums of powers of two.

Solution. First write the powers of 2:
1 2 4 8 16 32 64 128 256 . . .
We stop here because 128 < 221 < 256, that is, because 128 is the largest power of two that
does not exceed 221. This means that 128 is one of the powers of two that will be used to
create the sum. We remove 128 from 221, and then look for the next largest power that can
be removed. The full process looks like this:
221 = 128 + 93
= 128 + 64 + 29
= 128 + 64 + 16 + 13
..
.
= 128 + 64 + 16 + 8 + 4 + 1
or, writing it as actual powers:
231 = 27 + 26 + 24 + 23 + +22 + 20 .
If we are going to write lots of numbers as powers of 2, it is tedious to use the preceding
notation. Instead, we use a positional notation to indicate which powers of two are present,
the rightmost position being for 20 . We put 1’s or 0’s in the position according to whether
the indicated power of 2 appears or does not appear in the expansion obtained. So, for 221,
you would get
1 1 0 1 1 1 0 1
7 6 5 4 3 2 1
2 2 2 2 2 2 2 20
So, instead of writing 27 + 26 + 24 + 23 + +22 + 20 , we could simply write 11011101, which

is called the binary expansion or binary representation, or base–2 representation of 221.
When different bases are involved, it is a common practice to indicate the base by using a
parenthetical subscript, so we would write
221(10) = 11011101(2) .
As easy as it is to convert a base-ten number to base-two, it is even easier to convert back.
Example 8.1.2. Express 10111010(2) as a base-ten number.
Solution. Here is the number with the powers of 2 written below the corresponding digits:
1 0 1 1 1 0 1 0
27 26 25 24 23 22 21 20
So in base-10, this is the number 27 + 25 + 24 + 23 + 21 = 128 + 32 + 16 + 8 + 2 = 186.
The numbers on the cards

The table on the right lists the binary expansions of the num-
bers from 1 through 15 (except that we have used blanks in D C B A
the places of the zeros). The four cards in the binary card 8 4 2 1
trick correspond to the four columns, and the columns tell
1 1
what should be on each card.
2 1
On card A we put the numbers whose binary representation 3 1 1
has a 1 in the column headed by A. On card B we put the
4 1
numbers whose binary representation has a 1 in the column
headed by B. We do the same for C and D. For example, the 5 1 1
C column contains 1’s beside the numbers 4, 5, 6, 7, 12, 13, 6 1 1
14, and 15, so card C must contain those eight numbers. 7 1 1 1
So, when I say if you tell me what cards your number is on, 8 1
then I can tell you what your number is, I am really saying 9 1 1
that if you tell me what your number is in base-2, then I can 10 1 1
tell you what it is in base-10. 11 1 1 1
The trick can be carried farther. Each of the integers from 12 1 1
1 to 31 and be written as the sum of numbers from the set 13 1 1 1
{1, 2, 4, 8, 16}, and so you could use 5 cards with numbers 1, 14 1 1 1
2, 4, 8, and 16 in the upper left corner.
15 1 1 1 1
8.2 Base-n blocks and the line abacus

We will begin with two physical models that are frequently used for counting, and for adding
and subtracting in different bases. Perhaps a word or two is worthwhile here. Many texts
advocate the use of base-10 blocks for teaching children about our number system, and this
approach also works for other bases as well. However, several students said that base-n
blocks confuse them, even ’though they were unable to pin down the reason. The figure
below shows what base-4 blocks look like, and the picture suggests what might be the cause
of the problem:
8.2. BASE-N BLOCKS AND THE LINE ABACUS 99
Base-4 Blocks
1 2 3 10
11 12 13 20
The problem arises because the shape of a block corresponds to the size of the digit rather
than its position in the number. If you were to use base-ten blocks to represent the number
111, you could use one large slab-like block for the 100, a rod for the 10, and a cube for
the unit. However, for even moderately sized numbers, you will need many different sized
blocks! Does this sound familiar? Using different shaped blocks to represent numbers is
really not very much different than using Roman numerals.
A line abacus consists of a set of parallel lines with the numbers 1, 10, 100, etc, written
below them starting with 1 on the right. Numbers are represented by placing tokens on
various lines. If you are in base-n, you can place at most n − 1 tokens on a line. The
diagram below shows the first few numbers using a base-4 line abacus.
Base-4 line abacus
1000 100 10 1 1000 100 10 1 1000 100 10 1 1000 100 10 1
1 2 3 10
1000 100 10 1 1000 100 10 1 1000 100 10 1 1000 100 10 1
11 12 13 20
In base-4 the digits are 0, 1, 2, and 3. We would count: 1, 2, 3, 10, 11, 12, 13, 20, 21, and
so on. When we count objects in base-4 like this, each place tells us how many groups of
objects we have. The rightmost digit tells us how many groups of size 1 we have, the next
digit to the left tells us how many groups of size four (which is 10(4) ) we have, the next digit
tells us how many groups of size sixteen (which is 100(4)), the next tells how many groups
of size sixty-four (which is 1000(4)), and so on.
NOTE: When counting in a base other than ten, it is a good practice to avoid using the
words “ten”, “eleven”, “twelve” and so on. The reason is that the association of these
numbers with the base-10 system is so strong that it may cause you to think in base-ten
rather than in the base you are working in. So, when you are counting in base-4, think
“one”, “two”, “three”, “one-zero”, “one-one”, “one-two” , “one-three, “two-zero” . . . .
If b is a positive integer bigger than one but less than or equal

to ten, then base-b integers use the digits 0, 1, 2, . . . , (b − 1), Base
so base-2 uses digits 0 and 1, base-3 uses digits 0, 1 and 10 2 3 4 12
2, and so on. Since we only have 10 symbols for digits, 0 0 0 0 0
when b is greater than 10 we have to include extra sym- 1 1 1 1 1
bols. We will adopt the practice of using uppercase letters, 2 10 2 2 2
so base-11 uses digits 0, 1, 2, . . . , 8, 9, A and base-16 uses digits 3 11 10 3 3
0, 1, 2, . . . , 8, 9, A, B, C, D, E, F . 4 100 11 10 4
5 101 12 11 5
An odometer provides another model for counting in base-n. 6 110 20 12 6
When the rightmost digit (the units digit) becomes (n − 1), 7 111 21 13 7
a “rollover” occurs. The same thing happens when you are 8 1000 22 20 8
using a line abacus or base-n blocks. The table shows the 9 1001 100 21 9
rollover effect for bases 10, 2, 3, 4, and 12. 10 1010 101 22 A
11 1011 102 23 B
12 1100 110 30 10
13 1101 111 31 11
It is important to understand that no matter what base we 14 1110 112 32 12
use, we can represent every positive integer using that base 15 1111 120 33 13
without the need for additional symbols. 16 10000 121 100 14
8.3 Addition of base-n numbers

To add small or single-digit numbers, it is probably easiest to count up to the sum.
Example 8.3.1. Find 13(5) + 4(5)
Solution. Counting the base-5 numbers starting with 13 (that’s one-three in base 5):
13 14 20 21 22 23 24
+1 +2 +3 +4
So in base-5, 13 + 4 is 22.
8.3. ADDITION OF BASE-N NUMBERS 101
Addition with a line abacus

Example 8.3.2. Compute 134(5) + 23(5) .
Addition of multi-digit numbers can be done easily with a line

abacus. Begin by drawing a horizontal line on the abacus.
To add 23(4) and 134(4) on a base-5 line abacus, put the counters
for one number above the horizontal line and the counters for
the other below it.
1000 100 10 1
Push all counters together keeping them on their original lines.

On the rightmost unit line there are too many counters. So
remove five of the counters from the unit line and place an extra
counter on the 10 line. (We remove 5 because we are dealing
with base-5 numbers.)
1000 100 10 1
After doing this the unit line is OK, but now there are too many
counters on the 10 line.
1000 100 10 1
Remove five counters from the 10 line and place an extra counter
on the 100 line. All lines are now OK, and the sum is 212.
1000 100 10 1
As you can see, a line abacus is useful in describing the arithmetic of positional systems. It is
an interesting sidelight to note that prior to the universal adoption of our base-10 positional
system, calculations were performed on some sort of abacus. They are very efficient for
adding and subtracting numbers1 , and are still in use in many places around the world.
In the western hemisphere they seem to be relegated to helping elementary students learn
basic arithmetic. This is somewhat ironic, because in the past it was the great efficiency of
the abacus that hindered the adoption of the base-10 system.
Pencil and paper addition

Addition with pencil and paper mimics addition on a line abacus. The computations may
require the use of addition tables.
To create an addition table for any base, start with the number on the left of a row, fill in
the columns to the right by counting from that number. For example, to get the entries
for 3+1, 3+2, etc in the base-5 table, count from three in base-5. (Since 0 is the additive
identity in every base, there is no reason to include it in the table). The addition table for
base-5 is shown below.
Base-5
+ 1 2 3 4
1 2 3 4 10
2 3 4 10 11
3 4 10 11 12
4 10 11 12 13
The carrying process described with the line abacus has a direct counter part in pencil and
paper calculation.
Example 8.3.3. Compute 134(5) + 23(5) using pencil and paper computation.
Solution. Using the addition table for base-5, we have 4 + 3 = 12, and 3 + 2 = 10, so
1 1
1 3 4
+ 2 3
2 1 2
1 A person who is skilled on an abacus can beat an electronic calculator—you cannot punch numbers into
a calculator fast enough to compete!

8.4. MULTIPLICATION OF BASE-N NUMBERS 103
Notice the connection between Example 8.3.3 with the line abacus. The second step with
the line abacus was to remove five of the counters from the unit line and put an additional
counter on the 10 line. By doing so, we are replacing the “4 + 3” on the unit line with “1”
on the 10 line and“2” on the unit line. That is, we are saying that in base-5, 4 + 3 = 12.
8.4 Multiplication of base-n numbers

To calculate the product of small numbers, think of multiplication as being repeated addi-
tion. For example, to find 3(5) × 4(5) , here’s how it can be done:
0 1 2 3 4 10 11 12 13 14 20 21 22 23
3 1 3 2 3 3 3 4
To perform multiplication requires the use of multiplication tables (and this is true even
with a line abacus). To create a multiplication table, start with the column on the left, and
repeatedly add the appropriate number. For example, to get the row for 3 × n, start with
3 and increase by 3 for each column to the right. In the multiplication table there is really
no need to include 0 or 1, however, some people prefer to include 1 to make it the same size
as the corresponding addition table. You may also take advantage of commutativity—the
table is symmetric with respect to the diagonal, and this will cut your work in half.
Base 5
× 1 2 3 4
1 1 2 3 4
2 2 4 11 13
3 3 11 14 22
4 4 13 22 31
Multiplication of multi-digit numbers

Multiplication of multi-digit numbers follows the same pattern in all bases. We will use the
appropriate base-n tables to aid us. Since you will only be using the tables occasionally, do
not bother to memorize them. (If, however, your life happens to be centered around base
b it would probably be a good idea to memorize the multiplication and addition tables for
base b.)
Example 8.4.1. Compute 234(5) × 4(5) . Do all computations in base-5.

Solution. Taking advantage of the positional system, we have
234×4 = (2×100+3×10+4)×4 = 2×4×100+3×4×10+4×4 = 1300+220+31 = 2101.
The figure below shows how the addition step in Example 8.4.1 is performed on a line
abacus.
31
+
220
+
1300 2101
1000 100 10 1 1000 100 10 1 1000 100 10 1
Let us see how to turn this into the usual format for paper and pencil multiplication. First,
write it as shown in Figure (a) below, then drop the trailing zeroes as in Figure (b), and
then collapse it as in Figure (c). In Figure (c), the numbers 31, 22, and 13 have been written
on a slant like this: 31 , 22 , and 13 .
(a) 234 (b) 234 (c) 234 (d) 234

4 4 4 4
31 31 123 2101
220 22 321
1300 13 2101
2101 2101
The final stage is to carry out the implied additions in Figure (c) as you go along and end
up with Figure (d), which is the usual way multiplication is displayed.
Example 8.4.2. Compute 234(5) × 43(5) . Do all computations in base-5.

Solution. Taking advantage of the positional system, we have
234 × 42 = 234(40 + 2) = 234 × 40 + 234 × 2.
Carrying this out as a tableau we have the following.
234
42
1023 (234 × 2)
21010 (234 × 40)
22033
8.5. SUBTRACTION OF BASE-N NUMBERS 105
Example 8.4.3. Compute 12A(12) × 57(12) . Use the base-12 tables on page 113.
Solution. As mentioned earlier, we use letters to denote the extra digits in base-12, so the
digits are 0, 1, 2, . . ., 7, 8, 9, A, B.
12A
57
87A (12A × 7)
6220 (12A × 50)
6A9A
8.5 Subtraction of base-n numbers

Example 8.5.1. Calculate 42(5) − 4(5) .
Solution. The reason for such a simple example is to illustrate two different ways that
subtraction can be performed. Both involve “borrowing” from the digit on the left.
3
12 3
base+2
4 2 4 2
− 4 − 4
3 3 3 3
The computation on the left is probably closest to the way you learned it. To get the boxed
number 3, you borrow the 1 from the 4, forming the base-5 number 12(5) . You have to find
a number which added to 4(5) will give you 12(5) . You find this number by looking in the
base-5 addition table.
The computation on the right uses what is called subtraction from the base. No matter
how we do the subtraction, we are adding the base to the number 2, and the computation
we are performing is (base + 2) − 4. In the first computation, we visualized this as being
12(5) − 4(5) . With the second method, we do not combine the base and the digit 2, but use
the commutativity of addition and proceed as follows
(base + 2) − 4 = (base − 4) + 2 .
In this case the base is 5, so (base − 4) = 1 and the computation becomes
(base − 4) + 2 = 1 + 2 = 3 .
Both methods can be extended to numbers involving any number of digits. It is an in-
teresting exercise to interpret the two methods using a base-5 line abacus as we did for
addition.
8.6 Switching bases

The following example is solved by switching from base-n to base-10.
Example 8.6.1. Is the number 334212(5) odd or even?

Solution. A number is defined to be even if it is divisible by 2, otherwise it is defined to
be odd. The definition of being odd or even does not depend upon the base. However, our
familiar and automatic test for evenness does depend upon the base and so we will switch
to base-10.
Expanding the number 334212(5) to base-10, we get
334212(5) = 3(55 ) + 3(54 ) + 4(53 ) + 2(52 ) + 1(5) +2

= odd + odd + even + even + odd + even.
So 334212(5) is an odd number.
To switch from base-10 to a different base, we use powers of the base we want to switch to.
The idea is to express the given base-10 number as sums of multiples of the powers of the
base. Earlier, we had shown how to express 221 as a binary number. The next example
asks us to express it as a ternary (base-3) number.
Example 8.6.2. Express 221 as a base-3 number.

Solution. The powers of 3 are
1 3 9 27 81 243 . . .
30 31 32 33 34 35
Proceed as before, this time using the division algorithm to obtain multiples of powers of
three.
221 = 2(81) + 59 = 2(81) + 2(27) + 5

= 2(81) + 2(27) + 1(3) + 2(1)
= 2(34 ) + 2(33 ) + 1(31 ) + 2(30 ),
and so 221(10) = 22012(3)
Another way to do the conversion, is to use repeated division by the base and collect the
remainders as you go along. This is how it would be used to answer Example 8.6.2:
Divide 221 by 3: 221 = 3 × 73 + 2 (R0 = 2)

Divide 73 by 3: 73 = 3 × 24 + 1 (R1 = 1)
Divide 24 by 3: 24 = 3 × 8 (R2 = 0)
Divide 8 by 3: 8=3×2+2 (R4 = 2)
Divide 2 by 3: 2=3×0+2 (R5 = 2)
The base-3 number is R5 R4 R3 R2 R1 R0 , that is, 22012.

8.6. SWITCHING BASES 107
This can be set in a variety of compact forms, such as:

3 221 R2

3 73 R1

3 24 R0

3 8 R2

3 2 R2
This method works to convert a base-10 number to any base.
Example 8.6.3. Express 1251(10) as a base-16 number.
Solution. Using the compact form we have

16 1251 R3

16 78 R12

16 4 R4
0
The remainder of 12 (which is a base-10 number) has to be converted to the base-16 digit
“E”, and then this gives us the answer: 1251(10) = 4E3(16) .
We use the preceding example to explain why this works:

The first division by 16, namely, 16 1251 R3 , tells us that 1251 = 78 · 16 + 3.
78

The next division, 16 78 R12 , tells us that 78 = 4 · 16 + 12. So,
4
1251 = (4 · 16 + 12)16 + 3 = 4 · 162 + 12 · 16 + 3 .
In base-16 notation, the expression on the right is 4·102 +E·10+3, and so 1251(10) = 4E3(16) .

Note that the final division, namely 16 4 R4 , does not give us any more infor-
0
mation.
8.7 Long division

The long division algorithm and the division algorithm are not the same, although the
former is based on the latter. Recall that the division algorithm for positive integers says:
Given positive integers a and d, there are two other integers q and r, with 0 ≤
r < d, such that
a = q · d + r.
The integer q is called the quotient and r is called the remainder.
The division algorithm just tells us that the quotient and remainder exist. It is really a bit
of a stretch to call it an algorithm, because it does not tell us how to find the quotient and
remainder. The long division algorithm, however, does describe how to find them. It is not
clear why it the word long is used, but at least it makes a distinction between the two.
The purpose of this section is to gain an understanding of the long division algorithm and
why it works. The algorithm depends upon the fact that our number system is a positional
system. It works for all bases, but we begin with base-10 numbers simply because we are very
familiar with the base-10 multiplication tables. (By the time children start long division,
they should also be quite used to the base-10 system).
Multiplication can be thought of as being repeated addition. Since division is the operation
that undoes multiplication, then division can be thought of as being repeated subtraction.
Although this does not immediately explain why the long division algorithm works, its serves
as a starting point.
Example 8.7.1. Find the quotient and remainder when 481 is 481
divided by 89 by using repeated subtraction. − 89
392
Solution. Start with 481 and subtract 89 repeatedly until the
− 89
result is less than 89 for the first time. In this case, we subtracted
303
89 five times. leaving us with 36, so
− 89
481 = 5 · 89 + 36. 214
− 89
The quotient is 5 and the remainder is 36. 125
− 89
36
Repeated subtraction is not very efficient, and it is pos-
sible to guess that the quotient is 5. This is accom-
plished by approximating the divisor and dividend by
481
simpler numbers. Note that 89 is approximately 90 and
− 5 · 89 = − 445
481 is approximately 480, so 481 ÷ 89 is approximately
36
480 ÷ 90. But 480 ÷ 90 = 48 ÷ 9 and in this case the
quotient is 5. So, we proceed as shown on the right and
get the same answer as before.
8.7. LONG DIVISION 109
About the only hard and fast rule for estimating the divisor and dividend is that the estimate
for the dividend should have at least as many zeros as does the estimate for the divisor.
Your guess may not always be accurate, but it usually provides enough information so that
you only need one additional estimate.
Example 8.7.2. Find the quotient and remainder when 179981 is divided by 25443 by
estimating the quotient.
Solution.
25443 is approximately 30000 and 179981 is approximately 179981
180000, so the quotient is probably 18 ÷ 3 or 6. Using this − 6 · 25443 = − 152658
estimate, we proceed as shown on the right. 27323
Our guess was wrong. The remainder is too large—it has to be a nonnegative number that
is less than 25443.
We have to revise the quotient estimate upwards. Since
179981
27323 is close to the divisor, it seems likely that the quotient
− 7 · 25443 = − 178101
should be 7. The result is shown on the right, and it shows
1880
that the quotient is 7 and the remainder is 1880.
Even though 6 was an intelligent guess for the quotient, the estimate was not bang on.
Sometimes it will be too high, sometimes too low, but it will at least be close to the quotient.
In the above case, the “remainder” of 27323 was close to the divisor 25443, so we know that
although the estimate of 6 is not accurate, it is within 1 of the correct quotient.
If instead of 30000 we used 20000 as the estimates for 25443
(still using 180000 to estimate 179981), then we would try
18 ÷ 2, or 9, as the quotient. When you try it, you see 179981
that the remainder is negative and numerically almost twice − 9 · 25443 = − 228987
the size of the divisor, so you would have to reduce the −49006
estimated quotient by 2.
When the quotient is more than one digit

The preceding strategies work when the quotient is a single digit. It is not very useful, for
example, when we want to divide 5173 by 6. Repeated subtraction is out of the question,
and it is not clear how we how to get an approximation for the quotient.
The long division algorithm is easier to explain by undoing the multiplication algorithm.
Let us suppose that when 5173 is divided by 6 the quotient is xyz, where x, y and z are
digits. Here xyz denotes a three digit number, not the product x · y · z. The remainder will
be a number r where 0 ≤ r < 6.
If we have done our computations correctly, we should get

5173 = xyz · 6 + r.
Our objective is to find the digits x, y, and z and the number r. The three digit number is
really x · 100 + y · 10 + z, so the previous equation becomes:
5173 = (x · 100 + y · 10 + z) · 6 + r
and expanding it we get
5173 = 600 · x + 60 · y + 6 · z + r
Now, we can find x, y and z very systematically. First, we find x. Think of the previous
equation as being
5173 = 600 · x + r1 , where r1 = 60 · y + 6 · z + r.
But now it is clear what we’re doing: we are dividing

5173
5398 by 600 and getting a quotient of x and a remainder
− 8 · 600 = − 4800
of r1 . We can estimate x because it is approximately
373
the same as 5300 ÷ 600 (i.e. x is approximately 8).
So this tells us that x = 8 and r1 = 373. Since r1 = 60 · y + 6 · z + r, we have
373 = 60 · y + 6 · z + r
Which we write as 373 = 60 · y + r2 , where r2 = 6 · z + r
Now we should divide 373 by 60 to get the quotient

373
y and a remainder r2 . We estimate q to be 370 ÷ 60
− 6 · 60 = − 360
which is approximately 6. The computation is on the
13
right and we get r2 = 13.
Since r2 = 6 · z + r, we have 13 = 6 · z + r, and all that remains is to find z and r by dividing
13 by 6. We get z = 2 and r = 1.
To summarize: We have found that the quotient xyz is 862 and the remainder is 1.
We can gather the steps together (shown on the left below). This is the long division
algorithm, but it is usually presented in the format shown below on the right. In the usual
format, the negative signs are omitted, and digits 8, 6 and 2 are placed above the number
5173.
862
5173 6 5173
− 8×600 = − 4800 4800
373 373
− 6×60 = − 360 360
13 13
− 2×6 = − 12 12
1 1
8.7. LONG DIVISION 111
The approach is the same for all single-digit divisors. For example, when dividing 127116
by 8, you first divide by 80000, then divide the resulting remainder by 8000, and so on
down through 800, 80, and finally 8. In fact the approach is the same when the divisor has
multiple digits. For example, to divide 230073 by 731, our successive divisors will be 73100,
7310, and finally 731. Here is how it would appear in the “long-winded” version and in a
more usual format (note that at each stage, the guess and adjust approach must be used).
314
230073 731 230073
− 3×73100 = − 219300 219300
10773 10773
− 1×7310 = − 7310 7310
3463 3463
− 4×731 = − 2924 2924
539 539
Long division in other bases.

The long division algorithm in other bases follows the same format.
Example 8.7.3. Using the tables below, carry out the long division algorithm to find the
quotient and remainder when 12513(6) is divided by 24(6) .
× 1 2 3 4 5 + 1 2 3 4 5
1 1 2 3 4 5 1 2 3 4 5 10
2 2 4 10 12 14 2 3 4 5 10 11
3 3 10 13 20 23 3 4 5 10 11 12
4 4 12 20 24 32 4 5 10 11 12 13
5 5 14 23 32 41 5 10 11 12 13 14
Solution. In this case the divisor has two digits, 315

but the process is exactly the same as with one 24 12513
digit. With a divisor of 24(6) we subtract multiples 12000 (2400 × 3)
of 2400(6), 240(6) , and 24(6) . The long division 513
algorithm is shown on the right. All computations 240 (240 × 1)
are in base-6. 233
212 (24 × 5)
21
8.8 Exercises
1. Explain, with diagrams, how to use a line abacus to compute 42(5) − 4(5) .
2. Use a line abacus to do the following base-6 computations.
(a) 3423 + 1223. (b) 1223 − 341.
3. Perform the above computations using a pencil and paper.
4. Generate the “base-7” multiplication table.
5. Using the base-6 tables from page 111, compute 532(6) × 42(6) .
6. What are the numbers, in base twelve, that precede the following. (Recall that the
digits in base twelve are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B.)
(a) 1000(12) (b) B0(12) (c) 99A(12) .
7. Using the base-12 tables on page 113 compute AB4(12) × 9A(12) .
8. Using the base-5 multiplication table on page 103, find the remainder when 2340(5) is
divided by 12(5) . Use long division. Do not convert to base-10 to do the calculation.
9. Convert 274(10) to (a) base-4, (b) base-5, and (c) base-12. (Use symbols A and B for
the extra digits for base-12.)
10. Convert each of the following numbers to base-10:

(a) 110111(2) (b)23113(4) (c) DA1F(16) .
11. The base-8 number 40401(8) happens to be a perfect square. Will it also be a perfect
square when it is converted to base-12?
12. (a) Which of the following numbers are even.

(i) 33(5) (ii) 331(5) (iii) 41(5) (iv) 141(5) (v) 10234141(5).
(b) Based on the results from part (a) devise a test for telling whether abcdef (5) is
even, where a, b, c, d, e, and f are the digits of the base-5 number.
13. In each case, find the base b that makes the following equation valid or else explain
why no such base exists.
(a) 54(b) = 213(4). (b) 1110(b) = 124(5). (c) 403(b) = 124(5) .
8.8. EXERCISES 113
14. For a positional number system, which of the following statements are true?
(a) A number n(b) is divisible by 5(10) if and only if its rightmost (units) digit is a 5.
(b) A number n(b) is divisible by 10(b) (that’s one-zero) if and only if it ends in a
zero.
(c) A number n(b) where b ≥ 5(10) is divisible by 5(b) if and only if its rightmost
(units) digit is a 5.
Base-12 Addition Table

+ 1 2 3 4 5 6 7 8 9 A B
1 2 3 4 5 6 7 8 9 A B 10
2 3 4 5 6 7 8 9 A B 10 11
3 4 5 6 7 8 9 A B 10 11 12
4 5 6 7 8 9 A B 10 11 12 13
5 6 7 8 9 A B 10 11 12 13 14
6 7 8 9 A B 10 11 12 13 14 15
7 8 9 A B 10 11 12 13 14 15 16
8 9 A B 10 11 12 13 14 15 16 17
9 A B 10 11 12 13 14 15 16 17 18
A B 10 11 12 13 14 15 16 17 18 19
B 10 11 12 13 14 15 16 17 18 19 1A
Base-12 Multiplication Table
× 1 2 3 4 5 6 7 8 9 A B
1 1 2 3 4 5 6 7 8 9 A B
2 2 4 6 8 A 10 12 14 16 18 1A
3 3 6 9 10 13 16 19 20 23 26 29
4 4 8 10 14 18 20 24 28 30 34 38
5 5 A 13 18 21 26 2B 34 39 42 47
6 6 10 16 20 26 30 36 40 46 50 56
7 7 12 19 24 2B 36 41 48 53 5A 65
8 8 14 20 28 34 40 48 54 60 68 74
9 9 16 23 30 39 46 53 60 69 76 83
A A 18 26 34 42 50 5A 68 76 84 92
B B 1A 29 38 47 56 65 74 83 92 A1
8.8. EXERCISES 115
Appendix A
Proof of the the Linear Divisibility Theorem
The theorem states:
Given positive integers a and b, the smallest positive value of ax + by is d where

d is the greatest common divisor of a and b.
Proof. Let k be the smallest positive value of ax + by. We will prove the theorem in two
steps. First, we will show that k is at least as small as both a and b. Second we will show
that if k > d, then we can find a positive value for ax + by that is smaller than k which
contradicts the definition of k.
Step 1. k ≤ a and k ≤ b: This is clear because with x = 1 and y = 0 we get ax + by = a, so
k ≤ a. Similarly, with x = 0 and y = 1 we get ax + by = a, so k ≤ b.
Step 2. If k > d, then we can find x and y so that ax + by < k:
To see why, let us suppose that x′ and y ′ are integers for which
ax′ + by ′ = k. (8.1)
Now, k must be strictly less that the smaller of a and b. Moreover, k cannot divide both
a and b (because our assumption is that k is larger than the greatest common divisor of a
and b). So let us suppose that k does not divide b. This means that k 6= b and so by step
1, we have k < b. Then by the division algorithm,
b − kq = r, 0 < r < k. (8.2)
Substitute the value of k from equation (8.1) into equation (8.2) to get:
b − (ax′ + by ′ )q = r
This implies that a(−x′ q) + b(1 + y ′ q) = r, which shows that if x = −x′ q and y = 1 − y ′ ,
we get a value of ax + by that is positive but strictly smaller than k.
This finishes the proof.
Proof of the Fundamental Theorem

We start with a lemma:
LemmaIf p, q1 , q2 , . . ., qr are primes and if p | q1 q2 · · · qr , then p is one of the primes q1 , q2 ,
. . ., qr .
Proof. If p6 | q1 , then p and q1 are relatively prime, so p | q2 q3 · · · qr . If p6 | q2 , then p and

q2 are relatively prime, so p | q3 q4 · · · qr . Continuing this process either we may find that
p is one of the primes q1 , . . . qr−1 (in which case we are finished) ore else we arrive at the
conclusion that p | qr . But this can only happen if p = 1 or p = qr , and since p is a prime
we must conclude that p = qr .
Recall the statement of the theorem
If p1 p + 2 · · · pk and q1 q2 · · · qr are two prime factorizations of the same integer,

then, except for the order of the primes, the factorizations are identical.
Proof. We have
p1 p2 · · · pk = q1 q2 · · · qr .
Since p1 divides the left side of the equation, it must also divide the right side of the equation,
so by the Lemma, p1 must be one of the primes q1 , . . ., qk . Remove the factor p1 from both
sides of the equation. The equality is preserved, since this amounts to dividing both sides
by p1 . Repeat this process, until we exhaust all of the prime factors on the left. Then we
must end up cancelling all prims factors on the right. But the process removes primes in
pairs, one member of the pair from each side of the equation. This shows that the two prime
factorizations must have been identical, except for the order of the factors.
The international dateline

If you were positioned in space above the north pole, the earth would be turning counter
clockwise. That’s why we look east in the morning to see the rising sun.
Consider now if you are in Edmonton Alberta 30 minutes before midnight on a Monday. Let
us freeze that instant in time and imaging that you have a line of friends holding hands and
encircling the world. For your friend immediately to your east, the time is 2330 Monday, for
the next one to the east is is also 2330 Monday, and so on. But a few hundred kilometres
down the line to the east we encounter a situation where a person who is standing in the
mountain time zone is holding the hand of a friend who is standing in the central time zone,
and her time is 0030 Tuesday! Continuing this way we eventually discover two friends where
one is standing in the central time zone and holding the hand of someone standing in the
eastern time zone. For the one in the eastern time zone, it is 0130 Tuesday.
8.8. EXERCISES 117
As you continue travelling eastward, the time changes to 0230 Tuesday, then 0330 Tuesday,
and for your friend in Europe its much later in the morning on Tuesday. Further on, its
noon on Tuesday. In Asia its Tuesday evening, and so on.
Now, eventually we will come full circle. But something is wrong. We never cross midnight
again! so it seems that as we travel east, it remains forever Tuesday. But how can that be?
You are in Edmonton and it is Monday! There must be some place where Tuesday turns
back into Monday, and indeed there — its called the international dateline.
The international dateline is a fixed imaginary line running from the north to the south pole
through the pacific ocean and it geographically separates one day from the next. As you
cross the date line travelling from west to east, the day changes back to the previous one.
This stops the apparent contradiction.
Tuesday Monday
A history timeline
The next three pages are a time chart of some of the significant developments of our number
system alongside some selected historical events. As you can see, the development of our
number system was sporadic, and took many centuries to reach its current state. The geo-
graphical progress of so called western mathematics travelled from very ancient civilizations,
to classical Greece, then to the arabic world, and finally back to Europe. It should be men-
tioned that many civilizations had just as interesting mathematics as the Arabic/Western
world, and discovered similar or identical results without contact between the civilizations.
For example, the Chinese and Indian civilizations had independently discovered and proved
Pythagoras’ Theorem. These developments of other civilizations are not included in the
following chart, and it would be interesting to make a similar one for them.
Ancient period (3000 BCE – 1000 BCE)

Plimpton tablet (Pythagorean triples in Great Pyramid at Gizeh. Trojan Wars.
Babylonia). Rhind Papyrus Stonehenge.
Early period (1000 BCE – 500 BCE)
Pythagoras. Homer’s Odyssey. Rise of Persia.
Classical period (500 BCE – 1BCE)
Eratosthenes’ sieve for generating primes. Alexander the Great. Rosetta stone
Euclid writes “The Elements’. Irrational engraved. Caesar assassinated.
numbers discovered.
Classical period (1 CE – 500 CE)
Diophantus. Constantinople founded. Pompeii and
Herculaneum destroyed. Vandals sack Rome.
Medieval Period (500–1500)
500 – 1000
Library at Alexandria burned. Charlemagne.
1000 – 1200
Euclid translated from Arabic to Latin. First universities founded. Vikings reach
Arabs use modern fractional notation (eg 37 ). North America. Death of Omar Khayyam.
First Crusade
1200 – 1300
Fibonacci introduces Arabic-Hindu numerals, Marco Polo. Fourth Crusade. Magna Carta
suggests the use of zero and negative signed. Inquisition begins. Spectacles
numbers. invented. First mechanical clock.
8.8. EXERCISES 119
1300 – 1450
Decimal notation used by Arabic Chaucer. Hundred year’s war. Black Death
mathematicians. Percent symbol (%) in Europe. Witch hunts begin. Death of Joan
introduced of Arc. Gutenberg invents his printing press.
Renaissance Period (1450–1600)
1450 – 1500
Positive and negative symbols (+ and −) voyages of Columbus and da Gama
used for surpluses and deficits
1500 – 1550
Euclid translated into most languages. Copernicus dies. Martin Luther’s 95 Theses.
Positive and negative symbols used to denote Da Vinci paints the Mona Lisa. Michelangelo
operations. paints the ceiling of the Sistine chapel.
Protestant reformation. Watch invented.
1550 – 1600
Zero and negative numbers used for double Growth of the merchant class and
entry bookkeeping. Equality (=) symbol international trade. Gregorian (present day)
used for the first time. Complex numbers. calendar introduced throughout Roman
Symbols for inequality (>, <). Catholic world. Elizabeth I. Shakespeare.
Magellan circumnavigates the globe.
Enlightenment Period (1600 – 1800)
1600 – 1650
Modern decimal notation introduced by Galileo imprisoned. African slaves imported
Napier. Introduction of multiplication to North America. Descartes.
symbols (× and ·) and division division
symbol (÷). Exponentiation notation (eg 35 ).
1650 – 1700
Rembrandt. Rubens. Louvre museum.
Milton’s Paradise Lost. Newton and gravity.
Plague in London. Salem witch hunts end.
1700 – 1750
The symbols for pi (π) and base of natural Kingdom of Great Britain formed. Louis
logarithm (e) introduced. Symbols for ‘not XIV dies.
equal’ (6=) etc. a/b used for fractional
notation.
1750 – 1800
Mozart. French Revolution. Plains of
Abraham. American Declaration of
independence. Cook’s voyages to British
Columbia. Rosetta Stone found.
Modern Period (1800-1900)

1800 – 1850
Napoleon. Britain abolishes slavery. British
Empire in full swing. Electromagnetism
discovered. First steam. First steamships
cross Atlantic.
1850 – 1900
First use of modern long division notation. Darwin’s “Origin of Species”. Marx’s “Das
Conventions established for order of Kapital”. Telegraph. Telephone. Internal
precedence of arithmetic operations. First combustion engine. Wireless telegraphy.
rigorous definition of real numbers.

160 Online Text Book

Uploaded by

Copyright:

Available Formats

160 Online Text Book

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

160 Online Text Book

Uploaded by

Copyright:

Available Formats

Contents

2 Numbers and operations 11

3 Introduction to Number Theory 25

3.4 Answers to the questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4 Common multiples and divisors 39

5 Fractions, decimals, and percentages 53

7 Linear Diophantine Equations 81

7.2 The homogeneous case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

1.2 Shunting trains

1.3 River crossings

Getting an army across a river. During the Turkish stampede in Thrace, a

1.4 Scales and balances

2 Numbers and operations

The natural numbers are the numbers 1, 2, 3, . . . .

2.2 The basic arithmetic operations

A binary operation is a mathematical operation that applies to two things to produce

2.2.1 The trichotomy law

The trichotomy law.

Given two real numbers a and b, either a > b, a = b, or a < b.

1. Is set of numbers we are dealing with closed under the operation?

2. Is the operation commutative or noncommutative?

2.2.3 Commutativity and associativity

A binary operation “◦” is commutative if a ◦ b = b ◦ a .

Question 2.2.2. Is there an associative law of addition for four numbers?

1. Functions are evaluated first.

Question 2.2.4. Evaluate each of the following expressions

2.2.4 The distributive law

Multiplication distributes over addition: a(b + c) = ab + ac.

2.2.5 Identity elements and inverses

Theorem 2.2.5. a · 0 = 0 for every number a.

Proof. We begin by using the fact that 0 + 0 = 0:

a(0) = a(0 + 0) (definition of 0).

a(0) + x = (a(0) + a(0)) + x

This completes the proof.

2.2.6 The cancellation laws

The cancellation laws. If a, x and y are real numbers, then

a+x=a+y =⇒ x = y, for all a.

(a) In the set of integers, what is the additive inverse of 0?

(b) What members of the set of rationals have multiplicative inverses?

2.2.7 The monotone laws

2.3 Those mysterious negative numbers

x + (−1)x = (1)x + (−1)x, (1 is the multiplicative identity)

2.4 Answers to the questions

3. An archaeologist has commissioned you to settle an argument about some printed

3 Introduction to Number Theory

1. Change the state of all of the lockers.

3.1 Multiples and divisors

If n can be obtained from an integer d by multiplying d by another integer, we say that

The following statements all mean the same thing:

Question 3.1.2. What integers divide all other integers.?

Question 3.1.3. What integer is a multiple of every positive integer?

Proof. We will prove statement 3 and leave the rest as exercises.

Since n and m are integers, so is n − m, so we have shown what we wanted.

(a) If x | 17 then x | 34.

Example 3.2.3. Given that 3x is divisible by 12, explain why x is divisible by 4.

3.2.1 Quotient and remainder

dividend = quotient · divisor + remainder

For example, when we divide 895 by 46, we write 895 = 19 · 46 + 21.

When an integer a is divided by a positive integer d, the remainder is the smallest

−54 = (−7)7 − 5, (q = −7 and r = −5).