03 The Division Algorithm What you know a Review of Long division 201 2 3 12 24148 0 24 01 0 14 12 28 24 40 36 40 1 Now we move on to Polynomial Division u x w x v x u x v x u x 0 v x 0 If u x x3 x v x x2 x 1 x3 x w x x2 x 1 Previous Long Divison x 1 remainder x 2 x 1 x 3 x x x 3 x 2 x x2 0 x x2 xx 1 x 1 2 Lets take it back to the book defn u x w x v x x 3 x w x x 2 x 1 Think about w x u x w x v x x 3 x w x x 2 x 1 w x must be degree 1 3 Now Substitute w x ax b u x w x v x x 3 x ax b x 2 x 1 ax 3 ax 2 ax bx 2 bx b Now Substitute w x ax b u x w x v x x 3 x ax b x 2 x 1 ax 3 ax 2 ax bx 2 bx b Now Substitute w x ax b u x w x v x x 3 x ax b x 2 x 1 ax 3 ax 2 ax bx 2 bx b ax 3 a b x 2 a b x b 4 Remember this is suppose to w x x 3 x ax 3 a b x 2 a b x b So think about this x 3 x ax 3 a b x 2 a b x b So think about this x 3 x ax 3 a b x 2 a b x b 0 1 2 5 Manipulate u x w x v x u x multiple of v x remainder Manipulate u x multiple of v x remainder 2 x 3 x ax 3 a b x 2 a b x b 3 The goal ax b from slide 9 4 u x multiple of v x remainder u x x 1 v x remainder 6 So w x x 1 w x v x x 1 x 2 x 1 w x v x x 3 1 5 u x w x v x x 3 x Manipulate x3 x x3 1 x 1 x 3 6 7 x3 1 x 1 Put it all together u x x 3 x x 3 1 x 1 x 1 x 2 x 1 x 1 w x v x remainder x 3 x x 1 x 2 x 1 x 1 x 1 2 x x 1 x 3 x remainder x 1 7 Previous Long Divison 1 remainder x 1 x 2 x 1 x 3 x x x 3 x 2 x x22 0 x x 1 x 1 x Switch gears Think about degrees u x q x v x r x 0 simplify matters remove the x u qv r 8 u x 3 1 Repeated Addition v x 3 u x x 2 x 1 v x x 2 x 2 u x q x v x 9 8 u x x 1 v x x 1 Same work in a new format x3 2 x 1 x2 x 2 Same work in a new format x3 2 x 1 x2 x 2 x 1 x 1 9 Same work in a new format x3 2 x 1 x2 x 2 x 1 x 1 Same work in a new format x3 2 x 1 x2 x 2 x 1 2 x 1 x Same work in a new format x3 2 x 1 x2 x 2 x 1 2 x 1 x 10 Same work in a new format x3 2 x 1 x 1 x x2 x 2 x 1 2 0 x 1 2 6 3 2 GCD and LCM 0 4 0 4 d x GCD u x v x L x LCM u x v x 3 3 Division Algorithm in Integers 11 GCD LCM 0 A GCD LCM 0 B 0 A 3 4 Aryabhata Algorithm Efficient Euclidean Algorithm 1 AC A 12 Aryabhata Algorithm Efficient Euclidean Algorithm 1 AC D A Aryabhata Algorithm Efficient Euclidean Algorithm 5 E 1 AC E A Aryabhata Algorithm Efficient Euclidean Algorithm 2 F 1 AC E B G A 13 Aryabhata Algorithm Efficient Euclidean Algorithm 2 F G 1 AC E B A Aryabhata Algorithm Efficient Euclidean Algorithm C H 1 AC E B A Aryabhata Algorithm Efficient Euclidean Algorithm C B H 1 AC E A 14 Aryabhata Algorithm Efficient Euclidean Algorithm 2 1 AC A Aryabhata Algorithm Efficient Euclidean Algorithm 2 1 AC Aryabhata Algorithm The SIGN Rule I 1 J 7 1 AC E A 15 Where are we going with this K 0 1 AC E A Aryabhata works for polynomials too 3 x x 1 x2 2x 1 2 x 1 x x x 2 x 1 2 0 x 1 0 1 x 1 2 6 2 x2 x 1 x2 x 2 x x3 2x 1 16