Suggested languages for you:
|
|

## All-in-one learning app

• Flashcards
• NotesNotes
• ExplanationsExplanations
• Study Planner
• Textbook solutions

# Euclidean Algorithm

Suppose you are a towel manufacturer. You get shipments of fabric in rectangles of $$600 \,cm$$ by $$250 \,cm,$$ and you want to make the largest square towels possible without wasting any fabric. What size should you cut? The answer is actually to find the greatest common divisor of the two side lengths, $$600\,cm$$ and $$250\,cm,$$ which is $$50\,cm,$$ so the towels should have a side length of $$50\,cm.$$ In this case it is not too hard to calculate the greatest common factor by listing the factors of each of the side lengths and seeing the largest number that is in both, but as the lengths get longer, this task will get more and more tedious. This calls for a better way of calculating the greatest common divisor: the Euclidean Algorithm.

If you want to cut a rectangle into the largest possible integer length squares without any waste, you must cut them to the size of the greatest common divisor of the two side lengths of the rectangle.

## Number Theory and the Euclidean Algorithm

Before you study the Euclidean Algorithm, it is important to fully understand greatest common divisors first.

### Greatest Common Divisors (GCD)

The greatest common divisor is one of the most fundamental concepts in elementary number theory.

The Greatest Common Divisor of two integers $$p$$ and $$q$$ is the greatest positive integer such that dividing both $$p$$ and $$q$$ by that number will give an integer value. This is written $$GCD(p, q).$$

For example:

• The divisors of 12 are 1, 2, 3, 4, 6 and 12.

• The divisors of 16 are 1, 2, 4, 8 and 16.

Hence, the greatest common divisor of 12 and 16, $$GCD(12,16),$$ is 4.

## Defining the Euclidean Algorithm

The Euclidean Algorithm is a method of finding the greatest common divisor between two numbers. The Euclidean Algorithm finds $$GCD(a,b), a>b$$ in the following way:

1. Find integers $$q_1, r_1$$ such that $$r_1 < b$$ and $$a = q_1 b + r_1.$$

2. If $$r_1 = 0,$$ then $$GCD(a,b)$$ is $$b.$$

3. If $$r_1 \neq 0,$$ then $$GCD(a,b) = GCD(b, r_1).$$ Repeat the algorithm for $$GCD(b, r_1)$$ until you find an $$r_i=0,$$ in which case $$GCD(a,b) = r_{i-1}.$$

The $$q$$ values are called the quotients and the $$r$$ values are the remainders. This algorithm is recursive, meaning part of it requires plugging a value back into the algorithm again, but it will always give an answer. This is because in step one, you require that $$r_1 < b,$$ so when you use the algorithm recursively you guarantee that $$r_i < \dots < r_2 < r_1 < b,$$ meaning that eventually you will reach an $$r$$ that is equal to 0.

## Euclidean Algorithm Examples

Now that you know how the Euclidean algorithm works, let's look at some examples of it.

Use the Euclidean Algorithm to find $$GCD(100,78).$$

Solution

First, you must find $$q_1,r_1$$ such that

$100 = q_1 78 + r_1.$

$$q_1$$ must be $$1,$$ since any integer greater than that will exceed our left-hand side. Given this, $$r_1$$ must be $$22$$ to make the left-hand side equal to 100.

$100 = 1 \cdot 78 + 22.$

Since $$r_1 = 22 \neq 0,$$ you must repeat the algorithm with $$GCD(78, 22).$$ $$22$$ goes into $$78$$ $$3$$ times with a remainder of $$12,$$ hence these are the values for $$q_2$$ and $$r_2.$$

$78 = 3 \cdot 22 + 12.$

Again, $$r_2 \cdot 0$$ so the algorithm must be repeated with $$GCD(22, 12).$$ $$12$$ goes into $$22$$ once with a remainder of $$10,$$ so:

$22 = 1 \cdot 12 + 10.$

Again, the algorithm must be repeated. This time, finding $$GCD(12,10).$$ 10 goes into 12 once, with a remainder of 2, so:

$12 = 1 \cdot 10 + 2.$

The algorithm must be repeated once more. $$2$$ goes into $$10$$ $$5$$ times, with no remainder:

$10 = 5\cdot 2 + 0.$

Since the remainder here is $$0,$$ the algorithm is finished. The last remainder in the algorithm was $$2,$$ hence $$GCD(100,78) = 2.$$

For questions with relatively smaller numbers such as the one above, the Euclidean algorithm may be no quicker than simply listing and comparing the divisors of each number. But when the numbers are bigger, the Euclidean Algorithm is very useful.

Use the Euclidean Algorithm to find $$GCD(2365,781).$$

Solution

Firstly, you must find $$q_1,r_1$$ such that

$2365 = q_1 781 + r_1.$

Three lots of $$781$$ can go into $$2365$$ before exceeding it, hence $$q_1$$ must be three. This leaves a remainder of 22, which is the value for $$r_1.$$

$2365 = 3 \cdot 781 + 22.$

Since $$r_1$$ is not $$0,$$ you must repeat the algorithm with $$GCD(781, 22).$$ $$22$$ can go into $$781$$ 35 times, leaving a remainder of $$11.$$ Hence:

$781 = 35 \cdot 22 + 11.$

Since $$r_2$$ is not $$0,$$ the algorithm must be repeated again, for $$GCD(22, 11).$$ This one is quite easy, $$11$$ goes into $$22$$ twice with no remainder.

$22 = 2 \cdot 11 + 0.$

Since there is no remainder, the previous remainder must be the greatest common divisor. Hence, $$GCD(2365, 781) = 11.$$

## Euclidean Algorithm Proof

Now that you have seen the Euclidean algorithm and a few examples of it, you may be wondering: why does it work? The key part of the Euclidean algorithm that requires proving is that if

$a = q_1 b + r_1,$

then $$GCD(a,b) = GCD(b, r_1).$$

Once this is proven, the Euclidean algorithm works through recursion so that

\begin{align} GCD(a,b) &= GCD(b, r_1) \\ & \quad \vdots \\ &= GCD(r_{i-1}, 0) \\ &= r_{i-1}. \end{align}

Before we prove this, here are some important things to note. For any integers $$p, q, r$$:

1. If $$p$$ divides $$q$$, then $$p$$ divides $$rq.$$
2. If $$p$$ divides $$q$$ and $$r,$$ then $$p$$ divides $$q + r.$$
3. If $$p$$ divides $$q$$ and $$r,$$ then $$p \leq GCD(q,r).$$

Now that these have been stated, we can use them to build the proof.

Prove that if $$a = q b + r,$$ then $$GCD(a,b) = GCD(b, r).$$

Solution

Rearrange the first equation to be

$r = a - qb.$

$$GCD(a,b)$$ must divide $$a$$ and $$b$$ by its definition. Hence, it must also divide $$-qb$$ by rule 1 above. Using rule 2, we get that $$GCD(a,b)$$ must divide $$a - qb = r.$$ By rule three, since $$GCD(a,b)$$ must divide $$b$$ and $$r,$$ $$GCD(a,b) \leq GCD(b,r).$$

Similarly, $$GCD(b,r)$$ must divide both $$b$$ and $$r,$$ by definition. By rule 1, it must also divide $$qb.$$ By rule 2, it must also divide $$qb + r = a.$$ Since $$GCD(b,r)$$ divides $$a$$ and $$b,$$ by rule three $$GCD(b,r) \leq GCD(a,b).$$

Since $$GCD(a,b) \leq GCD(b,r)$$ and $$GCD(b,r) \leq GCD(a,b),$$ it must be the case that $$GCD(a,b) = GCD(b, r).$$

## Application of Euclidean Algorithm

Here, the Euclidean Algorithm has only been applied to integers, but it can be applied to many other types of mathematical objects too. Here, you will look at using the Euclidean Algorithm to find the greatest common divider of two polynomials.

A polynomial $$p(x)$$ divides another polynomial $$q(x)$$ if there exists another polynomial, $$r(x),$$ such that $$p(x) = q(x) \cdot r(x).$$

A monic polynomial is a polynomial with a leading coefficient of $$1,$$ meaning the coefficient of the highest power term is $$1.$$

The greatest common divisor, $$GCD(p, q)$$ of polynomials $$p(x), q(x)$$ is the monic polynomial of the highest order that divides both $$p(x)$$ and $$q(x).$$

The requirement for the greatest common divisor of polynomials to be monic ensures that it is unique. With these definitions in place, the Euclidean Algorithm works in exactly the same way as it does for real numbers. To find $$GCD(a(x), b(x)):$$

1. Find polynomials $$q_1(x), r_1(x)$$ such that $$r_1(x)$$ is lower order than $$b(x)$$ and $$a(x) = q_1(x) b(x) + r_1(x).$$

2. If $$r_1(x) = 0,$$ then $$GCD(a(x),b(x))$$ is $$b(x).$$

3. If $$r_1(x) \neq 0,$$ then $$GCD(a(x),b(x)) = GCD(b(x), r_1(x)).$$ Repeat the algorithm for $$GCD(b(x), r_1(x))$$ until you find an $$r_i(x)=0,$$ in which case $$GCD(a(x),b(x)) = r_{i-1}(x).$$

Use the Euclidean Algorithm to find $$GCD(f(x),g(x)),$$ where:

\begin{align} f(x) & = x^4 - 5x^3 - 35x^2 - 5x - 36 \\ g(x) & = x^3 - 5x^2 + x-5. \end{align}

Solution

To find the $$q$$ and $$r$$ values, you could use polynomial division. In this case however, you can see that by multiplying $$g(x)$$ by $$x,$$ the the $$x^4, x^3,$$ and $$x$$ terms are all correct. Hence, you can take $$x$$ to be $$q_1(x),$$ and correct the sum by setting the remainder as $$-36x^2 - 36.$$

$x^4 - 5x^3 - 35x^2 - 5x - 36 = (x) \cdot (x^3 - 5x^2 + x-5) + (-36x^2 - 36).$

Since the remainder term is not zero, you must repeat the algorithm using $$GCD(g(x), r_1(x)).$$ This time, lets use polynomial division.

$\begin{array}{rll} - \frac{1}{36} x + \frac{5}{36} \phantom{)} && \\ -36x^2-36 \enclose{longdiv}{\; x^3 - 5x^2 + \phantom{1}x - 5\phantom{)}}\kern-.2ex \\ \underline{-\; (x^3 +0x^2 + \phantom{1} x )\phantom{-5) }} && \hbox{Subtract like terms} \\ -5x^2 + 0x -5\phantom{)} && \hbox{} \\ \underline{\phantom{ x^3 }-(-5x^2-0x -5)} && \hbox{Subtract like terms} \\ \phantom{00}0\phantom{)} && \hbox{The remainder is zero.} \end{array}$

Hence, the quotient value is $$-\frac{1}{36} + \frac{5}{36}$$ and the remainder is $$0.$$ So

$x^3 - 5x^2 + x-5 = \left(-\frac{1}{36} + \frac{5}{36}\right) \cdot (-36x^2 - 36) + 0.$

Since the remainder is 0, the greatest common divider must be the last remainder, $$-36x^2 - 36.$$ But for polynomials, the greatest common divider must be monic, so you must divide this polynomial by $$-36$$ such that it is monic. Hence, $$GCD(a(x),b(x) = x^2 + 1.$$

## Euclidean Algorithm - Key takeaways

• The Euclidean algorithm is used to find the greatest common divider between two integers.
• The Euclidean Algorithm finds $$GCD(a,b), a>b$$ in the following way:
1. Find integers $$q_1, r_1$$ such that $$r_1 < b$$ and $$a = q_1 b + r_1.$$
2. If $$r_1 = 0,$$ then $$GCD(a,b)$$ is $$b.$$
3. If $$r_1 \neq 0,$$ then $$GCD(a,b) = GCD(b, r_1).$$ Repeat the algorithm for $$GCD(b, r_1)$$ until you find an $$r_i=0,$$ in which case $$GCD(a,b) = r_{i-1}.$$

The Euclidean Algorithm finds GCD(a,b), a>b  in the following way:

1. Find integers q, r such that r < b  and  a = qb + r.

2. If r=0 then GCD(a,b) is b.

3. If r isn't 0 then GCD(a,b) = GCDb, r). Repeat the algorithm for GCD(b, r) until you find a remainder of 0 in which case GCD(a,b) is the r that gave you a remainder of 0.

The Euclidean Algorithm is a computationally efficient way of finding the greatest common divisor of two numbers.

The GCD(30, 18) can be found using the Euclidean Algorithm:

• 30 = 1*18 + 12,
• 18 = 1*12 + 6,
• 12 = 2*6 + 0.

The last non-zero remainder is 6, hence GCD(30,18) = 6.

The Euclidean algorithm works because if a = q*b + r, then GCD(a, b) = GCD(b, r).

The Euclidean Algorithm finds GCD(a,b), a>b in the following way:

• Find integers q, r such that r < b  and  a = qb + r.

• If r=0 then GCD(a,b) is b.

• If r isn't 0 then GCD(a,b) = GCDb, r). Repeat the algorithm for GCD(b, r) until you find a remainder of 0 in which case GCD(a,b) is the r that gave you a remainder of 0.

The GCD(30, 18) can be found using the Euclidean Algorithm:

• 30 = 1*18 + 12,
• 18 = 1*12 + 6,
• 12 = 2*6 + 0.

The last non-zero remainder is 6, hence GCD(30,18) = 6.

## Final Euclidean Algorithm Quiz

Question

What is the Euclidean algorithm used to find?

Greatest common divider.

Show question

Question

What is the Greatest Common Divisor of two integers $$p$$ and $$q?$$

The greatest positive integer such that dividing both $$p$$ and $$q$$ by that number will give an integer value.

Show question

Question

What notation is used for the greatest common divider of two integers $$p$$ and $$q?$$

$$GCD(p, q).$$

Show question

Question

What is the first step in the Euclidean Algorithm for $$GCD(a,b)?$$

Find integers $$q_1, r_1$$ such that $$r_1 < b$$ and $$a = q_1 b + r_1.$$

Show question

Question

If Find $$a = q_1 b + r_1$$ and If $$r_1 = 0,$$ what should you do?

Stop, as the $$GCD(a,b)$$ is $$b.$$

Show question

Question

If Find $$a = q_1 b + r_1$$ and If If $$r_1 \neq 0,$$ what should you do?

Repeat the algorithm with $$GCD(b, r_1).$$

Show question

Question

When is the Euclidean algorithm finished?

When you get an $$r_i=0.$$

Show question

Question

If $$r_{i} = 0,$$ what is the solution of the Euclidean Algorithm?

$$GCD(a,b) = r_{i-1}.$$

Show question

Question

Why does the Euclidean algorithm work?

Because $$GCD(a,b) = GCD(b, r_1) = ... = GCD(r_{i-1}, 0).$$

Show question

Question

How do you prove that $$GCD(a,b) = GCD(b,r_1)?$$

Prove that $$GCD(a,b)$$ is a divider of $$r_1$$ and is thus smaller than or equal to $$GCD(b, r_1),$$ and that $$GCD(b,r_1)$$ divides $$a$$ and thus is smaller than or equal to $$GCD(a,b).$$ Thus, they must be equal.

Show question

Question

What does it mean for a polynomial $$p(x)$$ to divide another polynomial $$q(x)?$$

There exists another polynomial, $$r(x),$$ such that $$p(x) = q(x) \cdot r(x).$$

Show question

Question

What is a monic polynomial?

A monic polynomial is a polynomial with a leading coefficient of $$1,$$ meaning the coefficient of the highest power term is $$1.$$

Show question

Question

What is  the greatest common divisor, $$GCD(p, q)$$ of polynomials $$p(x), q(x)?$$

The monic polynomial of the highest order that divides both $$p(x)$$ and $$q(x).$$

Show question

Question

Why does the greatest common divisor of two polynomials have to be monic?

To ensure it is unique.

Show question

60%

of the users don't pass the Euclidean Algorithm quiz! Will you pass the quiz?

Start Quiz

## Study Plan

Be perfectly prepared on time with an individual plan.

## Quizzes

Test your knowledge with gamified quizzes.

## Flashcards

Create and find flashcards in record time.

## Notes

Create beautiful notes faster than ever before.

## Study Sets

Have all your study materials in one place.

## Documents

Upload unlimited documents and save them online.

## Study Analytics

Identify your study strength and weaknesses.

## Weekly Goals

Set individual study goals and earn points reaching them.

## Smart Reminders

Stop procrastinating with our study reminders.

## Rewards

Earn points, unlock badges and level up while studying.

## Magic Marker

Create flashcards in notes completely automatically.

## Smart Formatting

Create the most beautiful study materials using our templates.