Advanced High-School Mathematics

78 CHAPTER 2 Discrete Mathematics

5. Show that there exist unique positive integers xandy satisfying
   x^2 + 84x+ 2008 =y^2. Find these integers.^11


6. For each positive integern, define

H(n) = 1 +

1

2

+

1

3

+···+

1

n

.

Prove that ifn≥2, thenH(n) isnot

an integer.

In perfect harmony | plus.maths.org 9/8/10 9:06 PM

file:///Users/davidsurowski/Desktop/harmonic.webarchive Page 3 of 6

Missing the cracks

Suppose that. Choose an integer such that. Then Consider the

lowest common multiple of integer. Now multiply both sides of the equation by this number, to get. This number will be of the form , where is an odd

Now, when multiplied out, all the terms on the left will be integers, except one:

is not an integer, since that is not an integer. is odd. So the left hand side is not an integer, and hence neither is the right hand side. That means

Record rainfalls

How often are weather records broken? The harmonic series gives the answer.

Suppose we have a list of rainfall figures for a hundred years. How many record-breaking falls ofrain do you expect have taken place over that period? We assume that the rainfall figures are

random, in the sense that the amount of rain in any one year has no influence on the rainfall inany subsequent year.

The first year was undoubtedly a record year. In the second year, the rain could equally likelyhave been more than, or less than, the rainfall of the first year. So there is a probability of

that the second year was a record year. The expected number of record years in the first twoyears of record-keeping is therefore. Go on to the third year. The probability is 1/3 that

the third observation is higher than the first two, so the expected number of record rainfalls inthree years is. Continuing this line of reasoning leads to the conclusion that the

expected number of records in the list of observations is

What was your guess for the number of record rainfalls in a hundred years of keeping rainfall figures? If it was 5, you werenearly right, for the sum of the first hundred terms of the harmonic series is 5.19.

Even after a record-breaking rainfall, nobody will deny that the record will be broken some time in the future - perhaps in thevery next year. The number of record years in an infinity of observations is clearly infinity. There we have an intuitive reason

(Hint: Letkbe the largest integer such that 2k≤n, and letMbe

the least common multiple of the integers 1, 2 , ..., 2 k− 1 ,

2 k+ 1, ..., n. What happens when you multiplyH(n) byM?)

7. Here’s an interesting system of “integers” for which the Funda-
   mental Theorem of Arithmetic fails. Define the set

Z[

√

−5] = {a+b

√

− 5 |a, b∈Z}.

Define primes as on page 60,^12 and show that

3 ·7 = (1 + 2

√

−5)(1− 2

√

−5) = (4 +

√

−5)(4−

√

−5)

give three distinct prime factorizations of 21. In otherwords, the

uniqueness aspect of the Fundamental Theorem of Arithmetic fails

to hold in this case.

8. In this exercise we outline another proof that there exist infinitely
   many primes. To this end, define the n-thFermat numberFn,
   by settingFn= 2^2
   n
   
   
   • 1, n= 0, 1 , 2 ,...,.
   
   
   
   

(a) Show that

n∏− 1

m=0

=Fn− 2 , n= 1, 2 ,...(Induction!)

(b) Conclude from part (a) that the Fermat numbersFm andFn

are relatively prime wheneverm 6 =n.

(^11) Essentially Problem #4 from the 2008 American Invitational Mathematics Examination.
(^12) Actually, in more advanced treatments, one distinguishes between the notion of a “prime” and
the notion of an “irreducible,” with the latter being defined more or less as on page 60 (I’m trying
to avoid a systematic discussion of “units”). On the other hand, a numberpis calledprimeif
wheneverp|ab, thenp|aorp|b. In the above exercise the numbers given are all irreducibles but,
of course, aren’t prime.