Step By Step Calculus » 2.9 - Tricks for Dividing

show_hiddenExpand All [+]
Synopsis
  • Euclid’s algorithm (Euclidean Division) can be used to determine the GCD of two integers (n,m)n,m) where |n|>|m||n|>|m|) by generating a list of R_{-1}, R_0, R_1R_{-1}, R_0, R_1, R_2R_2, \ldots\ldots where R_{-1}=|n|, R_0=|m|R_{-1}=|n|, R_0=|m| and
    \displaystyle R_i=\displaystyle R_i=remainder of \displaystyle R_{i-2}\div R_{i-1} \quad \displaystyle R_{i-2}\div R_{i-1} \quad for \displaystyle i=1,2,\cdots\displaystyle i=1,2,\cdots
    All the RR’s after some point will be zero. The last non-zero RR is the GCD of n,mn,m. Euclidean division is also useful when it becomes necessary to reduce ratios of polynomials, since this algorithm works equally well in finding the GCD of two polynomials.
  • Synthetic division is a shortcut method for polynomial long division.