Linear Diophantine Equations

Section 8.3 Linear Diophantine Equations

Beginning Activity Beginning Activity 1: Integer Solutions for Linear Equations in One Variable
A4 US

1.

Does the linear equation $6x = 42$ have a solution that is an integer? Explain.

2.

Does the linear equation $7x = -21$ have a solution that is an integer? Explain.

3.

Does the linear equation $4x = 9$ have a solution that is an integer? Explain.

4.

Does the linear equation $-3x = 20$ have a solution that is an integer? Explain.

5.

Prove the following theorem:

Theorem 8.20.

Let $a, b \in \mathbb{Z}$ with $a \ne 0\text{.}$

If $a$ divides $b\text{,}$ then the equation $ax = b$ has exactly one solution that is an integer.
If $a$ does not divide $b\text{,}$ then the equation $ax = b$ has no solution that is an integer.

Beginning Activity Beginning Activity 2: Linear Equations in Two Variables
A4 US

1.

Find integers $x$ and $y$ so that $2x + 6y = 25$ or explain why it is not possible to find such a pair of integers.

2.

Find integers $x$ and $y$ so that $6x - 9y = 100$ or explain why it is not possible to find such a pair of integers.

3.

Notice that $x = 2$ and $y = 1$ is a solution of the equation $3x + 5y = 11\text{,}$ and that $x = 7$ and $y = -2$ is also a solution of the equation $3x + 5y = 11\text{.}$

(a)

Find two pairs of integers $x$ and $y$ so that $x > 7$ and $3x + 5y = 11\text{.}$ (Try to keep the integer values of $x$ as small as possible.)

(b)

Find two pairs of integers $x$ and $y$ so that $x \lt 2$ and $3x + 5y = 11\text{.}$ (Try to keep the integer values of $x$ as close to 2 as possible.)

(c)

Determine formulas (one for $x$ and one for $y$) that will generate pairs of integers $x$ and $y$ so that $3x + 5y = 11\text{.}$

Hint.

The two formulas can be written in the form $x = 2 + km$ and $y = 1 + kn\text{,}$ where $k$ is an arbitrary integer and $m$ and $n$ are specific integers.

4.

Notice that $x = 4$ and $y = 0$ is a solution of the equation $4x + 6y = 16\text{,}$ and that $x = 7$ and $y = -2$ is a solution of the equation $4x + 6y = 16\text{.}$

(a)

Find two pairs of integers $x$ and $y$ so that $x > 7$ and $4x + 6y = 16\text{.}$ (Try to keep the integer values of $x$ as small as possible.)

(b)

Find two pairs of integers $x$ and $y$ so that $x \lt 4$ and $4x + 6y = 16\text{.}$ (Try to keep the integer values of $x$ as close to 4 as possible.)

(c)

Determine formulas (one for $x$ and one for $y$) that will generate pairs of integers $x$ and $y$ so that $4x + 6y = 16\text{.}$

Hint.

The two formulas can be written in the form $x = 4 + km$ and $y = 0 + kn\text{,}$ where $k$ is an arbitrary integer and $m$ and $n$ are specific integers.

In the two beginning activities, we were interested only in integer solutions for certain equations. In such instances, we give the equation a special name.

Definition.

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 (third century C.E.). Very little is known about Diophantus' life except that he probably lived in Alexandria in the early part of the fourth century C.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.

Definition.

If $a$ and $b$ are integers with $a \ne 0\text{,}$ then the equation $ax = b$ is a linear Diophantine equation in one variable.

Theorem 8.20 in Beginning Activity 1 provides us with results that allow us to determine which linear diophantine equations in one variable have solutions and which ones do not have a solution.

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.

Definition.

Let $a\text{,}$ $b\text{,}$ and $c$ be integers with $a \ne 0$ and $b \ne 0\text{.}$ The Diophantine equation $ax + by = c$ is called a linear Diophantine equation in two variables.

The equations that were investigated in Beginning Activity 2 were linear Diophantine equations in two variables. The problem of determining all the solutions of a linear Diophantine equation has been completely solved. Before stating the general result, we will provide a few more examples.

Example 8.21. A Linear Diophantine Equation in Two Variables.

The following example is similar to the examples studied in Beginning Activity 2.

We can use substitution to verify that $x = 2$ and $y = -1$ is a solution of the linear Diophantine equation

\begin{equation*} 4x + 3y = 5\text{.} \end{equation*}

The following table shows other solutions of this Diophantine equation.

$x$	$y$
2	$-1$
5	$-5$
8	$-9$
11	$-13$
$-1$	3
$-4$	7
$-7$	11
$-10$	15

It would be nice to determine the pattern that these solutions exhibit. If we consider the solution $x = 2$ and $y =-1$ to be the “starting point,” then we can see that the other solutions are obtained by adding 3 to $x$ and subtracting 4 from $y$ in the previous solution. So we can write these solutions to the equation as

\begin{equation*} x = 2 + 3k \qquad \text{ and } \qquad y = -1 - 4k\text{,} \end{equation*}

where $k$ is an integer. We can use substitution and algebra to verify that these expressions for $x$ and $y$ give solutions of this equation as follows:

\begin{align*} 4x + 3y \amp = 4 \left( 2+3k \right) + 3 \left( -1-4k \right)\\ \amp = \left( 8 + 12k \right) + \left( -3 - 12k \right)\\ \amp = 5\text{.} \end{align*}

We should note that we have not yet proved that these solutions are all of the solutions of the Diophantine equation $4x + 3y = 5\text{.}$ This will be done later.

If the general form for a linear Diophantine equation is $ax + by = c\text{,}$ then for this example, $a = 4$ and $b = 3\text{.}$ Notice that for this equation, we started with one solution and obtained other solutions by adding $b = 3$ to $x$ and subtracting $a = 4$ from $y$ in the previous solution. Also, notice that $\gcd( 3, 4 ) = 1\text{.}$

Progress Check 8.22. An Example of a Linear Diophantine Equation.

(a)

Verify that the following table shows some solutions of the linear Diophantine equation $6x + 9y = 12\text{.}$

$x$	$y$
2	0
5	$-2$
8	$-4$
11	$-6$
$-1$	2
$-4$	4
$-7$	6
$-10$	8

(b)

Follow the pattern in this table to determine formulas for $x$ and $y$ that will generate integer solutions of the equation $6x + 9y = 12\text{.}$ Verify that the formulas actually produce solutions for the equation $6x + 9y = 12\text{.}$

Solution.

$x = 2 + 3k$ and $y = 0 - 2k\text{,}$ where $k$ can be any integer. Again, this does not prove that these are the only solutions.

Progress Check 8.23. Revisiting Beginning Activity 2.

Do the solutions for the linear Diophantine equations in Beginning Activity 2 show the same type of pattern as the solutions for the linear Diophantine equations in Example 8.21 and Progress Check 8.22? Explain.

Solution.

One of the Diophantine equations in Beginning Activity 2 was $3x + 5y = 11\text{.}$ We were able to write the solutions of this Diophantine equation in the form

\begin{equation*} x = 2 + 5k \text{ and } y = 1 - 3k\text{,} \end{equation*}

where $k$ is an integer. Notice that $x = 2$ and $y = 1$ is a solution of this equation. If we consider this equation to be in the form $ax + by = c\text{,}$ then we see that $a = 3\text{,}$ $b = 5\text{,}$ and $c = 11\text{.}$ Solutions for this equation can be written in the form

\begin{equation*} x = 2 + bk \text{ and } y = 1 - ak\text{,} \end{equation*}

where $k$ is an integer.

The other equation was $4x + 6y = 16\text{.}$ So in this case, $a = 4\text{,}$ $b = 6\text{,}$ and $c = 16\text{.}$ Also notice that $d = \gcd ( 4, 6 ) = 2\text{.}$ We note that $x = 4$ and $y = 0$ is one solution of this Diophantine equation and solutions can be written in the form

\begin{equation*} x = 4 + 3k \text{ and } y = 0 - 2k\text{,} \end{equation*}

where $k$ is an integer. Using the values of $a\text{,}$ $b\text{,}$ and $d$ given above, we see that the solutions can be written in the form

\begin{equation*} x = 2 + \frac{b}{d} k \text{ and } y = 0 - \frac{a}{d}\text{,} \end{equation*}

where $k$ is an integer.

The solutions for the linear Diophantine equations in Beginning Activty 2, Example 8.21, and Progress Check 8.22 provide examples for the second part of Theorem 8.24.

Theorem 8.24.

Let $a\text{,}$ $b\text{,}$ and $c$ be integers with $a \ne 0$ and $b \ne 0\text{,}$ and let $d = \gcd( a, b )\text{.}$

If $d$ does not divide $c\text{,}$ then the linear Diophantine equation $ax + by = c$ has no solution.
If $d$ divides $c\text{,}$ then the linear Diophantine equation $ax + by = c$ has infinitely many solutions. In addition, if $\left( x_0, y_0 \right)$ is a particular solution of this equation, then all the solutions of this equation can be written in the form

\begin{equation*} x = x_0 + \frac{b}{d} k \text{ and } y = y_0 - \frac{a}{d} k\text{,} \end{equation*}

for some integer $k\text{.}$

Proof.

The proof of Item 1 is Exercise 8.3.1. For Item 2, we let $a\text{,}$ $b\text{,}$ and $c$ be integers with $a \ne 0$ and $b \ne 0\text{,}$ and let $d = \gcd( a,b )\text{.}$ We also assume that $d \mid c\text{.}$ Since $d = \gcd( a,b )\text{,}$ Theorem 8.10 tells us that $d$ is a linear combination of $a$ and $b\text{.}$ So there exist integers $s$ and $t$ such that

\begin{equation} d = as + bt\text{.}\tag{79} \end{equation}

Since $d \mid c\text{,}$ there exists an integer $m$ such that $c = dm\text{.}$ We can now multiply both sides of equation (79) by $m$ and obtain

\begin{align*} dm \amp = ( {as + bt} ) m\\ c \amp a( sm ) + b( tm )\text{.} \end{align*}

This means that $x = sm\text{,}$ $y = tm$ is a solution of $ax + by = c\text{,}$ and we have proved that the Diophantine equation $ax + by = c$ has at least one solution.

Now let $x = x_0\text{,}$ $y = y_0$ be any particular solution of $ax + by = c\text{,}$ let $k \in \mathbb{Z}\text{,}$ and let

\begin{equation} x = x_0 + \frac{b}{d} k \qquad y = y_0 - \frac{a}{d} k\text{.}\tag{80} \end{equation}

We now verify that for each $k \in \mathbb{Z}\text{,}$ the equations in (80) produce a solution of $ax + by = c\text{.}$

\begin{align*} ax + by \amp = a \!\left( {x_0 + \frac{b}{d} k } \right) + b \!\left( {y_0 - \frac{a}{d} k} \right )\\ \amp = a x_0 + \frac{ab}{d} k + b y_0 - \frac{ab}{d} k\\ \amp = a x_0 + b y_0\\ \amp = c\text{.} \end{align*}

This proves that the Diophantine equation $ax + by = c$ has infinitely many solutions.

We now show that every solution of this equation can be written in the form described in equation (80). So suppose that $x$ and $y$ are integers such that $ax + by = c\text{.}$ Then

\begin{equation*} ( {ax + by} ) - ( {ax_0 + by_0} ) = c - c = 0\text{,} \end{equation*}

and this equation can be rewritten in the following form:

\begin{equation} a( {x - x_0} ) = b( {y_0 - y} )\text{.}\tag{81} \end{equation}

Dividing both sides of this equation by $d\text{,}$ we obtain

\begin{equation*} \left( \frac{a}{d} \right) \left( {x - x_0} \right ) = \left( \frac{b}{d} \right) \left( {y_0 - y} \right)\text{.} \end{equation*}

This implies that

\begin{equation*} \frac{a}{d} \text{ divides } \left( \frac{b}{d} \right) ( {y_0 - y} )\text{.} \end{equation*}

However, by Task 7.a in Section 8.2, $\gcd \!\left( \dfrac{a}{d}, \dfrac{b}{d} \right) = 1\text{,}$ and so by Theorem 8.14, we can conclude that $\dfrac{a}{d}$ divides $\left( {y_0 - y} \right)\text{.}$ This means that there exists an integer $k$ such that $y_0 - y = \dfrac{a}{d} k\text{,}$ and solving for $y$ gives

\begin{equation*} y = y_0 - \frac{a}{d} k\text{.} \end{equation*}

Substituting this value for $y$ in equation (81) and solving for $x$ yields

\begin{equation*} x = x_0 + \frac{b}{d} k\text{.} \end{equation*}

This proves that every solution of the Diophantine equation $ax + by = c$ can be written in the form prescribed in (2).

The proof of the following corollary to Theorem 8.24 is Exercise 8.3.2.

Corollary 8.25.

Let $a\text{,}$ $b\text{,}$ and $c$ be integers with $a \ne 0$ and $b \ne 0\text{.}$ If $a$ and $b$ are relatively prime, then the linear Diophantine equation $ax + by = c$ has infinitely many solutions. In addition, if $x_0\text{,}$ $y_0$ is a particular solution of this equation, then all the solutions of the equation are given by

\begin{equation*} x = x_0 + b k \qquad y = y_0 - a k \end{equation*}

where $k \in \mathbb{Z}\text{.}$

Progress Check 8.26. Linear Diophantine Equations.

(a)

Use the Euclidean Algorithm to verify that $\gcd ({63, 336} ) = 21\text{.}$ What conclusion can be made about linear Diophantine equation $63x + 336y = 40$ using Theorem 8.24? If this Diophantine equation has solutions, write formulas that will generate the solutions.

Solution.

Since 21 does not divide 40, Theorem 8.24 tells us that the Diophantine equation $63x + 336y = 40$ has no solutions. Remember that this means there is no ordered pair of integers $( x, y )$ such that $63x + 336y = 40\text{.}$ However, if we allow $x$ and $y$ to be real numbers, then there are real number solutions. In fact, we can graph the straight line whose equation is $63x + 336y = 40$ in the Cartesian plane. From the fact that there is no pair of integers $x, y$ such that $63x + 336y = 40\text{,}$ we can conclude that there is no point on the graph of this line in which both coordinates are integers.

(b)

Use the Euclidean Algorithm to verify that $\gcd( {144, 225} ) = 9\text{.}$ What conclusion can be made about linear Diophantine equation $144x + 225y = 27$ using Theorem 8.24? If this Diophantine equation has solutions, write formulas that will generate the solutions.

Solution.

To write formulas that will generate all the solutions, we first need to find one solution for $144x + 225y = 27\text{.}$ This can sometimes be done by trial and error, but there is a systematic way to find a solution. The first step is to use the Euclidean Algorithm in reverse to write $\gcd ( {144, 225} )$ as a linear combination of 144 and 225. See Section 8.1 to review how to do this. The result from using the Euclidean Algorithm in reverse for this situation is

\begin{equation*} 144 \cdot 11 + 225 \cdot ( {-7} ) = 9\text{.} \end{equation*}

If we multiply both sides of this equation by 3, we obtain

\begin{equation*} 144 \cdot 33 + 225 \cdot ( {-21} ) = 27\text{.} \end{equation*}

This means that $x_0 = 33, y_0 = -21$ is a solution of the linear Diophantine equation $144x + 225y = 27\text{.}$ We can now use Theorem 8.24 to conclude that all solutions of this Diophantine equation can be written in the form

\begin{equation*} x = 33 + \frac{225}{9} k \qquad y = -21 -\frac{144}{9} k\text{,} \end{equation*}

where $k \in \mathbb{Z}\text{.}$ Simplifying, we see that all solutions can be written in the form

\begin{equation*} x = 33 + 25 k \qquad y = -21 -16 k\text{,} \end{equation*}

where $k \in \mathbb{Z}\text{.}$

We can check this general solution as follows: Let $k \in \mathbb{Z}\text{.}$ Then

\begin{align*} 144x + 225y \amp = 144 ( {33 + 25k} ) + 225 ( {-21 - 16k} )\\ \amp = ( {4752 + 3600k} ) + ( {-4725 - 3600k} )\\ \amp = 27\text{.} \end{align*}

Exercises Exercises

1.

Prove Item 1 of Theorem 8.24:

Let $a\text{,}$ $b\text{,}$ and $c$ be integers with $a \ne 0$ and $b \ne 0\text{,}$ and let $d = \gcd( a,b )\text{.}$ If $d$ does not divide $c\text{,}$ then the linear Diophantine equation $ax + by = c$ has no solution.

2.

Prove Corollary 8.25.

Let $a\text{,}$ $b\text{,}$ and $c$ be integers with $a \ne 0$ and $b \ne 0\text{.}$ If $a$ and $b$ are relatively prime, then the linear Diophantine equation $ax + by = c$ has infinitely many solutions. In addition, if $\left( x_0, y_0 \right)$ is a particular solution of this equation, then all the solutions of the equation are given by
\begin{equation*} x = x_0 + b k \qquad y = y_0 - a k\!\text{,} \end{equation*}
where $k \in \mathbb{Z}\text{.}$

3.

Determine all solutions of the following linear Diophantine equations.

(a)

$9x + 14y = 1$

Answer.

$x = -3 + 14k\text{,}$ $y = 2 - 9k$

(b)

$18x + 22y = 4$

Answer.

$x = -1 + 11k\text{,}$ $y = 1 - 9k$

(c)

$48x - 18y = 15$

Answer.

No solution

(d)

$12x + 9y = 6$

Answer.

$x = 2+3k\text{,}$ $y = -2-4k$

(e)

$200x + 49y = 10$

(f)

$200x + 54y = 21$

(g)

$10x - 7y = 31$

(h)

$12x + 18y = 6$

4.

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.24 to devise a plan to check the weight of this artifact.

Hint.

Notice that $\gcd( {50, 27} ) = 1\text{.}$ Start by writing 1 as a linear combination of 50 and 27.

Answer.

There are several possible solutions to this problem, each of which can be generated from the solutions of the Diophantine equation $27x + 50y = 25\text{.}$

5.

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?

Answer.

This problem can be solved by finding all solutions of a linear Diophantine equation $25x + 16y = 1461\text{,}$ where both $x$ and $y$ are positive. The mininum number of people attending the banquet is 66.

6.

The goal of this exercise is to determine all (integer) solutions of the linear Diophantine equation in three variables $12x_1 + 9x_2 + 16x_3 = 20\text{.}$

(a)

First, notice that $\gcd( {12, 9} ) = 3\text{.}$ Determine formulas that will generate all solutions for the linear Diophantine equation $3y + 16x_3 = 20\text{.}$

Answer.

$y = 12 + 16k, x_3 = -1 - 3k$

(b)

Explain why the solutions (for $x_1$ and $x_2$) of the Diophantine equation $12x_1 + 9x_2 = 3y$ can be used to generate solutions for $12x_1 + 9x_2 + 16x_3 = 20\text{.}$

Answer.

If $3y = 12x_1 + 9x_2$ and $3y + 16x_3 = 20\text{,}$ we can substitute for $3y$ and obtain $12x_1 + 9x_2 + 16x_3 = 20\text{.}$

(c)

Use the general value for $y$ from Task 8.3.6.a to determine the solutions of $12x_1 + 9x_2 = 3y\text{.}$

Answer.

Rewrite the equation $12x_1 + 9x_2 = 3y$ as $4x_1 + 3x_2 = y\text{.}$ A general solution for this linear Diophantine equation is

\begin{align*} x_1 \amp = y + 3n\\ x_2 \amp = -y - 4n\text{.} \end{align*}

(d)

Use the results from Task 8.3.6.a and Task 8.3.6.c to determine formulas that will generate all solutions for the Diophantine equation $12x_1 + 9x_2 + 16x_3 = 20\text{.}$

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 $12x_1 + 9x_2 + 16x_3 = 20$ from Task 8.3.6.d.

7.

Use the method suggested in Exercise 8.3.6 to determine formulas that will generate all solutions of the Diophantine equation $8x_1 +4x_2 - 6x_3 = 6\text{.}$ Check the general solution.

8.

Explain why the Diophantine equation $24x_1 - 18x_2 + 60x_3 = 21$ has no solution.

9.

The purpose of this exercise will be to prove that the nonlinear Diophantine equation $3x^2 - y^2 = -2$ has no solution.

(a)

Explain why if there is a solution of the Diophantine equation $3x^2 - y^2 = -2\text{,}$ then that solution must also be a solution of the congruence $3x^2 - y^2 \equiv -2 \pmod 3\text{.}$

(b)

If there is a solution to the congruence $3x^2 - y^2 \equiv -2 \pmod 3\text{,}$ explain why there then must be an integer $y$ such that $y^2 \equiv 2 \pmod 3\text{.}$

(c)

Use a proof by contradiction to prove that the Diophantine equation $3x^2 - y^2 = -2$ has no solution.

10.

Use the method suggested in Exercise 8.3.9 to prove that the Diophantine equation $7x^2 + 2 = y^3$ has no solution.

Activity 49. Linear Congruences in One Variable.

Let $n$ be a natural number and let $a, b \in \mathbb{Z}$ with $a \ne 0\text{.}$ A congruence of the form $ax \equiv b \pmod n$ is called a linear congruence in one variable. This is called a linear congruence since the variable $x$ 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 $x\text{.}$ For example,

The integer $x = 3$ is a solution for the congruence $2x \equiv 1 \pmod 5$ since $2 \cdot 3 \equiv 1 \pmod 5$ is a true congruence.
The integer $x = 7$ is not a solution for the congruence $3x \equiv 1 \pmod 6$ since $3 \cdot 7 \equiv 1 \pmod 6$ is a not a true congruence.

(a)

Verify that $x = 2$ and $x = 5$ are the only solutions the linear congruence $4x \equiv 2 \pmod 6$ with $0 \leq x \lt 6\text{.}$

(b)

Show that the linear congruence $4x \equiv 3 \pmod 6$ has no solutions with $0 \leq x \lt 6\text{.}$

(c)

Determine all solutions of the linear congruence $3x \equiv 7 \pmod 8$ with $0 \leq x \lt 8\text{.}$

(d)

The following parts of this activity show that we can use the results of Theorem 8.24 to help find all solutions of the linear congruence $6x \equiv 4 \pmod 8\text{.}$

Verify that $x = 2$ and $x = 6$ are the only solutions for the linear congruence $6x \equiv 4 \pmod 8$ with $0 \leq x \lt 8\text{.}$

(e)

Use the definition of “congruence” to rewrite the congruence $6x \equiv 4 \pmod 8$ in terms of “divides.”

(f)

Use the definition of “divides” to rewrite the result in Task 49.e in the form of an equation. (An existential quantifier must be used.)

(g)

Use the results of Task 49.d and Task 49.f to write an equation that will generate all the solutions of the linear congruence $6x \equiv 4 \pmod 8\text{.}$

Hint.

Use Theorem 8.24. This can be used to generate solutions for $x$ and the variable introduced in Task 49.f. In this case, we are interested only in the solutions for $x\text{.}$

(h)

Now let $n$ be a natural number and let $a, c \in \mathbb{Z}$ with $a \ne 0\text{.}$ A general linear congruence of the form $ax \equiv c \pmod n$ can be handled in the same way that we handled in $6x \equiv 4 \pmod 8\text{.}$

Use the definition of “congruence” to rewrite $ax \equiv c \pmod n$ in terms of “divides.”

(i)

Use the definition of “divides” to rewrite the result in Task 49.h in the form of an equation. (An existential quantifier must be used.)

(j)

Let $d = \gcd( {a, n} )\text{.}$ State and prove a theorem about the solutions of the linear congruence $ax \equiv c \pmod n$ in the case where $d$ does not divide $c\text{.}$

Hint.

Use Theorem 8.24.

(k)

Let $d = \gcd( {a, n} )\text{.}$ State and prove a theorem about the solutions of the linear congruence $ax \equiv c \pmod n$ in the case where $d$ divides $c\text{.}$

\(x\)	\(y\)
2	\(-1\)
5	\(-5\)
8	\(-9\)
11	\(-13\)
\(-1\)	3
\(-4\)	7
\(-7\)	11
\(-10\)	15

\(x\)	\(y\)
2	0
5	\(-2\)
8	\(-4\)
11	\(-6\)
\(-1\)	2
\(-4\)	4
\(-7\)	6
\(-10\)	8

Section 8.3 Linear Diophantine Equations

Beginning Activity Beginning Activity 1: Integer Solutions for Linear Equations in One Variable A4US

1.

2.

3.

4.

5.

Theorem 8.20.

Beginning Activity Beginning Activity 2: Linear Equations in Two Variables A4US

1.

2.

3.

(a)

(b)

(c)

4.

(a)

(b)

(c)

Definition.

Definition.

Definition.

Example 8.21. A Linear Diophantine Equation in Two Variables.

Progress Check 8.22. An Example of a Linear Diophantine Equation.

(a)

(b)

Progress Check 8.23. Revisiting Beginning Activity 2.

Theorem 8.24.

Proof.

Corollary 8.25.

Progress Check 8.26. Linear Diophantine Equations.

(a)

(b)

Exercises Exercises

1.

2.

3.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

4.

5.

6.

(a)

(b)

(c)

(d)

(e)

7.

8.

9.

(a)

(b)

(c)

10.

Activity 49. Linear Congruences in One Variable.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

Beginning Activity Beginning Activity 1: Integer Solutions for Linear Equations in One Variable
A4 US

Beginning Activity Beginning Activity 2: Linear Equations in Two Variables
A4 US