State/Linear Diophantine equations can be solved with the Euclidean algorithm

From SlugmathWiki

Proposition
Proof
Metadata

Proposition: (Linear Diophantine equations can be solved with the Euclidean algorithm) Most specifically: Suppose that $a$ and $b$ are relatively prime integers. Then, there exist integers $x$ and $y$ such that $ax + by = 1$.

More generally: Suppose that $a$ and $b$ are integers, $a \neq 0$, and $g = GCD(a,b)$ (the greatest common divisor of $a$ and $b$), and $m \in \ZZ$. Then, there exist integers $x$ and $y$, such that $ax + by = m$ if and only if $m$ is a multiple of $g$.

Most generally: Suppose that $k$ is a positive integer, and $a_1, \ldots, a_k$ are integers, and $a_1 \neq 0$. Let $g = GCD(a_1, \ldots, a_k)$. If $m \in \ZZ$, then there exist integers $x_1, \ldots, x_k$, such that: $$a_1 x_1 + \cdots + a_k x_k = m,$$ if and only if $m$ is a multiple of $g$.

Logical Connections

This statement logically relies on the following definitions and statements: Def/Relatively prime, Def/Greatest common divisor, Def/Euclidean algorithm, State/Greatest common divisors can be found with the Euclidean algorithm, State/Induction, State/Two out of three principle for divisibility, State/Greatest common divisors can be computed pairwise

The following statements and definitions rely on the material of this page: State/Chinese remainder theorem, State/Every lax vector in a lax basis is primitive, State/Every primitive lax vector belongs to a lax basis, State/Primes dividing a product must divide a factor, and State/Relative primality to the modulus is equivalent to invertibility of a residue

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Basic number theory

Equations in two variables

We begin by proving that if $a,b \in \ZZ$, and $a \neq 0$, $g = GCD(a,b)$, and $m \in \ZZ$, then there exist $x,y \in \ZZ$ such that $ax + by = m$ if and only if $m$ is a multiple of $g$.

Suppose that $a$ and $b$ are integers, and $g = GCD(a,b)$.

We treat each logical direction separately.

$\Rightarrow$

Suppose that $m$ is a multiple of $g$. Let $n$ be an integer satisfying $m = gn$. We may apply the Euclidean algorithm to $a$ and $b$, yielding a sequence of quotients and remainders:

$$a = q_0 b + r_0,$$ $$b = q_1 r_0 + r_1,$$ $$r_0 = q_2 r_1 + r_2,$$ etc.., where the last step of the algorithm reads: $$r_{t-2} = q_{t} r_{t-1} + r_t,$$ and $r_t = g = GCD(a,b)$, since a greatest common divisor arises from the Euclidean algorithm.

Let $r_{-1} = b$ and $r_{-2} = a$, for convenience. From the equations $r_{k-2} = q_k r_{k-1} + r_k$ (for $0 \leq k \leq t$), we find that the sequence of remainders satisfies the linear recurrence relation: $$r_k = -q_k r_{k-1} + r_{k-2}.$$ We claim that, for all $k \in \ZZ$, such that $k \geq -2$, there exist $x,y \in \ZZ$, such that $r_k = x a + y b$. We prove this claim by induction on $k$.

$k=-2,-1$	When $k = -2$, $r_k = a$, and the claim follows from letting $x = 1, y = 0$. When $k = -1$, $r_k = b$, and the claim follows from letting $x = 0, y = 1$.
$k \geq 0$	Now, suppose that $k \geq 0$, and the claim has been proven for all smaller values of $k$. In particular, there exist integers $x_1, y_1, x_2, y_2$, such that $r_{k-1} = x_1 a + y_1 b$, and $r_{k-2} = x_2 a + y_2 b$. It follows that: $$r_k = -q_k r_{k-1} + r_{k-2} = -q_k (x_1 a + y_1 b) + (x_2 a + y_2 b).$$ Simplifying yields: $$r_k = (-q_k x_1 + x_2) a + (-q_k y_1 + y_2) b.$$ Thus, letting $x = -q_k x_1 + x_2$, and $y = -q_k y_1 + y_2$, the claim is verified.
By induction, we find that every remainder $r_k$ can be expressed as $x a + y b$, for some $x,y \in \ZZ$.

This applies, in particular, to the final remainder, $r_t = GCD(a,b)$. Hence, there exist $x,y \in \ZZ$, such that: $$ax + by = GCD(a,b).$$

Furthermore, since $n \in \ZZ$, multiplying both sides of this equation by $n$ yields: $$a (nx) + b (ny) = n GCD(a,b).$$ Hence the Diophantine equation $ax + by = m = ng$ has a solution, for every $n$.

$\Leftarrow$

Now, suppose that the Diophantine equation $ax + by = m$ has a solution. Then, since $g$ divides $a$ and $g$ divides $b$, the two out of three principle implies that $g$ divides $m$.

Hence, the Diophantine equation $ax + by = m$ has a solution if and only if $m$ is a multiple of $g$.

Equations in many variables

Now, we prove the solubility criterion for linear Diophantine equations of many variables, using induction on the number of variables.

$k=1,2$

If $k=1$, suppose that $a_1 \in \ZZ$, and $a_1 \neq 0$, and let $g = GCD(a_1) = a_1$. Let $m$ be an integer. We consider the Diophantine equation $a_1 x = m$. Substitution yields $gx = m$. It is clear that this equation has a solution if and only if $m$ is a multiple of $g$.

If $k=2$, the solubility criterion for the Diophantine equation $a_1 x_1 + a_2 x_2 = m$ (where $g = GCD(a_1, a_2)$) has been proven above.

$k > 2$

Suppose that $k > 2$, and we have proven the solubility criterion for linear Diophantine equations in fewer than $k$ variables. Let $a_1, \ldots, a_k$ be integers, and $a_1 \neq 0$. Let $g = GCD(a_1, \ldots, a_k)$. Let $h = GCD(a_1, a_2)$. Then $g = GCD(h, a_3, \ldots, a_k)$, since greatest common divisors can be computed pairwise. There are two directions to verify in the solubility criterion:

$\Rightarrow$	If $n \in \ZZ$, then by the inductive hypothesis (the solubility criterion for equations in $k-1$ variables), there exist integers $w, x_3, \ldots, x_k$ such that: $$h w + x_3 a_3 + \cdots + x_k a_k = gn.$$ Furthermore, by the solubility of linear Diophantine equations in $2$ variables, there exist integers $x_1, x_2$, such that: $$x_1 a_1 + x_2 a_2 = hw.$$ Substitution yields: $$x_1 a_1 + x_2 a_2 + x_3 a_3 + \cdots + x_k a_k = gn.$$ Hence, if $m$ is a multiple of $g$, the Diophantine equation $a_1 x_1 + \cdots + a_k x_k = m$ is soluble.
$\Leftarrow$	Suppose that the Diophantine equation $a_1 x_1 + \cdots + a_k x_k = m$ is soluble. Then, $g$ divides every term $a_i x_i$ on the left side of this equation, for any solution $x_1, \ldots, x_k \in \ZZ$. It follows that $g$ divides $m$.

Hence the Diophantine equation $a_1 x_1 + \cdots + a_k x_k = m$ is soluble if and only if $g$ divides $m$.

Hence we have proven the solubility criterion for linear Diophantine equations in $n$ variables.

State/Linear Diophantine equations can be solved with the Euclidean algorithm

From SlugmathWiki

Logical Connections

Equations in two variables

Equations in many variables

Views

Personal tools

Navigation

Mathematics

Pegagogy

Search

Toolbox