Triple diophantine

Number Theory Level 4

Using Euclidean Algorithm, find the solution to the given equation

(198, 288, 512) = 198 x + 288 y + 512 z

Let the value of x + y + z = S . Write your answer as S .

Note :

1) (x, y, z) represents the GCD of x, y and z. 2) Though there can be many solutions of x, y and z. But the first solution that comes using Euclidean Algorithm is the answer.

The answer is 55.

1 solution

Saqib M
Nov 21, 2014

Put d = GCD (198, 288).

Since GCD ( GCD (a, b), c) = GCD (a, b, c), we will find integers u and v for which GCD ( d , 512) = du + 512 v

Using Euclidean Algorithm,

288 = $1 \times 198$ + 90
198 = $2 \times 90$ + 18
90 = $5 \times 18$ + 0

So, d = 18.

To represent 18 as a linear combination of 198 and 288, we write the above equations backward -

$18 = 198 - 2 \times 90$
$= 198 - 2 \times (288 - 198)$
$= 3 \times 198 - 2 \times 288$

Now we have to find (18, 512) and then represent it in the form of 18 u +512 v

$512 = 28 \times 18 + 8$
$18 = 2 \times 8 + 2$

So (512, 18) = 2. Now,

$2 = 57 \times 18 - 2 \times 512$

Putting the value of 18,

$2 = 171 \times 198 - 114 \times 288 - 2 \times 512$

Thus, x = 171, y = - 114, z = - 2 and S = 55

Triple diophantine

The answer is 55.

1 solution

0 pending reports