Math 5336 Number Theory                                                       Dr. Cordero

Class activities for September 30, 2002

Topic: Diophantine Equations

1.  Discuss homework from last time.

8. Practice: §2.2 p.25 # 7, 14

11. Use the Extended Euclidean Algorithm to find integers x and y such that:

·        141x+120y=3

·        243x+41y=1

·        243x+41y=6

·        1721x+378y=7

12. The Stamps Problem

Suppose you have an unlimited supply of 6 -cents stamps and 11- cents stamps.

What amounts of postage can you make with these stamps?

·        Solve the Stamps problem.

·        What if the stamps were of 6-cents and 9-cents?

·        What if the stamps were of 6-cents and 10-cents?

2. The Money Problem

Suppose that Cathy and Jenai  each have an unlimited supply of money .J

However, suppose this money exists only as \$6 coins and \$11 coins. Clearly Cathy can give Jenai \$6, for example, by simply giving her a \$6 coin. Also, Jenai can give Cathy \$5 by giving her a, \$11 coin and collecting a \$6 coin as “change”. What other amounts are possible? Consider the following three questions:

a.      What amounts of money can be exchanged using only \$6 and \$11 coins?

b.      What amounts of money can be exchanged using only \$6 and \$9 coins?

c.       What amounts of money can be exchanged using only \$6 and \$10 coins?

3. The Diophantine Equation .

a. What does it mean to solve a linear Diophantine equation of the form ax+by=c?

b. How many years did Diophantus live? Figure it out using the following information about his life found in a publication from the fifth or sixth century.

“This tomb holds Diophantus. Ah, what a marvel! And the tomb tells scientifically the measure of his life. God vouchsafed that he should be a boy for the sixth part of his life; when a twelfth was added, his cheeks acquired a beard; He kindled for him the light of marriage after a seventh, and in the fifth year after his marriage He granted him a son. Alas! Late-begotten and miserable child, when he had reached the measure of half his father’s life, the chill grave took him. After consoling his grief by this science of numbers for four years, he reached the end of his life.”

c.Prove the following:

Theorem: The linear Diophantine equation ax+by=c admits a solution if and only if d|c where d=gcd(a, b).

d.      (Homework) Study the proof in your book (pp: 34-35) of the following:

Theorem: If  ,  is any particular solution to the linear Diophantine equation ax+by=c, then all other solutions are given by

where  t is an arbitrary integer.

e.       Prove the following corollary:

Corollary: If gcd(a, b)=1 and , is a solution to the linear Diophantine equation ax+by=c, then all other solutions are of the form

where t is an arbitrary integer.

f.        (a). Find a solution to 172x+20y=1000.

(b). Give the general form of all the solutions.

(c). Find a solution (if it exists) with positive integers.

g.      Study Example 2.5  and The Hundred Fowls Problem on pp. 36-37. Then do Problems # 6 a, 6b, 7, 8, 9b, 9d, 9e.

Problems # 1, 2, 3, 6c, 9a, 9c.