Question

Find the greatest common divisor of 624 and 441 by using the Eucledian algorithm and
express it as 624x+441y, where x and y are integers.​

Answer 1

Given : 624 and 441

To find :  greatest common divisor and express it as 624x+441y,

Solution:

greatest common divisor or HCF - hhighest common factor are same thing

624 = 441 * 1  +  183

441 = 183 * 2 +  75

183 = 75 * 2  + 33

75  = 33 * 2  + 9

33 = 9 * 3  + 6

9  = 6 *  1 +  3

6  = 3 * 2

3 is the HCF

9  = 6 *  1 +  3

=> 3  = 9  - 6 * 1

=> 3 =   9 -  (33 - 9 * 3) * 1

=> 3 =   9 *4   - 33

=> 3 =   (75 - 33 * 2) * 4  - 33

=> 3 =   75 * 4  -  33*9

=> 3  = 75 * 4  - ( 183 - 75 * 2) 9

=>  3 = 75 *   22  - 183 * 9

=> 3 =  (441 - 183 * 2) * 22 - 183 * 9

=> 3 =  441 * 22  -  183 * 53

=> 3 = 441 *22 -  (624 - 441 ) * 53

=> 3 = 441 * 75 - 624 * 53

=>3 = 624 (-53) + 441 * 75

3 = 624x+441y

x = - 53

y = 75

Learn more:

find the HCF of 60 and 405 and Express it in the form of 60q + 405r ...

https://brainly.in/question/17303043

find the hcf of 75 and 243 using Euclid division algorithm express in ...

https://brainly.in/question/9266837