✦ScienexySCIENCE KNOWLEDGE LIBRARY
topic · SCI-MAT-002-049

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.

NameExpressionDescription

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

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.

Variables

SymbolMeaning

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

NameDescription

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

NameDescription

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

NameDescription

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

NameExpressionDescription

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

ProblemSolutionExplanation

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