Page 89 - 'Blast_Into_Math
P. 89
Blast into Math! The Euclidean algorithm: a computational recipe
This means we have written the remainder 29 as an integer times 103 (namely, 1) plus an
integer times 37 (namely, −2). Please take a minute or two to think about this. Next we then
use the LDT to divide 37 by the remainder 29.
37 =29+ 8.
We can re-arrange this to write the remainder 8 as an integer times 29 plus an integer times 37,
8= (1)37+ (−1)29.
Now, we can substitute the equation for 29,
8= 1(37) +(−1) [103 +(−2)37]
which simplifies to
8= (−1)103 +(3)37.
Next, we divide 29 by 8,
29 =8 ∗ 3+ 5.
Re-arranging the long division equation like before,
5= 29 +(−3)8.
Substituting our equations for 29 and 8,
5= 103 +(−2)37 +(−3) [(−1)103 +(3)37] =(4)103 +(−11)37.
Next, we divide 8 by 5,
8= 5+ 3,
which we can re-arrange to write the remainder 3 as
3= 8 − 5.
Substituting our equations for 8 and 5 from above,
3= 8 − 5= (−1)103 +(3)37 − [(4)103 +(−11)37] =(−5)103 +(14)37.
89
