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.

h. Additional practice:

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