Section 008) Linear Diophantine equation

Introduction

Diophantine equation is a polynomial  usually in two or more unknowns  such that only the integer solutions are sought . A linear Diophantine equation equates the sum of two or more monomials  each of degree  1 in one of the variables, to a constant. An exponential Diophantine equation is one in which exponents on terms can be unknowns.

A Diophantine equation can have zero, finite or infinite solutions.
.
The name Diophantine equation comes from the mathematician  Diophantus who studied  these equations. 

In this chapter we shall focus on linear Diophantine equation.

Linear Diophantine Equation

As mentioned in introduction   a linear Diophantine equation equates the sum of two or more monomials  each of degree 1 in one of the variables, to a constant that seeks integer solutions. 

Mathematically we have

$\sum_{i=1}^na_i x_i = c$ where $a_i$ are integer  constants and $x_i$  is a variable and the value of n is greater or equal to 2. We are seeking solution that all the $x_i$ are integers

Linear Diophantine Equation with two variables

A linear Diophantine Equation with two variables is of the form 

$ax+by=c\cdots(1)$

Where a,b,c are integers and we are looking for solution x and y to be integers.

This equation may have zero solutions or at least one solution. In case this has at least one solution then it has infinite solutions

Criteria for equation to have at least one solution

$ax+by=c\cdots(1)$ has a solution if and only if gcd(a,b) is a factor of c

proof:

Since GCD(a,b) divides a and b then GCD(a,b) divides ax + by  or GCD(a,b) divides c.

Since GCD(a,b) = ap + bq for some integers p, and q divides c so there exists d such that

c = GCD(a,b ) * d = (ap + bq) * d = apd + bqd 

So x = pd, y = qd is  a solution of ax+by = c.

Hence proved 

General solution of Linear Diophantine equation

If $(x= x_0, y =y_0)$  is a solution of $ax+by=c$ then $x=x_0+t * \frac{b}{gcd(a,b)}, y=y_0- t * \frac{a}{gcd(a,b)}$ as t is an integer is a general solution of  $ax+by=c$

proof:

$(x_0,y_0)$ is a solution of $ax+by=c$
So  $ax_0+by_0=c$

So $a(x_0+t * \frac{b}{gcd(a,b)}) +  b(y_0- t * \frac{a}{gcd(a,b)})$
$= ax_0 + by_0 + at * \frac{b}{gcd(a,b)} - bt * \frac{a}{gcd(a,b)}$
$= ax_0 + by_0 +   \frac{bat}{gcd(a,b)} -  \frac{bat}{gcd(a,b)}$
$=ax_0+by+0 = c$

Proved

Finding Solutions of  Linear Diophantine Equation with 2 variables

To solve a linear Diophantine equation with 2 variables  extended Euclidean algorithm is used.

This shall provide one solution.
Then using the theorem above we can find all the solutions
For example we have found for 1001,104 one solution 

GCD(1001,104) = 13 = -3 * 1001 + 29 * 104 

Now $\frac{1001}{13} = 77$
And  $\frac{104}{13} = 8$

So we have gcd(1001,104) = 13 = (-3 + 8t ) * 1001 - (29 - 77t)  * 104 for $t \in \mathbb Z$


Now we provide below some examples providing solutions of linear Diophantine equations

Problem 1

Find an integer solution of $34x + 17 y = 1$

Solution 1

As GCD(34,17) = 17 and 17 does not divide 1 so there is no solution

Problem 2

Find an integer solution of $34x + 19 y = 1$

Solution 2

We have 

34 = 19 + 15

Or $15 = 34 - 19\cdots(1)$

Now 19 = 15 + 4

Or $ 4 = 19 - 15\cdots(2)$

Now 15 = 4 * 3 + 3 

Or $3= 15 - 4 * 3\cdots(3)$

Now $4= 3 + 1$

Or $1 = 4-3\cdots(4)$

As we have reached 1 so they are co primes 

Now working backwards

1= 4-3 using (4)

= 4 - (15 - 4 * 3) using (3)

=  4 * 4 - 15

= (19-15) * 4 - 15 using (2)

= 19 * 4 - 15 * 5

= 19 * 4 - ( 34 - 19) * 5 using (1)

= 19 * 9 - 34 * 5

So we have a solution x = -5  and y = 9 and general solution x = -5 + 19t and y = 9 - 34 t with t over integers

  

Problem 3(this appeared in PRMO 2017 question 8 )

A pen costs Rs 11 and a note book costs Rs 13. Find the number of ways in which a person can spend exactly Rs 1000 to buy pens and notebooks.

Solution 3

Let the person buy x pens and y notebooks
So we have
11x + 13y = 1000

Now let us compute gcd of 11 and 13 by using Extended Euclidean Alogorithm

We have
 13 = 11 + 2
Or $2  = 13 - 11\cdots(1)$
11 = 2 * 5 + 1
Or $ 1= 11 - 2 *5\cdots(2)$
As we have reached 1 so this is the gcd and we can work backwards as
$1 = 11 - 2 *5$ using (2)
Or $1 = 11 - (13-11) *5$ using (1)
$ = 11 * 6 - 5 * 13$
So 1000 = 1000(11 * 6 - 5 * 13) = 11 * 6000 - 13 * 5000
To find general solution we have
x = 6000 - 13 t
And y = - 5000 + 11 t
x = 6000 - 13 t and x is positive so $13t < 6000$ or $ t < 462$
y = - 5000 + 11 t and y is positive so $11t > 5000$ or $t >454$

So there are 7 values of t (from 455 to 461) for which x and y both are positive and so there are 7 solutions

Problem 4(this appeared in PRMO 2016)

Solve in integers $35x + 63y + 45z=1$ where $| x |  < 9|$,   $| y |  < 5|$,  $| z |  < 7|$

Solution 4

Above can be written as $35x+ 9(7y + 5z) = 1$

That is $35x + 9m= 1$ and $7y + 5z = m$

Now for solving $35x+9m=1$

We have
$35 = 9 * 3 + 8$
Or $8- 35 - 9 * 3 \cdots(1)$
$ 9 = 8 +1$
Or $1 = 9-8\cdots(2)$
So we get 
$1= 9-8$  using (2)
$ = 9 - (35 - 9 * 3) = 9 * 4 - 35$
So x = - 1 and m = 4
Or general solution $x = - 1 + 9t$ and $m = 4 - 35t$
t = 0 gives x = - 1, m= 4  and t = 1 gives x = 8, m = -31 . these satisfy    $| x |  < 9|$
We need to solve d $7y + 5z = m$
For this get us find solution $7a + 5b = gcd(7,5)$
To solve the same
we have 7 = 5 + 2 
Or $2 - 7 -5\cdots(1)$
5 = 2 * 2 + 1
Or $1 = 5 - 2 * 2$ \cdots(2)
Now we have
$1 = 5 - 2 *2$ using (2)
$= - 5 - 2 *(7-5)$ using (1)
$= 3 * 5 - 2 *7$
So -2,3 is a solution of $7a + 5b = 1$

Based on the above let us solve for y,z for the values of m corresponding to different x

Case 1: x =  -1 , m = 4
We have $1 = 3 * 5 - 2 * 7$
Or $4= - 8 * 7 + 12 * 5$
This is a particular solution
So general solution
$4= -  (8+ 5p)  * 7 + (12 + 7p) * 5$
We have |12+7p| < 7 and |8+5p| < 5
To solve |12+7p| < 7 we have
- 7 < 12 + 7p < -5
Or -19 < 7p < - 7
p = -2 or -1 and this satisfies  

The above is met when p = -2 and - 1 and we have 
p = -2 gives $4 =  2 * 7 - 2 * 5$ giving solution set(-1,2,-2)
p = -1 gives $4=  -3 * 7 + 5 * 5$ giving solution set(-1,3,5)

Case 2:

Now for solving  x= 8 , m = -31
We have $1= -2 * 7 + 3 * 5$
Or $-31 = 62 * 7 - 93 * 5$
For general solution we have
$-31 = (62-5t) * 7 + (7t-93) * 5$
We must have  - 5 < 62- 5t  < 5
Or 5t < 67 and 57 < 5t giving t = 12 or 13
t =12 gives coefficient of 5 (that is z) = -9 which is outside the range
t =  13 fives y = -3 and z = -2 so solution (8,-3,-2)

So solution sets   (-1,2,-2), (-1,3,5),(8,-3,-2)
,