Copyright

Euclidean Algorithm & Diophantine Equation: Examples & Solutions

An error occurred trying to load this video.

Try refreshing the page, or contact customer support.

Coming up next: Fermat's Last Theorem: Definition & Example

You're on a roll. Keep up the good work!

Take Quiz Watch Next Lesson
 Replay
Your next lesson will play in 10 seconds
  • 0:04 The Euclidean Algorithm
  • 3:19 Diophantine Equation
  • 6:12 Lesson Summary
Add to Add to Add to

Want to watch this again later?

Log in or sign up to add this lesson to a Custom Course.

Login or Sign up

Timeline
Autoplay
Autoplay
Lesson Transcript
Instructor: Gerald Lemay

Gerald has taught engineering, math and science and has a doctorate in electrical engineering.

Finding the greatest common divisor of two numbers is nicely accomplished using the Euclidean algorithm. In this lesson, we use this algorithm to explore solutions of Diophantine equations.

The Euclidean Algorithm

A food recipe has phrases like ''mix'' and ''blend.'' Knowing the meaning lets us create delicious results. In math, we have recipes called algorithms. Although the results aren't exactly edible, they can be fascinating. For example, the algorithm in this lesson has the terms dividend, divisor, quotient, and remainder. Interestingly, all of them relate to the mathematical operation of division. For example, let's divide 1,071 by 462:


1071/462


As a first step in the division operation, we look for the largest integer, or whole number, which when multiplied by 462 fits (i.e., does not exceed) 1,071. The number will become part of the answer to the division. The answer to the division is the quotient; so far, the quotient is 2.

The number 462 is the divisor. See the 924? We multiplied the quotient times the divisor (2 times 462) and obtained 924. Then, we subtract 924 from 1,071. What remains is the remainder; the remainder is 147.

Quotient, divisor and remainder; leaving only the term dividend. Make a guess of which number that could be. You're correct! The dividend is 1071.

Normally, we don't bother using colors to do division but in this lesson, we will keep track of the colored numbers: The blue 462 and the green 1,071.

Let's organize all this information with a table:

DIVIDEND DIVISOR QUOTIENT REMAINDER
1,071 462 2 147

Next step: divide 462 by 147. You might be asking why. It's because we are developing an algorithm for finding the greatest common divisor. But more on the greatest common divisor later.

For now, just divide 462 by 147 and identify the dividend, divisor, quotient and remainder:


462/147


  • The number being divided is the dividend: 462
  • The number doing the dividing is the divisor: 147
  • The answer to the division is the quotient: 3
  • What remains is the remainder: 21

Into the table we go:

DIVIDEND DIVISOR QUOTIENT REMAINDER
1,071 462 2 147
462 147 3 21

Doesn't the information just look far more organized? See how the divisor (second column) becomes the dividend in the next step? See how the remainder (fourth column) becomes the divisor in the next step?

Okay, next step is to divide 147 by 21, which as you can see, gives us 7:


147/21


And into the table to keep things organized:

DIVIDEND DIVISOR QUOTIENT REMAINDER
1,071 462 2 147
462 147 3 21
147 21 7 0

The algorithm stops when the remainder becomes 0. The last line contains the greatest common divisor. The greatest common divisor is the largest integer which divides into both 1,071 and 462 without producing a remainder. The greatest common divisor of 1,071 and 462 is 21.

We can check: 1,071 divided by 21 is the integer 51. And 462 divided by 21 is the integer 22.

This greatest common divisor algorithm is known as the Euclidean algorithm.

Diophantine Equation

Mathematicians love exploring and discovering relationships among numbers. What if someone asked you to write the greatest common divisor of the numbers 462 and 1,071 as the linear combination of 462 and 1,071? You might respond with, ''Say what?'', but all we are asking is to find x and y in the following equation:


21=x462+y1071


Plotting y versus x, we get the graph below:


An infinite number of solutions
An_infinite_number_of_solutions


To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 160 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Create an account to start this course today
Try it risk-free for 30 days!
Create An Account
Support