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