Module 4 Chapter 6: Diophantine Equations

Module 4 – Chapter 6: Diophantine Equations

Pages 65 – 77

This chapter is slightly mis-named. In reality we’ll be looking at lots and lots of equation, and what we’ll be searching for are Diophantine SOLUTIONS to them.

Which is to say, integers that make the equation true. We’re not interested in fractions or irrational solutions, only integers. Integers that make the equation true are called Diophantine Solutions. And equations that have some integer solutions are called Diophantine Equations.

For example:3x = 5is an equation and the solution is

So this is NOT an acceptable answer on our quest. The equation is not Diophantine, then.

Here’s another example:

Does this equation have Diophantine solutions?

Yes!

The x-intercept (3, 0) is a Diophantine solution. So is the y-intercept (0, 2).

It has non-Diophantine solutions, too. If x = 1 then y = 4/3. Not one we want.

The solutions go neatly into a set format.

Since our equations will be polynomials with rational coefficients, so I know that ALL solutions are algebraic numbers. I’ll start with that set:

Let’s look a little bit harder at the solutions.

Did you know that the line drawn in the Cartesian plane is the set of all solutions?

Let’s look more closely at that line: is the equation re-written and ready to graph. I used “Math GV” a nice free download grapher for this picture.

The line is ALL of the solutions. Let’s pick out the Diophantine solutions:

(3, 0) (0, 2) (6, −2) (− 3, 4)…these are just a few of the ones we want to look at.

Solutions like are NOT solutions we want. If we want to graph these, we’d graph points on a dotted line.

Or we could say we want all numbers in [ 0 ] mod 3 as our x-values. Any multiple of 3 for x will generate a Diophantine solution:

Another, set-style representation is

Now the last half of this Module, we’ll focus exclusively on lines.

For right now, let’s expand into a very famous equation and look at it’s Diophantine solutions.

Do you recognize this very famous equation?

When applied to right triangles, we call it The Pythagorean Theorem.

If x and y are the legs and z is the hypotenuse, then the formula always “works”.

So now if we have an isosceles right triangle with side length 1, the hypotenuse is . This situation is definitely NOT what we’re after. is an algebraic number that is A solution but it’s not a Diophantine solution.

There is a nice scalene right triangle that is Diophantine: 3 – 4 – 5. (9 + 16 = 25).

All of the Diophantine solutions for this application are called “Pythagorean Triples”. They’re a very famous set in mathematics.

So, we want to find more of these!

Luckily there’s a handy theorem that we can use to create as many of these as we want.

Here’s what the theorem says:

First, pick two generators: m and n that are natural numbers.

The generators are NOT the leg lengths, they are used with formulas to create the leg lengths.

Here are the Rules for Generators of Pythagorean Triples.

• They’re both natural numbers and mn.

• One is even and the other is odd.

• They are relatively prime (i.e. (m, n) = 1)

Once we’ve got the generators, we’re ready for the formulas:

• x = leg 1 =

• y = leg 2 =

• z = hypotenuse =

Now let’s apply these rules:

Let’s pick m = 2 and n = 1.

• They’re both natural numbers and mn.

• One is even and the other is odd.

• They are relatively prime (i.e. (2, 1) = 1)

x= 4 – 1 =3

y = 2(2)(1) = 4

z = 4 + 1 = 5

Our generators {2, 1} give us the 3 – 4 – 5 right triangle.

Let’s pick 2 different generators {5, 4}

x = 25 – 16 = 9

y = 2(5)(4) = 40

z = 25 + 16 = 41

Do these work? Let’s check:

Note, too, that this new Pythagorean Triple is NOT similar to the earlier example. These side lengths are not multiples of the {3, 4, 5} triangle.

So DIFFERENT generators give us totally DIFFERENT Pythagorean Triples each time we use them.

Popper 07, Question 1

Pythagorean Triples are Diophantine solutions to

ATrue

BFalse

On another note, here’s a geometric aside to Pythagorean Triples!

Associated with EVERY triangle is the incircle. This is a circle that is on the interior of a triangle and it is tangent (shares one point) to each side of the triangle. The interesting thing about incircles is that they stay inside the triangle no matter how you deform the triangle.

Here are two triangles with their incircles. I built one in Sketchpad and then dragged the vertices to get the others.

Now, Pythagorean triples are special triangles, of course, but they are still in the set of all triangles so each has an incircle. The amazing thing about this fact is that you can calculate the radius of the incircle from the generators of the triple.

r = n(m  n)p. 68

Who would have guessed at that!

Here’s a summary of what we’ve got on Pythagorean triples so far:

• Pythagorean triples are a proper subset of scalene right triangles.

• EACH triple is a Diophantine solution to the equation.

• Each triple that is not similar to another triple is generated by a pair of generators that follow rules given by a theorem

• They’re both natural numbers and mn.
• One is even and the other is odd.
• They are relatively prime (i.e. (m, n) = 1)
• The triangle sides come from these formulas:

• x = leg 1 =
• y = leg 2 =
• z = hypotenuse =

• The radius of the triple’s incircle is r = n(m  n).

Putting it together:

Let’s use m = 4 and n = 3

x = 16 – 9 = 7y = 2(4)(3) = 24z = 16 + 9 = 25

r = 3 (4 – 3) = 3

note that the generators do not appear in the equation!

Popper 07, Question 2

(6, 5, 21) is a Pythagorean Triple with generators 3 and 2

ATrue

BFalse

One common error is to assume that if the hypotenuse is a natural number, then the leg lengths are, too. Let’s look at an example of this.

Here’s a right triangle with a hypotenuse of 6 cm. It is quite common for students to get all excited and think that the leg lengths are natural numbers and that they’ve got a Pythagorean triple in the problem. But they’re wrong with this case!

We’re working with:

Suppose x = 1, then y =

Suppose x = 2, then y =

Suppose x = 3, then y =

Suppose x = 4, then y =

Suppose x = 5, then y =

And if we suppose x = 6, then y = 0.

Do NOT make assumptions about things mathematical without doing some checking ok?

The perimeter and area of this triangle are irrational! Not nice natural numbers at all.

Popper 07, Question 3

Given

The Diophantine solutions to this equation will be a proper subset of all the solutions.

A.True

B.False

Here’s another surprising tie-in to Pythagorean triples on page 69.

The question is simple enough

How many non-collinear points in the plane can be spaced at integer distances from one another?

(and have NICE, nice point coordinates…they meant to say this!)

The answer is startling.

Now “non-collinear” means not all on the same line so you’re going to have to work with triangles in answering the question.

You might be tempted to say that an isosceles right triangle with leg length one will work.

Unfortunately, that hypotenuse is .

It’s not a Diophantine solution to the question.

You might try a right triangle with legs, 1 and 2…but that hypotenuse is.

You might try a triangle that is equilateral with all side lengths 1. That sounds good until you look at the point coordinates of the apex angle.

This is one answer. And all similar triangles to this will work, too.

But look at those point coordinates!

Ugly as homemade sin, as my grandmother used to say.

So that’s 3 of them. To get 4 of them just add a point to the left one away from the apex, though 6 of them is easy.

You can continue to work with this and get numbers of points that are integer distances apart but with really ugly point coordinates.

Or for a second answer you might remember Pythagorean triple right triangles:

These are all integer distances apart. All nice point coordinates if we put the origin at the right angle.

Perfect! Here’s 3 points, integer distances.

Now the authors come up with a clever way to re-use this triangle and create similar right triangles that maintain the nice coordinates and natural number distances for ANY natural number of points.

Let’s look at how this would work for 4 points.

I know that (3, 4, 5) and (5, 12, 13) are 2 Pythagorean triples.

By careful multiplication I can come up with a pair of nested similar triangles that have natural number distances among 4 points.

The first multiplication is 3(5) so AD is now 15 units long. Then I multiply the rest of the

3 – 4 – 5 triangle by 5. Now it’s (15, 20, 25). Then, and this is the clever part, I multiply the other (5, 12, 13) triangle by 3 … I’ve already multiplied 5(3) so AD will be a side for BOTH triangles. Then 3(12) is AC and 3(13) is DC (a new hypotenuse).

To get 5 points that are integer numbers apart, I’ll get the second round of nested triangles inside a triangle similar to a (7, 24, 25) triangle. I’ll change point D to point F by multiplying the old (3, 4, 5) triangle by both 5 and, now, 7. I’ll multiply the old (5, 12, 13) by both 3 and 7, and I’ll multiply the new enclosing triangle (7, 24, 25) by (3)(5).

Now in the homework, show the changes to get 6 points at integer distances from one another…do it so clearly that the GRADER gets it, ok!

In another shift, the authors move to discuss a new equation on page 72.

It turns out that this nice equation has NO Diophantine solutions whatsoever.

And looking at another interesting equation on page 75:.

This is a polynomial with rational coefficients so all solutions will be algebraic numbers. There will be NO transcendental numbers in the solution set.

And the thing that is interesting with this equation is that there are EXACTLY TWO Diophantine solutions: (0, 1) and (1, 0). All other solutions have 1 or 2 irrational numbers in the point pair that is the solution. Imagine that.

In fact, solutions to the general equation:

were given by the British mathematician Dr. Wiley in the 1990’s. His solution was predicted but not proved by our old friend Fermat.

Now

On to Linear Diophantine Equations.

We’ll abandon all equations with powers of x and y higher than 1. And we’ll call them LDE’s.

All of our equations will look like

Theorem 1

An LDE has Diophantine solutions whever the GCD of (A, B) divides C.

Example:

(10, 15) = 55 does NOT divide 6this equation has NO Diophantine Solutions

Example:

(1, 5) = 1

1 divides 15This equation HAS Diophantine solutions.

Example

(3, 4) = 11 divides 11. This equation HAS Diophantine solutions.

Popper 7, Question 4

Given:

AThis equation has NO Diophantine solutions.

BThis equations does too have Diophantine solutions.

Theorem 2by Dr. Lamé

If an LED has Diophantine solutions, then the number of steps to the solution is less than or equal to 5 times the smaller of A and B, the coefficients in the equation.

Example:

The number of steps will be Note the “manglish” on “min”

Theorem 3

If you have one Diophantine solution to , then all the others can be calculated by using the following formula.

Let be the solution that you have and , the GCD.

An example:

Theorem 1(30, 12) = 6, 6 divides 18. There are Diophantine solutions

Theorem 2the number of steps is less than or equal to 5(12) = 60

Theorem 3(3, 6) is a Diophantine solution(how to get this, later!)

All other solutions can be found by varying t in the formulas:

If t = 0 we get our original point.

If t = 1, we get (1, 1)

If t = 3, we get (9, 21).

Now, naturally, there is the question of how we got that first Diophantine solution!

There are five steps to finding it:

Step 1Check Theorem 1

Step 2Rewrite the equation totally to

where d is the GCD of A and B

and p and q are dummy variables.

Step 3Use the Euclidean Algorithm to find p and q.

Step 4Multiply both sides of the changed equation to retrieve

the original equation.

Step 5Use Theorem 3 to generate all desired solutions.

Let’s use the same equation that we started with:

Step 1we did this.

Step 2work with:

Step 3

12 = 2(6) + 0

DONE!

Go to the next-to-the-last step and use it with a change: subtract 2(12) from both sides

30  2(12) = 6

Pattern match it to

30 (1) + 12 ( 2) = 6

Step 4I need for the right hand side to be 18, so I’ll multiply both sides by 3…and I’ll carefully preserve my original coefficients by multiplying INSIDE the parentheses.

30 (1 x 3) + 12 (  2 x 3) = 18

So my is (3,  6).

Step 5All my Diophantine solutions look like:

Where t is any integer.

There will be lots of practice on this in the second video.

Right now:Brilliant numbers.

A Brilliant number is a number with n prime factors each which is the same length. We name the number for the number of factors it has:

Example:9 = 3(3)9 is a 2-Brilliant number

121 = 11(11)121 is a 2-Brilliant number

143 = 11 (13)143 is a 2-Brilliant number

989 = 23 (43)989 is a 2-Brilliant number

Now sometimes we actually describe the number of digits in the number along with telling how Brilliant it is:

3, 589 is a 4 digit 2-Brilliant number 3589 = 37(97)

875is a 3 digit 4-Brilliant number875 = 5(5)(5)(7)

55, 913is a 5 digit 4-Brilliant number55913 = 11(13)(17)(23)

Now, on the other hand26 is not Brilliant. 26 = 2(13) and the factors are differing lengths

This is just an aside on yet another type of number. Note that Brilliant numbers are a proper subset of the natural numbers. In fact, the two subsets Brilliant and Not-brilliant are a partition on the set of natural numbers. 1, 2, and 3 are not 2-Brilliant because, for example: 2 has 2 factors: 2 and 1, but one is not a prime factor. You could argue that it’s a 1-Brilliant number, though but you’d still have to deal with 1 in your argument! This is the type of thing that keeps the coffee and beer flowing at international math conferences!

Popper 07, Question 5

16, 900 = 130(130)is a 5 digit 2-Brilliant number

ATrue

BFalse

End of video 1

Diophantine equations are those with some integer solutions – not every solution has to be diophantine, just some of them, to qualify. We’ve seen an example of an equation that has NO diophantine solutions:

This means that the distinction has meaning and that both kinds of subsets of the set of all equations with rational coefficients have set elements.

Let’s look at(10, 25) = 5 and 5 does not divide 7

Here’s another equation in the not-diophantine subset!

However:

(30, 19) = 1 and 1 divides 15

So this one is Diophantine.

Popper 8, Question 1

The two subsets: Diophantine and Not-diophantine are a partition on the set of all polynomials with rational number coefficients.

ATrue

BFalse

Let’s look at another example of solving an LDE (Linear Diophantine Equation)

(210, 45) = 15 and 15 divides 30

Set up the alternate equation in p and q:

210p + 45q = 15(so the last step will be MBS by 2!)

Using the Euclidean Algorithm:

210 = 45(4) + 30

45 = 30(1) + 15

30 = 15(2) + 0

End EA. Go to the next to the last equation and rewrite it by subtracting 30(1) from both sides:

45 – 30(1) = 15Note that the 30(1) does not match the p/q equation…

210 is needed. Solve the first equation for 30:

30 = 210 – 45(4)

SUBSTITUTE

45 – [210 – 45(4)] = 15

45 – 210 + 45 (4) = 15distribute

45(5) – 210 = 15combine like terms 45(1) + 45 (4) = 45 (5)

210 (−1) + 45 (5) = 15matches the p/q. Now multiply to match original (by 2)

210 ( −2) + 45 (10) = 15

is (−2, 10)

All Diophantine solutions are:

If t = 1 (1, − 4) is a Diophantine solution, for example.

Popper 08, Question 2

Given an original equation:5x + 7y = 6

Suppose we do all the work and get down to5(2) + 7(−1) = 3.

What is ?

A(2, −1)

B(4, −2)

CIt cannot be determined at this point in the work.

Another example:

Yes! There are Diophantine solutions.(7, 17) = 1

Set up the p/q equation:

7p + 17q = 1

Euclidean Algorithm work:NOTE THE SWITCH ON THE COEFFICIENTS!

17 = 7(2) + 3

7 = 3(2) + 1

3 = 1(3) + 0grab the next to the last equation! Reformat!

7 – 3(2) = 1oops! Hate that 3! Go up one further: 3 = 17 – 7(2)

Substitute

7 – [17 – 7(2)](2) = 1note the second times 2 there!

7 – [17(2) – 7(4)] = 1Distribute the second times 2 first

7 – 17(2) + 7(4) = 1Distribute the times – 1

7 (5) – 17 (2) = 1Check above 17 is positive…move it inside

7(5) + 17(−2) = 1NOW retrieve the original equation. Multiply “inside”

7(185(5)) + 17(185(−2)) = 185

7(925) + 17 (−370) = 185

is (925, −370)

All Diophantine solutions are:

Popper 08, Question 3

In the above equation (942, −377) is one of the solutions.

ATrue

BFalse

And now, one last example:

Find all Diophantine solutions to

(6, 64) = 22 divides 2!

Set up the p/q equation:

6p + 64q = 2This one is nice! We’ll multiply BS by 1 at the end/

Euclidean Algorithm work:

64 = 6(10) + 4

6 = 4(1) + 2

4 = 2(2) + 0

We’ll work with

6 – 4(1) = 2and we’re missing that coefficient of 64 so we’ll substitute

64 – 6(10) = 4

6 – [64 – 6(10)] = 2

6 – 64 + 6(10) = 2

6(11) – 64 = 2not quite a match to 6p + 64q = 2

6(11) + 64 (−1) = 2

is (11, −1).

All the other Diophantine solutions come from varying the integer t in

Popper 08, Question 4

If you use t = 0 in the above equation you get the from the work with the steps to a solution.

ATrue

BFalse

Popper 08, Question 5

Using this formula with the A and B coefficients from the original equation gives you:

Aall solutions to the equation

Ba proper subset of all solutions

1