Post you solutions to the Mar 20 In-Class Exercise to this thread.

Best,

Chris

'''Show step-by-step what Extended-Euclid(210, 858) would compute.'''

``

'''Solution:''' (6, -49, 12) : 6 = (-49)*210 + 12*858

Extended-Euclid(210, 858) --> return (6, -49, -12 - \lfloor\frac{210}{858}\rfloor*-49) = (6, -49, 12)

Extended-Euclid(858, 210) --> return (6, 12, -1 - \lfloor\frac{858}{210}\rfloor*12) = (6, 12, -49)

Extended-Euclid(210, 18) --> return (6, -1, 1 - \lfloor\frac{210}{18}\rfloor*-1) = (6, -1, 12)

Extended-Euclid(18, 12) --> return (6, 1, 0 - \lfloor\frac{18}{12}\rfloor*1) = (6, 1, -1)

Extended-Euclid(12, 6) --> return (6, 0, 1 - \lfloor\frac{12}{6}\rfloor*0) = (6, 0, 1)

Extended-Euclid(6, 0) --> return (6, 1, 0)

Ext-Euclid(210,858)

210x+858y = d = gcd(210,858)

858x' + 210y'= gcd(858, 210) = 6

143x' + 35y' = 1

gcd(143, 35) = 0

Recursive call (from bottom to up):

1. Extended-Euclid(6, 0) (6,1,0)
2. Extended-Euclid(12,6) (6,0,1)
3. Extended-Euclid(18,12) (6,1,-1)
4. Extended-Euclid(210,18) (6,-1,12)
5. Extended-Euclid(858,210) (6,12,-49)
6. Extended-Euclid(210,858) (6,-49,12)

Result: (6,-49,12)

<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>

Extended_Euclid(858, 210) 858 = 210 * 4 + 18 Extended_Euclid(210, 18) 210 = 18 * 11 + 12 Extended_Euclid(18, 12) 18 = 1 * 12 + 6 Extended_Euclid(12, 6) 12 = 2 * 6 + 0 Extended_Euclid(6, 0) returns(6, 1, 0) (d', x', y') = (6, 1, 0) (d, x, y) = (d', y', x' - floor(12/6) * y') = (6, 0, 1) returns (6, 0, 1) (d', x', y') = (6, 0, 1) (d, x, y) = (d', y', x' - floor(18, 12) * y') = (6, 1, -1) returns (6, 1, -1) (d', x', y') = (6, 1, -1) (d, x, y) = (d', y', x' - floor(210/18) * y') = (6, -1, 1 - 11 * (-1)) = (6, -1, 12) returns (6, -1, 12) (d', x', y') = (6, -1, 12) (d, x, y) = (d', y', x' - floor(858/210) * y') = (6, 12, -1 - 4 * 12) = (6, 12, -49) returns(6, 12, -49)

Extended_Euclid(210, 858) -> (6, -49, 12 - floor(210 / 858) * (-49)) -> return (6, -49, 12)

Extended_Euclid(858, 210) -> (6, 12, 1 - floor(858 / 210) * 12) -> return (6, 12, -49)

Extended_Euclid(210, 18) -> (6, -1, 1 - floor(210 / 18) * (-1)) -> return (6, -1, 12)

Extended_Euclid(18, 12) -> (6, 1, 0 - floor(18 / 12) * 1) -> return (6, 1, -1)

Extended_Euclid(12, 6) -> (6, 0, 1 - floor(12 / 6) * 0) -> return (6, 0, 1)

Extended_Euclid(6, 0) -> return (6, 1, 0)

Final solution: (6, -49, 12)

EE(210,858)->(6,-49,12-floor(210/858)*(-49))=(6,-49,12) EE(858,210)->(6,12,-1-floor(858/210)12)=(6,12,-49) EE(210,18)->(6,-1,1-floor(210/18)-1)=(6,-1,12) EE(18,12)->(6,1,0-floor(18/12)*1)=(6,1,-1) EE(12,6)->(6,0,1-floor(12/6)*0)=(6,0,1) EE(6,0)->(6,1,0)