I'm confused about how to do the extended algorithm. For example, here's the gcd part
gcd(8000,7001)
8000=7001⋅1+9997001=999⋅7+8999=8⋅124+78=7⋅1+17=1⋅7+0gcd(8000,7001)=1
Now, the extended algorithm
1=8−1⋅7=8−1⋅(999−8⋅124)=−1⋅999+8⋅125
How do you get this 8*125 from the previous line?
Answer
By the distributive law 8 −1(a−b)=−a+b ⏞−1⋅(999−8⋅124)= 8⋅1−999+8⋅124= 8⋅125−999 by 124+1=125
This "back-substitution method" for the extended gcd is notoriously error-prone. Simpler to compute and easier to remember is the method described here., where we keep track of each remainder's expression as a linear combination of the gcd arguments. Executing that algorithm yields
8000107001019991−18−78−1876−1001
where each line a b c means that a=8000b+7001c. Therefore
1=−876⋅8000+1001⋅7001
The linked post described the algorithm in great detail, in a way that is easy to remember.
Here is another example computing gcd(141,19), with the equations written explicitly
[[1]] 141 = 1⋅141+ 0⋅19[[2]] 19 = 0⋅141+ 1⋅19[[1]]−7[[2]]→[[3]] 8 = 1⋅141− 7⋅19[[2]]−2[[3]]→[[4]] 3 =−2⋅141+15⋅19[[3]]−3[[4]]→[[5]]−1 = 7⋅141−52⋅19
No comments:
Post a Comment