# Mathematics 1010 online

## The Euclidean Algorithm

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 .

### Division of 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:

• A coefficient in the decimal representation of a number must be one of the 10 digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. On the other hand, a coefficient of a polynomial may be any real (or even complex ) number.

• Ten of a certain power of 10 can be traded for one higher power of 10, or vice versa. For example, ten 10s can be traded for one 100. By comparison, no trading is possible for polynomials. This actually simplifies the process of division.

Let's illustrate the division process with a couple of examples.

We can easily check that

This can be rewritten as

The symbol stands for remainder. The ingredients of this expression have the following names:
• is the dividend, i.e., the expression that's being divided.
• is the divisor, i.e., the expression by which we divide.
• is the quotient.
• is the remainder.

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:

Notes

• There is one column for each power of .

• The divisor is written to the left of the dividend. That's a pretty arbitrary convention, you might also write the divisor to the right of the dividend, perhaps separated by the division sign.

• The quotient is written on top of the dividend, with the powers of lining up. This is also just a convention.

• To find the individual terms of the quotient you start with the leading term, and keep subtracting the product of the last term you computed and the divisor. At each step, to get the new term of the quotient, you simply divide the leading term of what's left of the dividend by the leading term of the divisor.

• The process terminates when the degree of what is left is less than the degree of the divisor.

• The examples you find in textbooks or notes like these usually will have polynomials whose coefficients are small integers. Of course nothing changes in principle if the coefficients are rational or irrational real numbers, or complex numbers, or even algebraic expressions.

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.

Thus

### The greatest common factor of two natural numbers

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,

Clearly, 11 is a common factor, and there is no greater common factor.

Here is another example. The greatest common factor of and is . We have:

Indeed,

There are two ingredients that make the Euclidean Algorithm work:

• Suppose in

has a factor . Then is also a factor of the right hand side. If is a common factor of and it is also a factor of the remainder . Thus a common factor of and is also a common factor of and . In particular, the greatest common factor of and is also a factor of . This property remains true throughout the procedure.

• The remainders are all non-negative, and they decrease at each step. Thus eventually we must have a remainder 0. Thus the last divisor is a factor of the last dividend. Working backwards using the previous observation we see that it is also a factor of and .

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 greatest common factor of two polynomials

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,

Try to do that sort of thing without the Euclidean algorithm!

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: