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

# Application of Euclidian’s algorithm in Diophantine equation

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.

## Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...