Linear Diophantine Equations

Abstract

Given the equation

Where and are not both zero. Let

By LDET 1, if does not divide , then the equation has no solutions
By LDET 1 and 2, if does divide , then the equation has an infinite number of solutions

When , there are infinitely many Certificates of Correctness for GCD

Definition

An equation in which both of the coefficients are integers is called a Diophantine equation.

Named after the 3rd century Hellenistic mathematician Diophantus of Alexandria.

The simplest Diophantine equation is

Where and are given. Suppose is non-zero. By definition of divisibility, this equation only has an integer solution of

Linear Diophantine Equation Theorem, Part 1 (LDET 1)

Theorem

For all integers , , and , with and not both zero, the linear Diophantine equation

has a integer solution if and only if where

(See divisibility, GCD)

Proof

Let and be arbitrary integers, with and both not zero.
First, assume the linear Diophantine equation has an integer solution, say and , so we hav . Since , we have and . Hence by DIC, which gives

Conversely, assume that .
By definition of divisibility, there exists an integer such that .
Now, by BL, there exists integers and such that .
Multiplying both sides of that equation by k gives
Hence, and is an integer solution to

Example

Which of the linear Diophantine equations has a solution?

Note that

Since is not divisible by , equation 1 does not have an integer solution
Since is divisible by , equation 2 has an integer solution

Note

To find an integer solution to when and :

Find a Certificate of Correctness and for , which gives
Multiply this equation by to get , which gives the solutions and

Example

Determine whether the Diophantine equation has a solution, and if so, find that solution

Apply the Extended Euclidean Algorithm

			EA

We see that . Since , then from LDET 1, we conclude that this equation has a solution.

The certificate of correctness from the EEA table is and , so we have

Multiplying this equation by gives

So one integer solution is and

Linear Diophantine Equation Theorem, Part 2 (LDET 2)

Theorem

Let , , and be integers with and not both zero, and . If and is one particular solution to the linear Diophantine equation , then the set of all solutions is given by

(See Set Builder Notation)

Proof

Let , , and be arbitrary integers, with and not both zero, and let . Define two sets

We will prove that using the method of proving set equality and universally quantified implications

To prove , we prove the implication
Let be an arbitrary integer, and assume that
Then we have

Where the last inequality follows since is a solution to the equation .
Thus we conclude that

To prove , we prove the implication
Assume that , so we have

subtracting these two equations gives

Dividing this equation by (which is valid since and are not both zero and )

Where since .
From Division by GCD, we know that and are coprime, and from equation (1), we know divides .
Hence, fr'm Coprimeness and Divisibility, it follows that

and therefore, by the definition of divisibility, there exists an integer such that .
Thus, we have , and subbing this into equation (1) gives (since ). We conclude that

for some integer , and hence

Example

Find all solutions to the Diophantine equation

From the previous example, we found that , and found an integer solution and . Based on this solution, from LDET 2, with and and , the set of all solutions is given by