Saturday, August 17, 2019

elementary number theory - Bezout identity of 720 and 231 by hand impossible?

Is it possible to solve this by hand? Without using the Extended Euclidean Algorithm



We do the Euclidean algorithm and we get:



720 = 231 * 3 + 27



231 = 27 * 8 + 15




27 = 15 * 1 + 12



15 = 12 * 1 + 3



12 = 3 * 4 + 0



The GCD is 3.



We now isolate the remainders:




27 = 720 - 231 * 3



15 = 231 - 27 * 8



12 = 27 - 15 * 1



3 = 15 - 12 * 1



We proceed by substitution:




3 = 15 - 12 * 1



What now? How can we proceed when we have *1? There is no substitution possible?



Help! Thanks!

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...