Navigation Panel: Previous | Up | Forward | Graphical Version | PostScript version | SIMMER Home Page | Fields Institute Home | U of T Math Network Home

SIMMER

May 1997 Presentation Topic (continued)

# Solutions

Solution to Question 1. Every non-zero integer has a prime factor. For any positive integer n, the number n! is divisible by all the positive integers from 1 to n inclusive, and so the number 1 + n! is not divisible by any of them. Therefore, all of the prime factors of 1 + n! must be greater than n.

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 sqrt(2).

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

Proof #1: Let k be the number of times 2 occurs as a factor of a, and l the number of times 2 occurs as a factor of b. Then 2 occurs 2k times (an even number) as a factor of a^2, but 2l + 1 times (an odd number) as a factor of of 2 b^2. No number is both even and odd, so the numbers a^2 and 2 b^2 must be different (since 2 appears as a factor a different number of times).

Therefore, no rational number a/b can equal sqrt(2).

Proof #2: Write a/b in lowest terms, in which a and b have no common factors. This means that a and b are not both even.

However, if a^2 = 2 b^2, then a would have to be even. That means we can write a = 2k for some integer k. The equation now becomes 4 k^2 = 2 b^2, so 2 k^2 = b^2, which implies b would have to be even as well, contradicting the fact that a/b is in lowest terms.

Therefore, no rational number a/b can equal sqrt(2).

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.

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 write r in the form a/b where a and b are positive integers?
Answering this question gives a positive integer N(r) for each positive rational number r. For example, N(1/4)=4 since 1/4 can't be written using anything smaller than a 4, but N(2/4) = 2 since 2/4 can be written as 1/2 which uses nothing larger than a 2.

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 a(1), a(2), ... and b(1), b(2), ... define the same real number if the distance |a(n) - b(n)| 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

sA000... and
sB999...
where s stands for a sequence of digits that is in common to the two numbers, B is a digit from 0 to 8, and A = B+1 (in our example, s is empty, A=1, and B=0). The decimal point has been omitted from the notation.

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 sB9, sB99, ..., 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 sA000...) and y is given by s(B+1) (which only happens when the second is of the form sB999...), 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 a = b (mod m), if a-b is divisible by m. (The congruence symbol is actually an equals sign with three lines, as shown in the graphical version, but that symbol is not available in this text-only version, so we have used an ordinary = sign instead).

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

x = 2 (mod 3),
x = 4 (mod 5), and
x = 5 (mod 7).
The first congruence means x = 3k + 2 for some integer k. Plugging this into the second congruence yields 3k + 2 = 4 (mod 5), and therefore
3k = 4-2 = 2 (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 can always divide by any non-zero number. So there is some number k for which 3k = 2 (mod 5). That means that if we keep adding 5 to the right-hand side 2 (which doesn't affect the congruence), we will eventually reach a multiple of 3. Let's do it, adding 5 until we get a multiple of 3:
3k = 2 = 7 = 12 (mod 5)
and now we can divide by 3 to get k = 4 (mod 5), so k = 5l + 4 for some integer l, and therefore x = 3k + 2 = 15l + 14. Plugging this into the final congruence, we obtain that 15l + 14 = 5 (mod 7), so 15l = -9 (mod 7).

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

l = 15l = -9 = 5 (mod 7).
Finally, we rewrite the last congruence as l = 7m + 5 for some integer m, and plug this in to the formula x = 15l + 14 to obtain x = 105m + 89. We know 0 <= x < 105 so m must be zero, and therefore x=89. John has 89 cents in his pocket.

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 b x 0, b x 1, ..., b x 6.

No two of these are equal to each other: if b x x = b x y (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 b x x = b x y is when x=y. (The same thing is true in arithmetic modulo any prime number).

Therefore, the seven numbers b x 0, b x 1, ..., b x 6, 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 b x q = a, 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, 2^7 = 2, 3^7 = 3, and 5^7 = 5. (The last one can be done easily by noting that 5 = -2 (mod 7), so 5^7 = (-1)^7 2^7 = -2 = 5).

It appears that a^7 = a (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 a, a^2, a^3, ... must eventually repeat itself (there are only seven different numbers available). So there are some two powers which are equal, say a^n and a^m with n > m. This means a^m(a^(n-m)-1) = 0 and we can divide by a^m to deduce that a^(n-m)-1 = 0.

We have now shown that some power of a equals 1 (modulo 7). Let m be the smallest such exponent, so that a^m=1 but the m numbers 1, a, a^2, ..., a^(m-1) 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 b = a^k c 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 ba, ba^2, ..., ba^(m-1). 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 a^m = 1, so a^(mn) = 1^n = 1, so a^6 = 1, which proves that a^7 = a (in the integers modulo 7). This same thing is true in the integers modulo any prime p: a^p = a (mod p) for all a.