Question

Priva tries to find the highest common factor of a
and b using Euclid's division algorithm (EDA).
In one of her steps she divides 2419 by 574
Find the highest common factor of a and b.
HCF(a,b) =

Answer 1

$\underline { \blue { Euclid's \: Division \:Algorithm :}}$

Given positive integers 'a' and 'b' , there exists unique pair of integers 'q' and 'r' satisfying

a = bq + r , 0 ≤ r < b

$Here, a = 2419 \: and \: b = 574$

$When \: 2419 \: divided \: by \:574 , \: the \\remainder \: is \: 123 \: we \:get$

$\pink { 2419 = 574 \times 4 + 123 }$

$Now , \:considered \: division\: of \: 574 \:with \\remainder \:123 \: and \: apply \:the \: division \\lemma \: to \:get$

$574 = 123 \times 4 + 82$

$\blue { Remainder \neq 0 . \: Apply \: lemma \:again }$

$123 = 82 \times 1 + 41$

$82 = \orange {41} \times 2 + \red{0}$

$The \: Remainder \:has \:now \: become \:zero,\\So, \:our \: procedure \:stops .$

$Since, \: the \: divisor \:at \: this \:stage \\is \: \green { 41}$

Therefore.,

$\red { H.C.F \:of \: (2419 , 574 )} \green {= 41 }$

•••♪

Answer 2

Answer:

&hhhhghcicuhhhhhgfyxufufgucgfffff