Using euclid algorithm to find the …

Given integers,
595 and 252
Applying Euclid division algorithm to 595 and 252 we get,
595=252×2+91.........................................1

Now applying ,Euclid division algorithm to 252 and 91 we get,
252=91×2+70.....….………...........................2

Now applying Euclid division algorithm to 91 and 70,we get
91=70×1+21…...............................................3

Now applying Euclid division algorithm to 70 and 21 we get,
70=21×3+7...................................................4

Now applying Euclid division algorithm to 21 and 7 we get,
21=7×3+0......................................................5
The remainder at this stage is zero.
Hence HCF of 595 and 252 is 7.

eq1,eq2,eq3, and eq4 can be written as,
595-(252×2)=91..........................................6

252-(91×2)=70.............................................7

91-(70×1)=21...................................................8

70-(21×3)=7.....................................................9
Now eq9 we have,
(as we express HCF in the form of a equation that is the reason we start from eq9)
7=70-(21×3)
By putting eq8 in above equation we have,
7=70-(91-70×1)3

7=70-91×3+70×3

7=70×4-91×3
By putting eq7 in above equation we have,
7=(252-91×2)4-91×3

7=252×4-91×8-91×3

7=252×4-91×11
By putting eq6 in above equation we have,
7=252×4-(595-252×2)11

7=252×4-595×11+252×22

7=252×26-595×11

7=595(-11)+252(26)

7=595m+252n, where m=-11 and n=26.
Hence HCF of 595 and 252 is in the form of 595m+252n,where m=-11 and n=26.