-- Apr 13 In-Class Exercise Thread
i = 1
m_1 = 42/2 = 21
call EE(21, 2)
call EE(2, 1)
call EE(1, 0) -> return (1, 1, 0)
EE(2, 1) -> return (1, 0, 1 - floor(2/1) * 0) = (1, 0, 1)
EE(21, 2) -> return (1, 1, 0 - floor(21/2) * 1) = (1, 1, -10)
21 * 1 - 10 * 2 = 1 -> 21* 1 = 1 mod 2
t_1 = 21^-1 = 1 mod 2
c_1 = 21 * 1 = 21
i = 2
m_2 = 42/3 = 14
call EE(14, 3)
call EE(3, 2)
call EE(2, 1)
call EE(1, 0) -> return (1, 1, 0)
EE(2, 1) -> return (1, 0, 1 - floor(2/1) * 0) = (1, 0, 1)
EE(3, 2) -> return (1, 1, 0 - floor(3/2) * 1) = (1, 1, -1)
EE(14, 3) -> return (1, -1, 1 - floor(14/3) * -1) = (1, -1, 5)
14 * -1 + 5 * 3 = 1
t_2 = (-14)^-1 = 1 mod 3
c_2 = -14 * 1 = -14
i = 3
m_3 = 42/7 = 6
call EE(6, 7)
call EE(7, 6)
call EE(6, 1)
call EE(1, 0) -> return (1, 1, 0)
EE(6, 1) -> return (1, 0, 1 - floor(6/1) * 0) = (1, 0, 1)
EE(7, 6) -> return (1, 1, 0 - floor(7/6) * 1) = (1, 1, -1)
EE(6, 7) -> return (1, -1, 1 - floor(6/7) * -1) = (1, -1, 2)
6 * -1 + 2 * 7 = 8 = 1 mod 7
t_3 = (-6)^-1 = 1 mod 7
c_3 = -6 * 1 = -6
a = 1 * 21 - 2 * 14 - 5 * 6 = 21 - 28 - 30 = -37 mod 42 = 5 mod 42
check 5 = 1 mod 2, 5 = 2 mod 3, 5 = 5 mod 7
i = 1
m_1 = 42/2 = 21
call EE(21, 2)
call EE(2, 1)
call EE(1, 0) -> return (1, 1, 0)
EE(2, 1) -> return (1, 0, 1 - floor(2/1) * 0) = (1, 0, 1)
EE(21, 2) -> return (1, 1, 0 - floor(21/2) * 1) = (1, 1, -10)
21 * 1 - 10 * 2 = 1 -> 21* 1 = 1 mod 2
t_1 = 21^-1 = 1 mod 2
c_1 = 21 * 1 = 21
----
i = 2
m_2 = 42/3 = 14
call EE(14, 3)
call EE(3, 2)
call EE(2, 1)
call EE(1, 0) -> return (1, 1, 0)
EE(2, 1) -> return (1, 0, 1 - floor(2/1) * 0) = (1, 0, 1)
EE(3, 2) -> return (1, 1, 0 - floor(3/2) * 1) = (1, 1, -1)
EE(14, 3) -> return (1, -1, 1 - floor(14/3) * -1) = (1, -1, 5)
14 * -1 + 5 * 3 = 1
t_2 = (-14)^-1 = 1 mod 3
c_2 = -14 * 1 = -14
----
i = 3
m_3 = 42/7 = 6
call EE(6, 7)
call EE(7, 6)
call EE(6, 1)
call EE(1, 0) -> return (1, 1, 0)
EE(6, 1) -> return (1, 0, 1 - floor(6/1) * 0) = (1, 0, 1)
EE(7, 6) -> return (1, 1, 0 - floor(7/6) * 1) = (1, 1, -1)
EE(6, 7) -> return (1, -1, 1 - floor(6/7) * -1) = (1, -1, 2)
6 * -1 + 2 * 7 = 8 = 1 mod 7
t_3 = (-6)^-1 = 1 mod 7
c_3 = -6 * 1 = -6
----
a = 1 * 21 - 2 * 14 - 5 * 6 = 21 - 28 - 30 = -37 mod 42 = 5 mod 42
check 5 = 1 mod 2, 5 = 2 mod 3, 5 = 5 mod 7