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)
, 

Section 007) Extended Euclidean algorithm

Introduction

The Extended Euclidean algorithm is an extension to the Euclidean algorithm and computes, in addition to the greatest  common divisor of integers a and b, also the coefficients of Bezout's identity  which are integers x and y such that

ax + by = gcd(a,b).

The gcd of and b is mentioned in https://kali-mathlessions.blogspot.com/2016/09/section-002-gcd.html


In case of Euclidean algorithm we are interested in only the remainder and not the quotients. Because we are interested in only the value of gcd(a,b) and not the quotients a and b, But in  Extended Euclidean algorithm as we are interested in a and b so we need to keep the quotients and these quotients are used to compute the a and b. This is illustrated as below for the same example for which we had computed the gcd in the gcd chapter.

In both cases we proceed by succession of divisions.

Outline of solution

We provide the outline of the solution here

Llet $r_0 = a$ and $r_1=b$ and we have values computed upto $r_n$ then we compute
$r_{n+1} = r_{n-1} - m_{n+1}  * r_n\cdots(1)$ and
We repeat the steps until we get  $r_{n+1} = 0$
Then $r_n$ is the gcd
Then we repeat using (1) and replacing $r_i$  by combination of $r_{i-1}$ and $r_{i-2}$ for i for i going From n down to 3. and thus we get the result

We wind it by providing an example

Problem 1 

Compute a ,b for GCD(1001,104)

Solution 1

 We have

1001 = 104*9 + 65 so $65 = 1001 - 104 *9 \cdots (1)$ 

104 = 65*1 + 39 so $39 = 104 -65 \cdots (2)$ 
 65 = 39*1 + 26  so $26 = 65 - 39 \cdots (3)$ 
 39 = 26*1 + 13 so  so $13 = 39 - 26 \cdots (4)$ 
 26 = 13*2 + 0

As the remainder is zero so we have the GCD 13.

Now $13 = 39-26$  (using (4))

$= 39 - (65-39)$ (using (3))

$= 2 * 39 - 65$

$= 2 * (104-65) - 65 $ (using (2))

$= 2 * 104 - 3 * 65$

$= 2 * 104 - 3 * (1001 - 104 *9)$ using (1)

$= 29 * 104 - 3 * 1001$

$= 1001 * (-3) + 104 * 29 $   (to put in form of ax + by)

So we get $GCD(1001,104)=13= -3 * 1001 + 29 * 1001$

So  we have for a = 1001 and b = 104 the value of gcd(a,b) = 13, x = -3 and y = 29

Section 006) Chinese Remainder Theorem

If m and n are positive integers which are relatively prime i.e. GCD(m , n ) = 1. Then there exists an integer N such that

$N \equiv a (\mod m)$
$N \equiv b (\mod n)$

Moreover $N \equiv x (\mod mn)$ where x is unique.

This can be proved  but I am not specifying the prrof here

This can be generalized to n  integers.

$N \equiv a_i (\mod m_i)$ where i varying from 1 to n and $m_i$ are pairwise relatively co-prime then there exists x such that

$x = \sum_{i=1}^n\frac{a_ib_iM}{m_i}$ where M is product of all $m_i$ and $b_i$ is determined from M as below

$b_i\frac{M}{m_1}  \equiv 1 \mod m_1$

We illustrate the same with an example below

Problem 1

What would be the least positive . which give the remainder 1 when divided by 7,2 when divided by 9 and 11 when divided by 11 

Solution 1

Let the number be x 

We have remainder 1 when divided by 7,2 when and 3 when divided by 11

So

$x=1\pmod 7\cdots(1)$
$x=2\pmod 9\cdots(2)$
$x=3\pmod {11}\cdots(3)$

Now 7 ,9 and 11 are pair wise co-prime 

So M= 7 * 9 * 11 = 693

So $x = 1 a_1b_1 + 2 a_2b_2 + 3 a_3b_3 \pmod {693}$ as M = 693 

Now let us compute $a_1,a_2,a_3$


$a_1 = \frac{M}{7}  = \frac{693}{7} = 99$
$a_2 = \frac{M}{9}  = \frac{693}{9} = 77$
$a_3 = \frac{M}{11}  = \frac{693}{11} = 63$

Now we need to compute $b_1,b_2,b_3$ such that

$99b_1 =1   \pmod 7$ or $b_1 =1  \pmod 7$ or $b_1 = 2$

$77b_2 =1   \pmod 9$ or $5b_2=1   \pmod 9$ or $b_2 = 2$
  
$63b_3 = 1 \pmod {11}$  or $8b_3 =1 \pmod {11}$ so $b_3 = 7$ as $ 7 * 8 = 56 = 1 \pmod {11}$

I have mentioned the above in hit and trial method because the co-coefficients are low and they can be computed using extended euclidean algorithm as below.

Let us try  the $3^{rd}$ part i.e.$8b_3 =1 \pmod {11}$

That is solve  $8x =1 \pmod {11}$

Or $8x= 1 + 11y$ 

We need to  compute $ 1= 8a + 11b$ where b is negative then a is the inverse of 8

To compute a ,b we have

$11 = 1 * 8 + 3$

So $3 = 11 -8$

$8 = 3 * 2 + 2$ or $2 = 8- 3 * 2 = 8- 2 * (11-8) = 3 * 8 - 2 * 11$

$1 = 3 -2 = (11-8) - ( 3 * 8 - 2 * 11) = 3 * 11 - 4 * 8$

We have found $1 = 8a + 11 b$  where $b = 3$ which is positive

We need to convert it to positive

Knowing $8a + 11 b = 8(a+11t) + 11(b-8t)$ identity if we add 8 to b and subtract 11 from a we get

$1 = 8(-4 +11) + 11(3 -8) = 7 * 8 - 5 * 11$

So $8 * 7  =1 \pmod {11}$

Hence 7 is inverse of 8  

So $x = 1 * 99 * 1 + 2 * 77 * 2 + 3 * 63 * 7 \pmod {693} = 1730 \pmod {693}$

$= 344 \pmod {693}$

So x if of the form $693n + 344$  or lowest x = 344


Problem 2

Find all integers that leave a remainder 1 when divided by either 2 or 5 but divisible by 3.

Solution 2

Let the number be x 

We have remainder 1 when divided by 2 or 5 but divisible by 3

So

$x=1\pmod 2\cdots(1)$
$x=1\pmod 5\cdots(2)$

$x=0\pmod 3 \cdots(3)$

we can combine (1) and (2) are remainders are same to have
$x=1\pmod 10 \cdots(4)$

now we need to solve the following

$x=0\pmod 3 \cdots(5)$

$x=1\pmod {10} \cdots(6)$

we shall use CRT as 3 and 10 are coprimes

M = 3 * 10 = 30

$a_1 = \frac{30}{3}  = 10$
$a_2 = \frac{30}{10}  =3$

Now we need to compute $b_1,b_2,b_3$ such that

$10b_1 =1   \pmod 3 $ or $b_1 =1  \pmod 3$ or $b_1 = 1$ (actually we need not compute as coefficient = 0)

$3b_2 =1   \pmod {10} $ or $b_2=7   \pmod {10}$ or $b_2 = 7$

so the number  = $0 * 10 * 1 + 1 *3 * 7 = 21  \pmod{30}$ 
  

Section 005) Pigeonhole Principle

Introduction

Pigeonhole principle simply states that if n+1 pigeons occupy n containers then one container shall have at least 2 pigeons.

As an example if you have socks of 2 colors and you pick 3 socks then at least 2 socks shall be of same color

If there are 13 persons in a room then 2 persons are born in the same month.

We now solve a couple of problems based on Pigeonhole principle

Problem  1

Show that inside  a square of radius 2 if we have 5 points then there are 2 points distance between them is less than $\sqrt{2}$.

Solution 1

Divide the square into 4 squares of size 1. As we have 5 points in 4 squares(edges includes) there are at least 2 points in one square. distance between 2 points inside the square is less than $\sqrt{2}$


Problem  2

 If you pick 51 numbers from the numbers 1 to 100 then there are 2 numbers whose sum is 101.

Solution 2

We can make 50 sets (1,100), (2,99), (3, 98) .... (50,51).

Now if we chose 51 numbers from the above 50 sets then 2 numbers must belong to same  set and and the sum shall be 101.

Section 004) Principle of Mathematical Induction

Introduction 

Principle of Mathematical induction (in short also known as PMI) is a method for proving a
proposition.  This consists of 2 steps the $1^{st}$ step is called the base case (also called basis)
and the $2^{nd}$ step is called induction step.

To prove by mathematical induction we have a hypothesis and then prove the hypothesis. The hypothesis is called induction hypothesis.They are explained below.

Steps  In Principle of Mathematical Induction 

In PMI the 2 steps are
Base step: This is true for some starting value say n. Typically but not always n = 1.
Induction step: Say this is true for all $n <=k$. Then it is true for k+ 1.
Combining the above 2 we prove it by mathematical induction.

There are two principles of mathematical induction

1st Principle of Mathematical Induction

In case the inductive step is based on the last value only then it is the 1st  Principle of
Mathematical Induction.

2nd Principle of Mathematical Induction

If it is based on more than one value then this is called 2nd Principle of Mathematical Induction.
This is also known as Principle of Strong Mathematical Induction as it is based on k and k-1 (or more than one value).

Proof  by Principle of Mathematical Induction

To prove by Principle of Mathematical Induction both the steps need to be proved. In absence of any one the proof is incomplete and hence is invalid.

This is demonstrated below how the proof by induction can be wrong unless applied properly.

To illustrate this, Joel E. Cohen proposed the following argument, which purports to prove by
mathematical induction that all horses are of the same color.

Base case: In a set of only one horse, there is only one color.

Inductive step: Assume as induction hypothesis that within any set of n horses, there is only
one color. Now look at any set of n + 1 horses. Number them: 1, 2, 3, ..., n, n + 1. Consider
the sets {1, 2, 3, ..., n} and {2, 3, 4, ..., n + 1}. Each is a set of only n horses, therefore
within each there is only one color. But the two sets overlap, so there must be only one color
among all n + 1 horses.

The base case n = 1 is trivial (as any horse is the same color as itself), and the inductive step
is correct in all cases $n > 1$. However, the logic of the inductive step is incorrect for n = 1,
Because the statement that "the two sets overlap" is false (there are only n + 1 = 2 horses prior
to either removal, and after removal the sets of one horse each do not overlap).

Hence the principle of induction has not been applied correctly and hence incorrect conclusion.

Here we provide couple of examples

Problem 1

Using PMI prove that $x^2+3x+3$ is a factor of $(x+1)^{n+1} + (x+2)^{2n-1}$
for integer $n >= 1$

Solution 1

n =1 gives $(x+1)^{n+1} + (x+2)^{2n-1} = (x+1)^2 + (x+2) = x^2 + 2x + 1 + x + 2 = x^2 + 3x + 3$ divisible

So the 1st step that is base step is proved

Let it be true for n = k.

We need to prove for n= k+ 1
Let $f(k) = (x+1)^{k+1} + (x+ 2)^{2k- 1}$
So $f(k+1) = (x+1)^{k+2} + (x+2)^{2k+ 1}$
$= (x+1)(x+1)^k + (x+2)^2 *(x+2)^{2k-1}$
$= (x+1)(x+1)^k + (x^2+4x + 4) *(x+2)^{2k-1}$
$= (x+1)(x+1)^k + (x + 1 + x^2+3x + 3) *(x+2)^{2k-1}$
$= (x+1)(x+1)^k + (x + 1)(x+2)^{(2k-1} + (x^2+3x + 3) *(x+2)^{2k-1}$
$= (x+1)[(x+1)^k + (x+2)^{2k-1}] + (x^2+3x + 3) *(x+2)^{2k-1}$
$= (x+1) f(k) + (x^2+3x + 3) *(x+2)^{2k-1}$

As both terms are divisible by $x^2+3x+3$ so f(k+1) is divisible by $x^2+3x+3$

So step of induction is proved

Hence proved as we have proved both the base step and induction step to be true.

Problem 2

Suppose x is a real number  and $x + \frac{1}{x}$ is an integer
Prove for all $n > 1, x^n + \frac{1}{x^n}$ is an integer.

Solution 2

$x+ \frac{1}{x} = n$ Say n integer (given)
So $(x+ \frac{1}{x})^2 = n^2$
$x^2 + \frac{1}{x^2} = n^2-2$ is an integer
So true for 1 and true for 2
Let it be true for upto k
Now $x^k+ \frac{1}{x^k}$
$(x^k+ \frac{1}{x^k})(x+ \frac{1}{x})$
$= (x^{k+1} + \frac{1}{x^{k-1}}) + x^{k-1} + \frac{1}{x^{k+1}}$
So $(x^{k+1} + \frac{1}{x^{k+ 1}})= (x^k+ \frac{1}{x^k})(x+ \frac{1}{x})- (x^{k-1} + \frac{1}{x^{k-1}})$
If it is true for all n upto k so RHS is integer then LHS is integer so for n = k+ 1 it is an ingeger so the
induction step is proved
Hence proved