The Euclidean algorithm calculates the greatest common divisor of two positive integers without listing all their factors or performing complete prime factorization. The method repeatedly divides the larger number by the smaller number and replaces the pair with the smaller number and the remainder. This process continues until the remainder becomes zero. The last nonzero remainder is the GCD. For example, to find the GCD of 48 and 18, divide 48 by 18 to obtain a remainder of 12, then divide 18 by 12 to obtain a remainder of 6, and finally divide 12 by 6 to obtain a remainder of zero. Therefore, the GCD is 6. The algorithm works because the common divisors of two numbers are also the common divisors of the smaller number and their remainder.
Euclidean Algorithm
The Euclidean algorithm is an efficient method for finding the greatest common divisor of two integers through repeated division and remainders. It is one of the oldest and most important algorithms in mathematics.
| Name | Expression | Description |
|---|---|---|
Euclidean Algorithm | GCD(a,b) = GCD(b, a mod b), for b ≠ 0 | The GCD remains unchanged when the larger number is replaced by the remainder after division by the smaller number. |
Division Algorithm | a = bq + r, where 0 ≤ r < b | Each division step expresses a as the product of b and an integer quotient q, plus remainder r. |
Termination Condition | GCD(a,0) = |a| | When the remainder becomes zero, the nonzero number is the GCD. |
Extended Euclidean Identity | ax + by = GCD(a,b) | The extended algorithm finds integers x and y that express the GCD as a linear combination of the original integers. |
Explanation
Variables
| Symbol | Meaning |
|---|---|
a | The first integer in a division step. |
b | The second integer and divisor in a division step. |
q | The integer quotient obtained from division. |
r | The remainder obtained after division. |
x | An integer coefficient in the extended Euclidean identity. |
y | Another integer coefficient in the extended Euclidean identity. |
Example or application
A worked example has not yet been added.
Definition
The Euclidean algorithm is a repeated-division procedure for finding the greatest common divisor of two integers by replacing a pair of numbers with the smaller number and the remainder until the remainder becomes zero.
Purpose
The algorithm provides an efficient and systematic way to calculate the GCD of large integers without requiring complete factorization.
Importance
It is fundamental to number theory, fraction simplification, modular arithmetic, cryptography and computer algorithms.
Key Concepts
| Name | Description |
|---|---|
Euclidean Algorithm | A repeated-division method for finding the GCD of two integers. |
Dividend | The number being divided at each step. |
Divisor | The number by which the dividend is divided. |
Remainder | The value left after division. |
Last Nonzero Remainder | The final nonzero remainder, which equals the GCD. |
Recursive Reduction | The repeated replacement of the original pair with a smaller pair that has the same GCD. |
Characteristics
The algorithm calculates the GCD using repeated division.
It does not require listing every factor.
Each step reduces the size of the numbers being considered.
The process terminates when the remainder becomes zero.
The last nonzero remainder is the GCD.
It is efficient even for very large integers.
The algorithm can be extended to find integer coefficients in Bézout's identity.
Types
| Name | Description |
|---|---|
Standard Euclidean Algorithm | Uses repeated division and remainders to calculate the GCD. |
Extended Euclidean Algorithm | An extension that also finds integers x and y satisfying ax + by = GCD(a,b). |
Recursive Implementation | An implementation that repeatedly calls the same procedure using the divisor and remainder. |
Iterative Implementation | An implementation that uses a loop to update the numbers until the remainder is zero. |
Components
| Name | Description |
|---|---|
First Integer | The initial larger or first input number. |
Second Integer | The initial smaller or second input number. |
Quotient | The integer result of each division step. |
Remainder | The value used to update the pair for the next division. |
GCD | The last nonzero remainder obtained by the procedure. |
Properties
| Name | Expression | Description |
|---|---|---|
GCD Preservation | GCD(a,b) = GCD(b,r) | Replacing a pair with the divisor and remainder preserves the GCD. |
Remainder Condition | 0 ≤ r < b | The remainder is always nonnegative and smaller than the positive divisor. |
Termination | r = 0 | The process ends when a division produces a zero remainder. |
Final GCD | GCD(a,b) = last nonzero remainder | The last nonzero remainder is the greatest common divisor. |
Coprime Condition | GCD(a,b) = 1 | The algorithm identifies coprime integers when the last nonzero remainder is 1. |
Examples
| Problem | Solution | Explanation |
|---|---|---|
Find the GCD of 48 and 18 using the Euclidean algorithm. | 48 = 18 × 2 + 12; 18 = 12 × 1 + 6; 12 = 6 × 2 + 0. Therefore, GCD = 6. | The last nonzero remainder is 6, so the greatest common divisor is 6. |
Find the GCD of 252 and 105. | 252 = 105 × 2 + 42; 105 = 42 × 2 + 21; 42 = 21 × 2 + 0. Therefore, GCD = 21. | Each step uses the divisor and remainder from the previous division until the remainder becomes zero. |
Determine whether 35 and 64 are coprime using the Euclidean algorithm. | 64 = 35 × 1 + 29; 35 = 29 × 1 + 6; 29 = 6 × 4 + 5; 6 = 5 × 1 + 1; 5 = 1 × 5 + 0. Therefore, GCD = 1. | Since their GCD is 1, the two integers are coprime. |
Find integers x and y satisfying 30x + 18y = GCD(30,18). | GCD(30,18) = 6. One solution is x = -1 and y = 2, because 30(-1) + 18(2) = 6. | This illustrates Bézout's identity, which can be obtained using the extended Euclidean algorithm. |
Applications
Calculating GCD of large integers.
Simplifying fractions.
Solving linear Diophantine equations.
Finding modular multiplicative inverses.
Supporting public-key cryptography.
Implementing efficient mathematical algorithms.
Prerequisites
Understanding of factors and multiples.
Knowledge of GCD and HCF.
Basic division and remainders.
Understanding of integers.
Familiarity with the division algorithm.
Learning Objectives
Define the Euclidean algorithm.
Explain why repeated division preserves the GCD.
Calculate GCD using the standard algorithm.
Identify the termination condition.
Recognize coprime integers through the algorithm.
Understand the purpose of the extended Euclidean algorithm.
Express the GCD as a linear combination of two integers.
Common Mistakes
Dividing the smaller number by the larger number incorrectly.
Replacing the pair with the wrong remainder.
Stopping before the remainder becomes zero.
Choosing the final zero remainder instead of the last nonzero remainder.
Making arithmetic errors during repeated division.
Confusing the standard Euclidean algorithm with the extended version.
Practice Questions
Find the GCD of 56 and 24 using the Euclidean algorithm.
Calculate the GCD of 252 and 198.
Use the Euclidean algorithm to determine whether 101 and 103 are coprime.
Find the GCD of 420 and 96.
Explain why the GCD remains unchanged when a number is replaced by its remainder.
Find integers x and y satisfying 26x + 15y = GCD(26,15).
Key Takeaway
The Euclidean algorithm finds the GCD efficiently through repeated division. The last nonzero remainder is always the greatest common divisor.
Related Topics
SCI-MAT-002-044
SCI-MAT-002-045
SCI-MAT-002-047
SCI-MAT-002-048
SCI-MAT-002-050
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Arithmetic & Number Theory