-- Apr 6 In-Class Exercise Thread

Extended-Euclid(3003, 182)
(d', x', y') = Extended-Euclid(182, 91)
(d', x', y') = Extended-Euclid(91, 0)
b == 0 : returns (91, 1, 0) 
 
Hence, (d', x', y') = (91, 1, 0)
returns  (91, 0, 1)
(d', x', y') = (91, 0, 1)
returns (91, 1, -16)
Final: (91, 1, -16)

<pre> Extended-Euclid(3003, 182) (d', x', y') = Extended-Euclid(182, 91) (d', x', y') = Extended-Euclid(91, 0) b == 0 : returns (91, 1, 0) Hence, (d', x', y') = (91, 1, 0) returns (91, 0, 1) (d', x', y') = (91, 0, 1) returns (91, 1, -16) Final: (91, 1, -16) </pre>

-- Apr 6 In-Class Exercise Thread

((resource:20220410_194631.jpg|Resource Description for 20220410_194631.jpg))

-- Apr 6 In-Class Exercise Thread

((resource:In-Class.jpg|Resource Description for In-Class.jpg))

-- Apr 6 In-Class Exercise Thread

((resource:apr6.jpeg|Resource Description for apr6.jpeg))

-- Apr 6 In-Class Exercise Thread

((resource:IMG-6854.jpg|Resource Description for IMG-6854.jpg))

-- Apr 6 In-Class Exercise Thread

					182 % 91 = 0
					(d', x', y') = Extended-Euclid(91, 0)
										return (91, 1, 0)
					(d', x', y') = (91, 1, 0)
					(d, x, y) = (91, 0, 1 - 2*0)
					(d, x, y) = (91, 0, 1)
					return (91, 0, 1)

Extended-Euclid(3003, 182) 3003 % 182 = 91 Therefore (d', x', y') = Extended-Euclid(182, 91) 182 % 91 = 0 (d', x', y') = Extended-Euclid(91, 0) return (91, 1, 0) (d', x', y') = (91, 1, 0) (d, x, y) = (91, 0, 1 - 2*0) (d, x, y) = (91, 0, 1) return (91, 0, 1) (d', x', y') = (91, 0, 1) (d, x, y) = (91, 1, 0 - 16*1) return (91, 1, -16) For ax + by = d we have: (3003)(1) + (182)(-16) = 91 gcd(3003,182) = 91

-- Apr 6 In-Class Exercise Thread

Extended-Euclid(3003, 182) (d', x', y') = Extended-Euclid(182, 91) (d', x', y') = Extended-Euclid(91, 0) b == 0 : returns (91, 1, 0) Hence, (d', x', y') = (91, 1, 0) returns (91, 0, 1) (d', x', y') = (91, 0, 1) returns (91, 1, -16) Final: (91, 1, -16)