BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Friday , July 28 2017
Home / Elementary Number Theory / Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –

a) 6x + 57y = 22

b) 33x + 14y = 115

c) 14x + 35y = 93

Solution: (a) Applying the Euclidian’s algorithm to the evaluation of gcd(51, 6), we find

51 = 8.6 + 3

6 = 2.3 + 0

Hence gcd (51, 6) = 3

Since 3 ∤ 22 , so the given equation cannot be solved.

(b) Applying the Euclidian’s algorithm to the evaluation of gcd(33, 14), we find

33 = 2.14+5

14 = 2.5 + 4

5 = 1.4 + 1

4 = 4.1 + 0

Hence, gcd(33, 14) = 1.

Since 1 | 115, so the given equation can be solved.

(c) Applying the Euclidian’s algorithm to the evaluation of gcd(14, 35), we find

35 = 2.14 + 7

7= 2.7 + 0

Hence gcd (35, 14) = 17

Since 7 ∤ 93 , so the given equation cannot be solved.

Problem-2: Determine all solutions in the integers of the following Diophantine equations.

(a) 56x + 72y = 40

(b) 24x + 138y = 18

(c) 221x + 35y = 11

Solution:

(a) Applying the Euclidian’s algorithm to the evaluation of gcd(56, 172) , we find

72 = 1.56 + 16

56 = 3.16 + 8

16 = 2.8 + 0

Hence the gcd(56, 172) = 8

Since 8| 40, a solution of this equation exists. To obtain the integer 8 as a linear combination of 56 and 72. We work backwards through the above calculation as follows

8 = 56 – 3.16

= 56 – 3(72 – 1.56)

= 56 – 3.72 + 3.56

= 4.56 – 3.72

Multiplying this relation by 5 , we get

40 = 8.5 = 5(4.56 – 3.72)

= 20.56 – 15.72

= 20.56 + (– 15 ). 72

So that, x = 20 and y =  – 15

Hence x and y provides one solution to the Diophantine equation.

All other solutions are expressed by,

x = 20 + (72/8)t = 20 + 9t

y =  – 15 – (56/8)t = – 15 – 7t

Here t is an integer.

(b)

Solution: Applying the Euclidian’s algorithm to the evaluation of gcd(24, 138) , we find

138= 5.24 + 18

24= 1.18 + 6

18 = 3.6 + 0

Hence the gcd(24, 138) = 6

Since 6| 18, a solution of this equation exists. To obtain the integer 8 as a linear combination of 24 and 138. We work backwards through the above calculation as follows

6 = 24 – 1.18

= 24 – 1(138 – 5.24)

= 24 – 1.138 + 5.24

= 6.24 + (– 1). 138

Multiplying this relation by 3 , we get

18 = 3.6 = 3(6.24 + (–1). 138

18 . 24 + (–3). 138

So that, x = 18 and y =  – 3

Hence x and y provides one solution to the Diophantine equation.

All other solutions are expressed by,

x = 18 + (138/6)t = 18 + 23t

y =  – 3 – (24/6)t = – 3 – 4t

Here t is an integer.

(c)

Solution: Applying the Euclidian’s algorithm to the evaluation of gcd(221, 35) , we find

221= 6.35 + 11

35= 3.11 + 2

11 = 5.2 + 1

2  = 2.1 + 0

Hence the gcd(221, 35) = 1

Since 1| 11, a solution of this equation exists. To obtain the integer 8 as a linear combination of 221 and 35. We work backwards through the above calculation as follows

1 = 11 – 5.2

=11 – 5(35– 3.11)

= 11– 5.35– 15.11

= 16.11 – 5. 35

= 16(221 – 6.35) – 5.35

= 16.221 – 96.35 – 5.35

= 16.221 – 101.35

Multiplying this relation by 11, we get

11 = 1.11 = 11(16.221 – 101.35)

= 176.221 + (– 1111) . 35

So that, x = 176and y =  – 1111

Hence x and y provides one solution to the Diophantine equation.

All other solutions are expressed by,

x = 176 + (35/1)t = 176 + 35t

y =  – 1111 – (221/1)t = – 1111 – 221t

Here t is an integer.

Problem-3: Determine all solutions in the positive integer of the following Diophantine equation-

(a) 18x + 5y = 48

(b) 54x + 21y = 906

(c) 123x + 360y = 99

(d) 158x – 57y = 7

Solution: (a)

Solution: Applying the Euclidian’s algorithm to the evaluation of gcd(18, 5) , we find

18= 3.5+3

5 = 1.3 + 2

3 = 1.2 + 1

2 = 1.2 + 0

Hence the gcd(18, 5) = 1

Since 1| 48, a solution of this equation exists. To obtain the integer 8 as a linear combination of  18 and 5. We work backwards through the above calculation as follows

1 = 3 – 1 .2

=3 – 1(5 – 1.3)

= 3 – 1.5 + 1.3

= 2.3 – 1.5

= 2(18 – 3.5) – 1.5

= 2.18 – 6.5 – 1.5

= 2.18 – 7.5

Multiplying this relation by 48, we get

48 = 1.48 = 48(2.18 – 7.5)

= 96.18 – 336 . 5

= 96. 18 + (–  336) .5

So that, x =96 and y =  – 336

Hence x and y provides one solution to the Diophantine equation.

All other solutions are expressed by,

x = 96 + (18/1)t = 96 + 18t

y =  – 336 – (5/1)t = – 336 – 5t

Here t is an integer.

Remain Problems reader will solved as according previous solution.

Application of Euclidian’s algorithm in Diophantine equation

Which of the following Diophantine equations cannot be solved – a) 6x + 57y = ...