Discussion of the Aryabhata-Euclid algorithm Chapter IIIPoints to ponderExamplesPolynomial examplesFull integer algorithmThe lifting mechanismAbout polynomial algorithmWhen not to use the algorithmContinued..Meaning of remainderContinuedSlide 12Discussion of the Aryabhata-Euclid algorithmChapter IIIBy Avinash Sathaye•It is better to do the integer version of the algorithm (3.4) before the general polynomial version.•It is good to repeat and review the definitions.•U(x) = q(x)v(x)+r(x)Points to ponderDividendquotientDivisorRemainderExamplesDividendquotientDivisorRemainder = 6523 2 + (157 12) 4 2384With a calculator, this is best done as = 65232157124.151731161Polynomial examplesDividendquotientDivisorRemainder = (x^3-1) + x (x ^2-1) (x-1)Full integer algorithm��������������������������������������������������������65232 *15712 42384 61408 1976 1432 2112 396 116 60 *First division(quotient)First remainderGCDLast division(quotient)��������������������������������������������������������602 65232 *145 15712 422 2384 613 1408 19 976 14 432 21 112 31 96 10 16 61 0 *The lifting mechanism(4)*(2)+1 = - 602 (15712) 145 (65232 ) -16The GCD is the top determinant, up to a sign!About polynomial algorithm•When working with polynomials, sometimes you get complicated denominators, if you insist on making the GCD monic. (See the example in the book.) •You can simply start with 0,1 as the bottom two answers and continue. Finally, you can fix the answers for the monic GCD.When not to use the algorithm•When only remainders are needed, the work can be shortened. For example to compute remainders moduloyou can proceed thus: - + x2x 1Remainder of is x2 - x 1x3has the same remainder as that of = x (x-1) - x2xand hence gives = - (x-1) x -1Thus gives x4 = (x) (-1)-xContinued..•Now we get with remainder equal to that of or • It is clear that all polynomials of degree at most five can now be easily handled. This technique is essential for many homework problems.x5-x2- + x 1Meaning of remainder•The remainder is simply a generalization of the idea of substitution. If we take remainder modulo a liner polynomialthen we are effectively plugging in•If we try a remainder modulothen we are trying to put a value of plus or minus since the sign is not given, we only agree to substitute for even powers. - x a = x a - x233Continued•Thus modulo we get the remainders for powers of x as :successively! - x23[ ], , , , , , ,x 3 3 x 9 9 x 27 27 x .