Find HCF of 4052 and 420. Also find x and y if HCF =4052x + 420y
Answers
Answer:
4 = 17(4052) - 164(420)
where x = 17 and y = -164
Step-by-step explanation:
We are given that
4052 and 420
Since by prime factorization
4052 = 2 × 2 × 1013
420 = 2 × 2× 3 × 5 × 7
Common factors of 4052 and 420 = 2 × 2
we know that
H.C.F = Product of common factors = 2 × 2 = 4
Thus
H.C.F = 4
And
See that
4052 = 420×9 + 272 ⇒ 272 = 4052 - 420(9)
420 = 272×1 + 148 ⇒ 148 = 420 - 272
272 = 148×1 + 124 ⇒ 124 = 272 - 148
148 = 124×1 + 24 ⇒ 24 = 148 - 124
124 = 24×5 + 4 ⇒ 4 = 124 - 24(5)
Now
4 = 124 - 24×5
= 124 - (148 - 124)×5 ∵ 24 = 148 - 124
= 6(124) - 5(148)
= 6(272 - 148) - 5(148) ∵ 124 = 242 - 148
= 6(272) - 11(148)
= 6(272) - 11(420 - 272) ∵ 148 = 420 - 272
= 17(272) - 11(420)
= 17(4052 - 420×9) - 11(420) ∵ 272 = 4052 - 420(9)
= 17(4052) - 153(420) - 11(420)
= 17(4052) - 164(420)
Thus
4 = 17(4052) - 164(420)
where x = 17 and y = -164