Tuesday, 12 June 2018

elementary number theory - Extended Euclidean Algorithm As Row Operations

I am trying to find gcd(211,88) and gcd(26400,63300) and the smallest linear combination that gives the Greatest Common Divisor (a.k.a. gcd) .



I have been using the following algorithm



For gcd(211,88) I got:




211=1(211)+0(88)88=0(211)+1(88)35=1(211)2(88)18=2(211)+5(88)17=3(211)7(88)1=5(211)+12(88)0=88(211)211(88)



And the operations were:
R12R2,R22R3,R3R4,R4R5,R517R6



What is the gcd ? the one before 0?



In the case of gcd(26400,63300) or in the case that we have one or two negative numbers, how do we use the algorithm?

No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...