-- Apr 6 In-Class Exercise Thread
Calculate Extended Euclid(3003, 182)
b = 182, not 0
(d’, x’, y’) = Extended Euclid(182, 3003 mod 182) = Extended Euclid(182, 91)
Calculate Extended Euclid(182, 91)
b = 91, not 0
(d’, x’, y’) = Extended Euclid(91, 182 mod 91) = Extended Euclid(91, 0)
Calculate Extended Euclid(91, 0)
Since b = 0,
return (91, 1, 0)
Back to Extended Euclid(182, 91)
(d’, x’, y’) = Extended Euclid(91, 0) = (91, 1, 0)
(d, x, y) = (91, 0, 1 - floor(182/91)*0)
return (91, 0, 1)
Back to Euclid(3003, 182)
(d’, x’, y’) = Extended Euclid(182, 91) = (91, 0, 1)
(d, x, y) = (91, 1, 0 - floor(3003/182)*1)
return (91, 1, -16)
For ax + by = d,
(3003)(1) + (182)(-16) = 91
So gcd(3003, 182) = 91
<pre>
Calculate Extended Euclid(3003, 182)
b = 182, not 0
(d’, x’, y’) = Extended Euclid(182, 3003 mod 182) = Extended Euclid(182, 91)
Calculate Extended Euclid(182, 91)
b = 91, not 0
(d’, x’, y’) = Extended Euclid(91, 182 mod 91) = Extended Euclid(91, 0)
Calculate Extended Euclid(91, 0)
Since b = 0,
return (91, 1, 0)
Back to Extended Euclid(182, 91)
(d’, x’, y’) = Extended Euclid(91, 0) = (91, 1, 0)
(d, x, y) = (91, 0, 1 - floor(182/91)*0)
return (91, 0, 1)
Back to Euclid(3003, 182)
(d’, x’, y’) = Extended Euclid(182, 91) = (91, 0, 1)
(d, x, y) = (91, 1, 0 - floor(3003/182)*1)
return (91, 1, -16)
For ax + by = d,
(3003)(1) + (182)(-16) = 91
So gcd(3003, 182) = 91
</pre>