Euclid of Alexandria lived during the third century BC. The Algorithm named after him let's you find the greatest common factor of two natural numbers or two polynomials .
Polynomials can be divided mechanically by long division, much like numbers can be divided. Numbers represented in decimal form are sums of powers of 10. Polynomial expressions similarly are sums of powers of the variable (let's say ). There are two main differences:
Let's illustrate the division process with a couple of examples.
We can easily check that
The equation can be rewritten alternatively, and equivalently, as:
Thus the equations , , and are all equivalent.
To illustrate the terminology let's rewrite with the words replacing the expressions:
If the remainder is zero then we say the divisor divides the dividend evenly.
Given a dividend and a divisor, the quotient and the remainder can be found by long division. For example, the division in - can be written as:
Here is a more complicated example, Some of the coefficients of the dividend and the quotient are zero. They are given here explicitly, but with practice you may just leave these spaces blank.
Let's say we want to find the greatest common factor of two natural numbers and , and let's suppose is the larger of the two, i.e., .
The Euclidean Algorithm proceeds by dividing by , with remainder, then dividing the divisor by the remainder, and repeating this process until the remainder is zero. The greatest common factor of and is the last divisor. (Notice that at no point do you pay attention to the current quotient.)
The following examples illustrate the process. Suppose we want to find the greatest common factor of and . We have
The last remainder is zero, the last divisor is , and so is the greatest common factor of 110 and 143. Indeed,
Here is another example. The greatest common factor of and is . We have:
There are two ingredients that make the Euclidean Algorithm work:
Of course, we could have solved the problems in these particular examples by listing all the factors of the numbers involved and finding the largest. Another technique is to find all the prime factors and see which ones are common to the numbers. Those techniques work fine for the small numbers. The power of the Euclidean Algorithm becomes apparent when the factors aren't obvious, i.e., when we have large numbers. Consider this example: Let
Factoring these numbers is possible using a computer, but larger numbers (with somewhere around 200 digits) are used in security codes whose effectiveness depend on those numbers being impossible to factor with current computer equipment. While factoring large numbers -- particularly products of large prime numbers -- is difficult, finding the greatest common factor of two numbers is easy!
In this case:
Thus the greatest common factor of and is . In fact, both and are the products of two large primes. Specifically,
The same arguments as above apply to dividing polynomials with remainder. Thus the Euclidean algorithm can be used to find the ``greatest'' common factor of the numerator and denominator in a rational expression. ``Greatest'' in this context means ``highest possible degree''. A (non-zero) constant multiplying such a greatest (polynomial) factor does not matter, and we can choose it conveniently depending upon the application.
Suppose we want to find the greatest common factor of and .
Using long division we see that
Thus is the highest degree common factor of and .
In fact, using long division again we see that
Thus, for example,
Here is another example. Let
What is the greatest common factor of and ? Using long division once again we get:
Thus the highest degree common factor of and is (we can ignore the constant factor 7.)
The main application of finding common factors of two polynomials is to enable to us to cancel them in the ratio of the two polynomials. In this case we obtain: