May 1997 Presentation Topic (continued)

This proves that, for any positive integer *n*, there are prime
numbers which are greater than *n*. Therefore, there are infinitely
many prime numbers.

**Solution to Question 2**.
Let the line segment be *PQ*. Use the standard ruler-and-compass
technique for constructing perpendiculars (found in most textbooks)
to draw a perpendicular line *L* to *PQ* through *Q*. With the centre
of the compass at *Q* and its tip at *P*, draw a circle, passing through
*L* at point *R*. Now *PQ* and *QR* are two adjacent sides of a square
of side length 1. Draw the line segment *PR*; this is the desired
diagonal, whose length is .

This length is not a rational multiple of the original
side length. In other words, there is no rational number *a*/*b* which equals
. Here are two proofs of this (each proof uses that fact that,
if , then the equation would have
to be satisfied):

Proof #1 is a little more elegant, but it requires that one first prove the theorem that all positive integers can be written uniquely (except for the order) as a product of positive prime numbers.Proof #1: Letkbe the number of times 2 occurs as a factor ofa, andlthe number of times 2 occurs as a factor ofb. Then 2 occurs 2ktimes (an even number) as a factor of , but 2l+ 1 times (an odd number) as a factor of of . No number is both even and odd, so the numbers and must be different (since 2 appears as a factor a different number of times).Therefore, no rational number

a/bcan equal .

Proof #2: Writea/bin lowest terms, in whichaandbhave no common factors. This means thataandbare not both even.However, if , then

awould have to be even. That means we can writea= 2kfor some integerk. The equation now becomes , so , which impliesbwould have to be even as well, contradicting the fact thata/bis in lowest terms.Therefore, no rational number

a/bcan equal .

**Solution to Question 3**.
For any positive rational number *r*, *r*/2 is a smaller one. Therefore,
there is no smallest positive rational number.

**Solution to Question 4**.
There are many ways to do this. One way is to compare positive rational
numbers by asking, for each number *r*,

What is the largest integer needed to writeAnswering this question gives a positive integerrin the forma/bwhereaandbare positive integers?

Now we can compare positive rational numbers *r* and *s*
by comparing *N*(*r*) to *N*(*s*)
(and when there is a tie, i.e. when *N*(*r*)=*N*(*s*), use the usual ordering).
For example: 1/2 comes before 1/4 in this new ordering (because
*N*(1/2) = 2 < 4 = *N*(1/4)). Also 2/3 comes before 3 (because
*N*(2/3) = 3 = *N*(3/1), and since there is a tie, we use the usual
ordering, in which 2/3 < 3).

In this ordering 1 is the smallest positive rational number (every other number must have an integer >1 in either numerator or denominator).

In fact, any non-empty collection of positive rational numbers
has a smallest number in this new ordering.
To prove this,
look at all the positive integers *N*(*r*) that correspond to the
numbers *r* in the collection. Pick the smallest one of these; call it *N*.
There are only
finitely many positive rational numbers *r* for which *N*(*r*)=*N* (for there
are only finitely many fractions you can build out of the numbers 1
through *N*), so there are only finitely many numbers *r* in the collection
for which *N*(*r*)=*N*. An ordered, finite set always has a smallest
element, so there is a smallest number *r* for which *N*(*r*)=*N*, and this
number *r* will be the smallest in the entire collection.

**Solution to Question 5**.
There are many arguments that can be used to try to convince someone
that 0.999. . . = 1. One common one is to note that
0.333. . . = 1/3, and multiplying both sides by 3 gives you
0.999. . . = 3/3 = 1.
However, none of these arguments can be considered a mathematical
proof until two fundamental questions are answered: (1) What *is*
a real number? (2) What does an infinite decimal like 0.999. . .
actually *mean*?

We discuss these questions briefly
in the **Concepts**
section, concluding that a real number
can be defined to be a "Cauchy sequence" of rational numbers, and two
such sequences and
define the same real number if the
distance
between corresponding terms converges to zero.

The infinite decimal 0.999. . . means the real number defined by the sequence of finite decimals 0, 0.9, 0.99, 0.999, . . . , while 1.000. . . means the sequence 1, 1.0, 1.00, 1.000, . . . (which is the constant sequence 1, 1, 1, . . . ). These two sequences describe the same real number because the differences between corresponding terms are 1-0 = 1, 1-0.9 = 0.1, 1-0.99 = 0.01, 1-0.999 = 0.001, . . . and this sequence is converging to zero.

However, even though the two decimals 1.000. . . and 0.999. . .
each represent the same real number 1, there are no other decimals
which do. In fact, the *only* time in which two decimals represent
the same real number is when, if you write them as a sequence of digits
making sure that their decimal
points line up, they are of the form

wheresA000. . . andsB999. . .

Here's a proof that this is the only case in which different decimals
give rise to the same number. Write the decimals as above (lining up
their decimal points). Skip over any beginning digits that are in common
to both (call this digit sequence "*s*") until you reach the first
digit that is different. Let *A* and *B* be the
differing digits, with *A *> *B*.

The first infinite decimal describes a sequence whose terms
from some point on are finite decimals of the form *sA*, *sAX*, *sAXY*, . . . .
If all the digits after *A* are zeros, these terms are all equal to the
rational number *x* given by the finite decimal *sA*. Otherwise,
at least one subsequent digit *C* is non-zero, and all the terms
from that point on are greater than or equal to the rational number
*x* given by the finite decimal *sA*. . . *C*.

The second infinite decimal describes a sequence whose terms from some point
on are finite
decimals of the form *sB*, *sBP*, *sBPQ*, . . . . If all the subsequent digits
are 9's, these terms are *sB*9, *sB*99, . . . , all of which are less than
the rational number *y* given by the finite decimal *s*(*B*+1).
If at least one subsequent digit *D* is less than 9, then the terms
from some point on are of the form *sB*. . . *D*. . . which are all less
than the rational number *y* given by the finite decimal *sB*. . . (*D*+1).

The difference between corresponding terms is always at least
*x*-*y*, as the term from the first decimal is at least *x* and the term
from the second one is at most *y*.

If *x *> *y*, these differences are always greater than the fixed positive
number *x *- *y* and therefore cannot converge to zero, so the decimals
describe different real numbers. The only time they can describe the same
real number is when *x*=*y*. This
only happens in the case when *x* is given by *sA* (which only happens when
the first decimal is of the form *sA*000. . . ) and *y* is given by *s*(*B*+1)
(which only happens when the second is of the form *sB*999. . . ),
and only when *A*=*B*+1.

**Solution to Question 6**.
Obviously, after each step, under option (A)
Abe's barrel will have many many more coconuts than Bonzo's, and under
option (B) Bonzo's barrel will have many many more coconuts than Abe's.
If these monkeys can only do finitely much work,
it would clearly be to Bonzo's
advantage to choose option (B).

However, things change radically if the monkeys can complete their task (working infinitely fast), assigning each coconut to a final resting place in either barrel A or barrel B:

*Under option (A), each barrel will end up with the same number of
coconuts, while under option (B), barrel A will get all the coconuts
and barrel B will get none.* So it's actually better for Bonzo to choose
option (A)!

Here's why. Under option (A), it is clear that an infinite number of coconuts get placed into each barrel. It is a (strange at first glance, but nevertheless true) fact that any two infinite sets of positive integers are the same size: they can be placed in one-to-one correspondence with each other. In this particular problem, you can set up the correspondence as follows: match the lowest-numbered coconut in A with the lowest one in B, match the second-lowest one in A with the second-lowest one in B, and so on. Every coconut gets matched in this way.

Under option (B), though, things are different. Once a coconut
is placed into barrel A, it is never
removed; that is its final resting place. However, whenever a coconut
(let's say it's number *n*) is placed into barrel B, it will eventually
be removed and put into barrel A. This is because there are
at most *n*-1 smaller-numbered coconuts in B, one of which is removed
during each turn, so after at most *n*-1 turns coconut *n* will
become the smallest-numbered coconut in barrel B
and will be removed on the next turn. Therefore,
when all coconuts are in their
final resting place, Abe will have them all!

**Solution to Question 7**.
In the language of congruences, we say that *a is congruent
to b modulo m*, written (mod *m*),
if *a*-*b* is divisible by *m*.

This problem can be restated as: find a number *x* (the number of cents
John has) which is less than 105 and which satisfies the three congruences

(mod 3),The first congruence means

(mod 5), and

(mod 7).

(mod 5)How do we solve this? We cannot simply divide 2 by 3, since 2/3 is not an integer. However, the theory in question 8 below shows that in arithmetic modulo a prime, one

(mod 5)and now we can divide by 3 to get (mod 5), so

We could solve this by the same procedure as above, but it is easier to note that (mod 7) and therefore

(mod 7).Finally, we rewrite the last congruence as

A procedure for solving systems of simultaneous congruences was known
to the ancient Chinese, and the theorem that guarantees the existence
of a solution (under appropriate conditions on the numbers involved) is
known as the *Chinese Remainder Theorem*.

**Solution to Question 8**.
Let *a* and *b* be integers modulo 7, with *b* non-zero.
We want to show that there is a unique quotient *q* for the division
"*a* divided by *b*". Look at the numbers .

No two of these are equal to each other:
if (in arithmetic modulo 7), that means
7 divides the difference *bx *- *by* (in ordinary arithmetic).
Because 7 is prime, the fact that 7 divides *b*(*x*-*y*) means that
either 7 divides *b* (which it doesn't, since *b* is a number from 1 to 6),
or else 7 divides *x*-*y*. This means *x* and *y* are equal modulo 7.
So, in mod 7 arithmetic, the only time is
when *x*=*y*.
(The same thing is true in arithmetic modulo any prime number).

Therefore, the seven numbers , being seven different members of the set
{0,1,2,3,4,5,6} (which only has seven members), must together
make up the entire set. That means there is exactly one value of *q* for
which , proving that division of *a* by *b* is well defined.

This works in arithmetic modulo any prime number, but not in arithmetic modulo non-primes. For instance, in arithmetic modulo 12, 3 times 4 equals 0, so you cannot divide by 3 (if you could, you could divide both sides by 3 to get 4 = 0, which is not true). However, you can still divide by any non-zero number which is relatively prime to 12.

**Solution to Question 9**.
In the integers modulo 7, , , and .
(The last one can be done easily by noting that (mod 7),
so ).

It appears that (mod 7) for any *a*, and
this is in fact true.

It's clearly true when *a*=0, so let's think about nonzero *a*.

In the integers modulo 7 the sequence
must eventually repeat itself (there are only seven different numbers
available). So there are some two powers which are equal, say
and with *n *> *m*. This means
and we can divide by to deduce that .

We have now shown that some power of *a* equals 1 (modulo 7).
Let *m* be the smallest such exponent, so that
but the *m* numbers are all distinct.

Divide the six numbers 1, 2, 3, 4, 5, 6 into categories
by placing two numbers *b* and *c* into the same category if
for some *k*. (This works because the relationship
just described is a symmetric and
transitive one: if *b *= *a*^*k c* and *c *= *a*^*l d*,
then *b *= *a*^(*k*+*l*)*d*, so if *b* and *c* are to go together and
*c* and *d* are to go together, then *b* and *d* are to go together as
well).

Each category has exactly *m* members, because if *b* is in the category,
then the other members of the category are .
Therefore, if *n* is the number of categories, the product *mn* equals
the total number of numbers we placed into categories: namely, 6.

This proves that *m* is a factor of 6. We know , so
, so , which proves that
(in the integers modulo 7).
This same thing is true in the integers modulo any prime *p*:
(mod *p*) for all *a*.

Go backward to A Sampling of Questions

Go up to Introduction and Contents

Go forward to History and Concepts

Switch to text-only version (no graphics)

Access printed version in PostScript format (requires PostScript printer)

Go to SIMMER Home Page

Go to The Fields Institute Home Page

Go to University of Toronto Mathematics Network
Home Page