Page 90 - 'Blast_Into_Math
P. 90
Blast into Math! The Euclidean algorithm: a computational recipe
Next, we divide 5 by 3,
5= 3+ 2.
The remainder
2= 5 − 3.
Substituting our equations for 5 and 3,
2= 5 − 3= (4)103 +(−11)37 − [(−5)103 +(14)37] =(9)103 +(−25)37.
Finally, we divide the last two remainders,
3= 2+ 1.
The last remainder
1= 3 − 2.
Substituting our equations for 3 and 2,
90
