8.3: Linear Diophantine Equations
- Last updated
- Sep 29, 2021
- Save as PDF
( \newcommand{\kernel}{\mathrm{null}\,}\)
- Does the linear equation
- Does the linear equation
- Does the linear equation
- Does the linear equation
- Prove the following theorem:
Let
- If
divides , then the equation - If
does not divide , then the equation
- Find integers
and so that - Find integers
and so that - Notice that
(a) Find two pairs of integers
(b) Find two pairs of integers
(c) Determine formulas (one for x and one for y) that will generate pairs of integers
Hint: The two formulas can be written in the form
- Notice that
and so that as small as possible.)
(b) Find two pairs of integersand so that as close to 4 as possible.)
(c) Determine formulas (one forand one for ) that will generate pairs of integers x and y so that
Hint: The two formulas can be written in the formis an arbitrary integer and and are specific integers.
In the two preview activities, we were interested only in integer solutions for certain equations. In such instances, we give the equation a special name.
An equation whose solutions are required to be integers is called a Diophantine equation.
Diophantine equations are named in honor of the Greek mathematician Diophantus of Alexandria (circa 300 c.e.). Very little is known about Diophantus’ life except that he probably lived in Alexandria in the early part of the fourth centuryc.e. and was probably the first to use letters for unknown quantities in arithmetic problems. His most famous work, Arithmetica, consists of approximately 130 problems and their solutions. Most of these problems involved solutions of equations in various numbers of variables. It is interesting to note that Diophantus did not restrict his solutions to the integers but recognized rational number solutions as well. Today, however, the solutions for a so-called Diophantine equation must be integers.
If
Theorem 8.18 in Preview Activity
A linear Diophantine equation in two variables can be defined in a manner similar to the definition for a linear Diophantine equation in one variable.
Let
The equations that were investigated in Preview Activity
The following example is similar to the examples studied in Preview Activity
We can use substitution to verify that
The following table shows other solutions of this Diophantine equation.
It would be nice to determine the pattern that these solutions exhibit. If we consider the solution
where
We should note that we have not yet proved that these solutions are all of the solutions of the Diophantine equation
If the general form for a linear Diophantine equation is
- Verify that the following table shows some solutions of the linear Diophantine equation
- Follow the pattern in this table to determine formulas for
and that will generate integer solutions of the equation
- Answer
-
Add texts here. Do not delete this text first.
Do the solutions for the linear Diophantine equations in Preview Activity
- Answer
-
Add texts here. Do not delete this text first.
The solutions for the linear Diophantine equations in Preview Activity
Let
- If
does not divide , then the linear Diophantine equation - If
divides , then the linear Diophantine equation , ) is a particular solution of this equation, then all the solutions of this equation can be written in the form
for some integer.
- Proof
-
The proof of Part (1) is Exercise (1). For Part (2), we let
, , and be integers with . Since is a linear combination of and . So there exist integers and such that Since
, there exists an integer such that This means that
Now let
We now verify that for each
This proves that the Diophantine equation
We now show that every solution of this equation can be written in the form described in (8.3.4). So suppose that
and are integers such that and this equation can be rewritten in the following form:
Dividing both sides of this equation by
, we obtain This implies that
divides However, by Exercise (7) in Section 8.2,
divides such that gives Substituting this value for
in equation (8.3.5) and solving for yields This proves that every solution of the Diophantine equation
The proof of the following corollary to Theorem 8.22 is Exercise (2)
Let
where
- Use the Euclidean Algorithm to verify that gcd.63; 336/ D 21. What conclusion can be made about linear Diophantine equation
- Use the Euclidean Algorithm to verify that gcd.144; 225/ D 9. What conclusion can be made about linear Diophantine equation
- Answer
-
Add texts here. Do not delete this text first.
- Prove Part (1) of Theorem 8.22:
Let
, , and be integers with does not divide , then the linear Diophantine equation - Prove Corollary 8.23.
Let
, , and be integers with and are relatively prime, then the linear Diophantine equation ) is a particular solution of this equation, then all the solutions of the equation are given by
where - Determine all solutions of the following linear Diophantine equations.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h) - A certain rare artifact is supposed to weigh exactly 25 grams. Suppose that you have an accurate balance scale and 500 each of 27 gram weights and 50 gram weights. Explain how to use Theorem 8.22 to devise a plan to check the weight of this artifact.
Hint: Notice that gcd(50, 27) = 1. Start by writing 1 as a linear combination of 50 and 27.
- On the night of a certain banquet, a caterer offered the choice of two dinners, a steak dinner for $25 and a vegetarian dinner for $16. At the end of the evening, the caterer presented the host with a bill (before tax and tips) for $1461. What is the minimum number of people who could have attended the banquet? What is the maximum number of people who could have attended the banquet?
- The goal of this exercise is to determine all (integer) solutions of the linear Diophantine equation in three variables
(a) First, notice that gcd(12, 9) = 3. Determine formulas that will generate all solutions for the linear Diophantine equation
(b) Explain why the solutions (forand ) of the Diophantine equation
(c) Use the general value for y from Exercise (6a) to determine the solutions of
(d) Use the results from Exercises (6a) and (6c) to determine formulas that will generate all solutions for the Diophantine equation
Note: These formulas will involve two arbitrary integer parameters. Substitute specific values for these integers and then check the resulting solution in the original equation. Repeat this at least three times.
(e) Check the general solution for - Use the method suggested in Exercise (6) to determine formulas that will generate all solutions of the Diophantine equation
- Explain why the Diophantine equation
- The purpose of this exercise will be to prove that the nonlinear Diophantine equation
(a) Explain why if there is a solution of the Diophantine equation
(b) If there is a solution to the congruencesuch that
(c) Use a proof by contradiction to prove that the Diophantine equation - Use the method suggested in Exercise (9) to prove that the Diophantine equation
Explorations and Activities - Linear Congruences in One Variable. Let
be a natural number and let ) is called a linear congruence in one variable. This is called a linear congruence since the variable occurs to the first power. A solution of a linear congruence in one variable is defined similarly to the solution of an equation. A solution is an integer that makes the resulting congruence true when the integer is substituted for the variable
. For example,
The integer
The integer
(a) Verify that
(b) Show that the linear congruence
(c) Determine all solutions of the linear congruence
The following parts of this activity show that we can use the results of Theorem 8.22 to help find all solutions of the linear congruence
(d) Verify that
(e) Use the definition of “congruence” to rewrite the congruence
(f) Use the definition of “divides” to rewrite the result in part (11e) in the form of an equation. (An existential quantifier must be used.)
(g) Use the results of parts (11d) and (11f) to write an equation that will generate all the solutions of the linear congruence
Hint: Use Theorem 8.22. This can be used to generate solutions forand the variable introduced in part (11f). In this case, we are interested only in the solutions for .
Now letbe a natural number and let ) can be handled in the same way that we handled in
(h) Use the definition of “congruence” to rewrite) in terms of “divides.”
(i) Use the definition of “divides” to rewrite the result in part (11h) in the form of an equation. (An existential quantifier must be used.)
(j) Let) in the case where does not divide .
Hint: Use Theorem 8.22.
(k) Let) in the case where divides .
- Answer
-
Add texts here. Do not delete this text first.
