Diophantine Equations Project

1. Define what’s meant by a Diophantine equation. (You might want to give a little background on Diophantus – see http://www.andrews.edu/~calkins/math/biograph/biodioph.htm for example.)

2. Explain how Diophantine equations are related to finding lattice points on lines.

3. Explain how the question “does the rth row of the multiplication table mod N contain a number k” leads to a Diophantine equation.

4. Theorem: The Diophantine equation ax + by = c has a solution if, and only if gcd(a,b) divides c. Explain why this is true by showing that

a) if the equation has a solution, then gcd(a,b) must divide c and,

b) if gcd(a,b) does divide c then there is a solution to ax + by = c

Note: part b is explained in the class handout. To show part a, note that anything that divides the left-hand side must divide the right-hand side.

5. If (x₀ , y₀) is a particular solution to the Diophantine equation ax + by = c, explain how to find all solutions using the “staircase” method. Include a diagram for clarity (it can be hand drawn).

6. Give some interesting examples (see me if necessary) of Diophantine problems, together with your complete solutions.

7. (Not Necessary: for maximum credit): Write a MatLab program (m-file) that inputs the coefficients a ,b, c of the Diophantine equation, then either reports there is no solution, or prints out the general solution (for example, prints out something like: x = 31 + 5k and y = 7 – 9k). You will want to use the MatLab function: [G, C, D] = gcd(a,b), where G becomes the gcd(a,b), and C, D are numbers such that G = gcd(a,b) = aC + bD. So, for example:

>> [G,C,D ] = gcd(21,56)

G =

7

C =

3

D =

-1