-- Mar 20 In-Class Exercise Thread
Extended-Euclid(210, 858)
(d', x', y') = Extended-Euclid(858, 210 % 858 = 210) = (6, 12, -49)
(d, x, y) = (6, -49, 12 - floor(210/858)*-49) = (6, -49, 12)
return (6, -49, 12)
Extended-Euclid(858, 210)
(d', x', y') = Extended-Euclid(210, 858 % 210 = 18) = (6, -1, 12)
(d, x, y) = (6, 12, -1 - floor(858/210)*12) = (6, 12, -49)
return (6, 12, -49)
Extended-Euclid(210, 18)
(d', x', y') = Extended-Euclid(18, 210 % 18 = 12) = (6, 1, -1)
(d, x, y) = (6, -1, 1 - floor(210/18)*-1) = (6, -1, 12)
return (6, -1, 12)
Extended-Euclid(18, 12)
(d', x', y') = Extended-Euclid(12, 18 % 12 = 6) = (6, 0, 1)
(d, x, y) = (6, 1, 0 - floor(18/12)*1) = (6, 1, -1)
return (6, 1, -1)
Extended-Euclid(12, 6)
(d', x', y') = Extended-Euclid(6, 12 % 6 = 0) = (6, 1, 0)
(d, x, y) = (6, 0, 1 - floor(12/6)*0) = (6, 0, 1)
return (6, 0, 1)
Extended-Euclid(6, 0)
return (6, 1, 0)
<pre>
Extended-Euclid(210, 858)
(d', x', y') = Extended-Euclid(858, 210 % 858 = 210) = (6, 12, -49)
(d, x, y) = (6, -49, 12 - floor(210/858)*-49) = (6, -49, 12)
return (6, -49, 12)
Extended-Euclid(858, 210)
(d', x', y') = Extended-Euclid(210, 858 % 210 = 18) = (6, -1, 12)
(d, x, y) = (6, 12, -1 - floor(858/210)*12) = (6, 12, -49)
return (6, 12, -49)
Extended-Euclid(210, 18)
(d', x', y') = Extended-Euclid(18, 210 % 18 = 12) = (6, 1, -1)
(d, x, y) = (6, -1, 1 - floor(210/18)*-1) = (6, -1, 12)
return (6, -1, 12)
Extended-Euclid(18, 12)
(d', x', y') = Extended-Euclid(12, 18 % 12 = 6) = (6, 0, 1)
(d, x, y) = (6, 1, 0 - floor(18/12)*1) = (6, 1, -1)
return (6, 1, -1)
Extended-Euclid(12, 6)
(d', x', y') = Extended-Euclid(6, 12 % 6 = 0) = (6, 1, 0)
(d, x, y) = (6, 0, 1 - floor(12/6)*0) = (6, 0, 1)
return (6, 0, 1)
Extended-Euclid(6, 0)
return (6, 1, 0)
</pre>