Advanced High-School Mathematics

62 CHAPTER 2 Discrete Mathematics

9. Letpbe a prime and show that for all integersh, 1 ≤h≤p−1,
   p

∣∣

∣∣

∣

Ñ

p

h

é

. Conclude that for any integers x and y, the numbers
(x+y)pandxp+yphave the same remainder when divided byp.
10. Show that the converse of Exercise 9 is also true. Namely, if n
is a positive integer such that for all integersh, 1 ≤h≤ n−1,
n

∣∣

∣∣

∣

Ñ

n

h

é

, thenn is prime. (Hint: Assume thatn isn’t prime, and

letpbe a prime divisor ofn. Show that ifpr is the highest power

ofpdividingn, thenpr−^1 is the highest power ofpdividing

Än

p

ä

.)

11. Assume thatn, mare positive integers andkis an exponent such
    thatn|(mk−1). Show that for any non-negative integerh,
    n|(mhk−1).


12. Assume that you have two measuring vessels, one with a capacity
    ofa liters and one of a capacity ofbliters. For the sake of speci-
    ficity, assume that we have an 8-liter vessel and a 5-liter vessel.
    Using these vessels we may dip into a river and measure out cer-
    tain amounts of water. For example, if I wish to measure exactly
    3 liters of water I could fill the 8-liter vessel, and then from this
    fill the 5-liter vessel; what remains in the 8-liter vessel is exactly 3
    liters of water.
    (a) Using the 8-liter vessel and 5-liter vessel, explain how to mea-
    sure out exactly 1 liter of water.
    (b) Assume that we return to the general situation, viz., where
    we have analiter vessel and a b-liter vessel. Explain how to
    measure out exactlydliters of water, whered= gcd(a,b).


13. Letaandbbe integers, both relatively prime to the positive integer
    n. Show thatabis also relatively prime ton.


14. Here’s a cute application of the Euclidean Algorithm. Let aand
    bbe positive integers and letqk, rk, k= 1, 2 ,...,be the sequence
    of integers determined as in the Euclidean Algorithm (page 59).
    Assume thatrmis the first zero remainder. Then^4

(^4) The expression given is often called asimple finite continued fraction.