Back To Course

GRE Math: Study Guide & Test Prep27 chapters | 182 lessons | 16 flashcard sets

Are you a student or a teacher?

Try Study.com, risk-free

As a member, you'll also get unlimited access to over 75,000 lessons in math, English, science, history, and more. Plus, get practice tests, quizzes, and personalized coaching to help you succeed.

Try it risk-freeWhat teachers are saying about Study.com

Already registered? Login here for access

Your next lesson will play in
10 seconds

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.

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:

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:

- 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:

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**.

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:

Plotting *y* versus *x*, we get the graph below:

A line has an infinite number of points. Meaning there are an infinite number of *x*-*y* combinations satisfying the equation. Please note: this 21 = *x*1,071 + *y*462 line looks like it passes through the origin but it does not. At *x* = 0 we have *y* = .0196.

Out of all these solutions, there is only one where both *x* and *y* are integers. Integer solutions are the key ingredient for **Diophantine equations**. You can get a feeling for this by choosing some arbitrary integer for *x* (like -2) and discovering the corresponding *y* is 0.9.

There's a neat way to find the complete integer solution. We start by writing the equation:

Remainder = Dividend - Quotient x Divisor

Going back to next to the last line in the table, the remainder is 21. It equals the dividend, 462, minus the quotient times the divisor, 3 x 147.

And the line before in the table says remainder, 147, equals the dividend, 1,071, minus the quotient times the divisor, 2 x 462.

We're now going to find *x* and *y*. The trick is to isolate the numbers 462 and 1,071. Start with:

Then, using the equation, 147 = 1071 - (2 x 462), use the right-hand side and substitute for 147:

Then group the terms:

And, finally, simplify:

Okay, comparing to the Diophantine equation, 21 = *x* 462 + *y* 1,071, we see *x* = 7 and *y* = -3. This is the integer solution.

If we have one integer solution, we will have an infinite number of them. The general form of the solutions:

*k* is any integer. For *k*=0, *x* = 7 and *y* = -3. For *k* = 1, *x* = 58 and *y* = -25. You can check these numbers to solve the original Diophantine equation.

Let's take a few moments to review what we've learned about the Euclidean algorithm and the Diophantine equation. Given two integers, we can find the largest integer which divides into both numbers and produces a **quotient**, or the result of division, which itself is an **integer**, or a whole number. This largest integer is called the **greatest common divisor** and, therefore, doesn't include any **remainders**, which are, well, the remaining numbers.

To find the greatest common divisor we use an algorithm called the **Euclidean algorithm**. The **linear combination** of the two integers can be set equal to the greatest common divisor. A **Diophantine equation** looks for integer solutions, since integers are the key ingredient for them.

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

Create your account

Are you a student or a teacher?

Already a member? Log In

BackWhat teachers are saying about Study.com

Already registered? Login here for access

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

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

You are viewing lesson
Lesson
2 in chapter 19 of the course:

Back To Course

GRE Math: Study Guide & Test Prep27 chapters | 182 lessons | 16 flashcard sets

- Number Theory: Divisibility & Division Algorithm 6:52
- Euclidean Algorithm & Diophantine Equation: Examples & Solutions 7:01
- Binary Operation & Binary Structure: Standard Sets in Abstract Algebra 5:34
- Binary and Non-Binary Operations 5:34
- Types of Subgroups in Abstract Algebra 5:43
- Finitely Generated Abelian Groups: Classification & Examples 7:07
- Group Homomorphisms: Definitions & Sample Calculations 6:10
- Rings: Binary Structures & Ring Homomorphism 5:40
- Go to Algebra: Number Theory & Abstract Algebra

- Introduction to HTML & CSS
- Introduction to JavaScript
- Computer Science 332: Cybersecurity Policies and Management
- Introduction to SQL
- Computer Science 203: Defensive Security
- JavaScript Language Basics
- JavaScript & HTML
- Error Handling, Debugging & Events in JavaScript
- HTML Elements & Lists
- Conditionals, Arrays & Loops in JavaScript
- Anti-Bullying Survey Finds Teachers Lack the Support They Need
- What is the ASCP Exam?
- ASCPI vs ASCP
- MEGA Exam Registration Information
- MEGA & MoGEA Prep Product Comparison
- PERT Prep Product Comparison
- MTLE Prep Product Comparison

- Dynamic Memory Allocation: Definition & Example
- How Culture Identity Impacts Early Childhood Development
- Arrays of Structures in C Programming
- Religion in the Neolithic Age
- Sensor Networks: Definition, Operation & Relationship
- Practical Application for C Programming: Creating Functions
- Publishing an Information Security Compliance Policy
- Quiz & Worksheet - ADHD in Students
- Quiz & Worksheet - Math in Daily Life
- Quiz & Worksheet - Questions About Chapter 8 of Lord of the Flies
- Quiz & Worksheet - The Arts in Early Childhood Curriculum
- Flashcards - Measurement & Experimental Design
- Flashcards - Stars & Celestial Bodies
- Project-Based Learning
- 11th Grade Math Worksheets

- ACT Science Section: Prep & Practice
- Marketing for Teachers: Professional Development
- Public Relations 101: Intro to Public Relations
- High School Algebra II: Homeschool Curriculum
- Retail Management Training
- FTCE Humanities: Philosophical & Religious Influences on Art
- FTCE Humanities: Medieval Art & Philosophy
- Quiz & Worksheet - A Raisin in the Sun's Setting
- Quiz & Worksheet - CVP Analysis & Income Statements
- Quiz & Worksheet - Project Communications Management
- Quiz & Worksheet - Similies in The Giver
- Quiz & Worksheet - Antigone vs. Creon

- Using the Systematic Risk Principle & Portfolio Beta
- 1984 Book 1 Chapter 5 Summary
- Major Battles & Offensives of the Vietnam War: Learning Objectives & Activities
- AP Biology Exam Scoring Information
- Sequencing Activities for Kindergarten
- Common Core State Standards in Missouri
- What are the National Board Certification Areas for Teachers?
- How to Prep for the NYS ELA Regents Exam
- Plant Cell Project Ideas
- Alternative Teacher Certification in Colorado
- Sequencing Activities for Preschoolers
- AP English Literature Test & Study Guide

- Tech and Engineering - Videos
- Tech and Engineering - Quizzes
- Tech and Engineering - Questions & Answers

Browse by subject