2378x + 1769y = ged (2378,1769)

i. To find ged (2378, 1769)

let a=2378, b=1769

by using Euclidean Algorithm,

a=2378 = $\ (1\times1769)$ + 609 -----------------------1

b=1769 = $\ (2\times609)$ + 551 -------------------------2

609= $\ (1\times551)$ + 58 --------------------------------3

551= $\ (9\times58)$ + 29 --------------------------------4

58= $\ (2\times29)$ + 0 --------------------------------5

$\therefore$ ged (2378, 1769) = 29

Now we find the value of X & y,

let a = 2378 and b=1769 as a linear combination of a and b

i. 609 = $a-b \ \ \ \ \ \ from$ equation 1

ii 559 = $b-2(a-b)\ \ \\ \ \ from$ 2 and i

= 3b-2a

iii 58 = (a-b)-(3b-2a) $ \ \ \ \ \ \ \ $ [by 3, i, & ii ]

= 3a-4b

iv. 29= (3b-2a) - 9 (3a-4b) $\ \ \ \ \ \ \ \ \ $ [by 4, ii & iii]

= 39b- 29a

= -29a +39b

We obtain -29a +39b = (a,b)

Therefore,

x=-29, y=39 is a solution to the equation 2378x+1769y =ged (2378, 1769)

other solution are,

$\ x= -29 + \frac{1769}{29} \times t$

$\ y= 39 - \frac{2378}{29} \times t$

other solution are,

x= -29+61t & y = 39-82t

where 't' is any integer.