What is the Euclidean algorithm?

The Euclidean algorithm is an efficient method for computing the Greatest Common Divisor (GCD) of two integers by repeatedly replacing the larger number with the remainder of division.

What is the Extended Euclidean algorithm?

The Extended Euclidean algorithm is an extension of the standard algorithm that also computes integers $x$ and $y$ (Bézout coefficients) satisfying $ax + by = \gcd(a, b)$.

What are Bézout's coefficients?

They are the integers $x$ and $y$ in Bézout's identity $ax + by = \gcd(a, b)$, representing the GCD as a linear combination of the two inputs.

What is a modular multiplicative inverse?

The modular inverse of $a$ modulo $m$ is an integer $x$ such that $(a \times x) \pmod{m} = 1$. It exists only if $a$ and $m$ are coprime.

How does the Euclidean algorithm relate to prime factorization?

While prime factorization can be used to find the GCD by comparing prime factors, it is computationally slow. The Euclidean algorithm finds the GCD much faster without factoring.

What does coprime mean?

Two integers are coprime (or relatively prime) if their greatest common divisor is 1: $\gcd(a, b) = 1$.

Why does the Euclidean algorithm always terminate?

It must terminate because the remainders form a strictly decreasing sequence of non-negative integers ($r_1 > r_2 > r_3 \dots \geq 0$), which must eventually reach zero.

Can the Euclidean algorithm handle negative numbers?

Yes. The GCD of negative numbers is calculated by taking their absolute values: $\gcd(a, b) = \gcd(|a|, |b|)$.

What is the complexity of the Euclidean algorithm?

The algorithm has logarithmic complexity: $O(\log(\min(a, b)))$. Lamé's Theorem states that the number of steps is never more than 5 times the number of digits of the smaller number.

What is a linear Diophantine equation?

A Diophantine equation of the form $ax + by = c$ has integer solutions for $x$ and $y$ if and only if the GCD of $a$ and $b$ divides $c$.

How are Bézout coefficients kept within bounds?

Bézout coefficients satisfy $|x| < |b|/\gcd(a,b)$ and $|y| < |a|/\gcd(a,b)$. If a solution is found, other solutions can be written as $x + k(b/d)$ and $y - k(a/d)$.

Is the GCD commutative?

Yes, $\gcd(a, b) = \gcd(b, a)$ for any integers $a$ and $b$.

math calculator

Extended Euclidean GCD Solver

Compute GCD of two numbers and find Bézout coefficients using the Extended Euclidean algorithm.

Formula Verified by Dr. Elena Rostova, PhD

Inputs

Integer a

Integer b

Results

Greatest Common Divisor (GCD)

Bézout Coefficient x-9

Bézout Coefficient y47

Modular Inverse StatusSince GCD = 2 ≠ 1, the modular inverse does not exist.

Euclidean Division Steps

\[240 = 5 \times 46 + 10\]

\[46 = 4 \times 10 + 6\]

\[10 = 1 \times 6 + 4\]

\[6 = 1 \times 4 + 2\]

\[4 = 2 \times 2 + 0\]

Extended Euclidean Steps

Initialize Extended coefficients:

$s_0 = 1, \; s_1 = 0, \; t_0 = 0, \; t_1 = 1$.

Step 1: coefficient updates using quotient $q = 5$:

\[s = 1 - (5) \times 0 = 1\]

\[t = 0 - (5) \times 1 = -5\]

Step 2: coefficient updates using quotient $q = 4$:

\[s = 0 - (4) \times 1 = -4\]

\[t = 1 - (4) \times -5 = 21\]

Step 3: coefficient updates using quotient $q = 1$:

\[s = 1 - (1) \times -4 = 5\]

\[t = -5 - (1) \times 21 = -26\]

Step 4: coefficient updates using quotient $q = 1$:

\[s = -4 - (1) \times 5 = -9\]

\[t = 21 - (1) \times -26 = 47\]

Step 5: coefficient updates using quotient $q = 2$:

\[s = 5 - (2) \times -9 = 23\]

\[t = -26 - (2) \times 47 = -120\]

Bézout\'s Identity check: \[(-9) \times 240 + (47) \times 46 = 2\]

Formula

Euclidean GCD & Bézout Formulas

a = q \cdot b + r, \quad ax + by = \gcd(a, b)

The standard algorithm computes the remainder r repeatedly until r=0. The Extended algorithm solves for x and y coefficients backward.

Step by step

How the calculation works

1Enter two positive integers (a and b) to calculate their Greatest Common Divisor.
2The division list shows the dividend, quotient, and remainder for each step.
3The extended steps display the Bézout coefficients s and t to solve the linear combination.

Related guides

Learn more about this calculation

Guide

Fraction Operations Guide: Add, Subtract, Multiply, Divide

Learn the rules for adding, subtracting, multiplying, and dividing fractions, with simplification steps and live DTC calculator workflows.

Site Guide

How to Use Do The Calculation Calculators: A Practical Step-by-Step Guide

Learn the fastest reliable workflow for using Do The Calculation calculators, reading results, checking formulas, and using save, print, share, and export actions correctly.

Factorization

Prime Factorization

Factor numbers to find GCD and LCM.

Long Division

Solve step-by-step divisions with remainders.

math calculator

Extended Euclidean GCD Solver

Compute GCD of two numbers and find Bézout coefficients using the Extended Euclidean algorithm.

Formula Verified by Dr. Elena Rostova, PhD

Inputs

Integer a

Integer b

Results

Greatest Common Divisor (GCD)

Bézout Coefficient x-9

Bézout Coefficient y47

Modular Inverse StatusSince GCD = 2 ≠ 1, the modular inverse does not exist.

Euclidean Division Steps

\[240 = 5 \times 46 + 10\]

\[46 = 4 \times 10 + 6\]

\[10 = 1 \times 6 + 4\]

\[6 = 1 \times 4 + 2\]

\[4 = 2 \times 2 + 0\]

Extended Euclidean Steps

Initialize Extended coefficients:

$s_0 = 1, \; s_1 = 0, \; t_0 = 0, \; t_1 = 1$.

Step 1: coefficient updates using quotient $q = 5$:

\[s = 1 - (5) \times 0 = 1\]

\[t = 0 - (5) \times 1 = -5\]

Step 2: coefficient updates using quotient $q = 4$:

\[s = 0 - (4) \times 1 = -4\]

\[t = 1 - (4) \times -5 = 21\]

Step 3: coefficient updates using quotient $q = 1$:

\[s = 1 - (1) \times -4 = 5\]

\[t = -5 - (1) \times 21 = -26\]

Step 4: coefficient updates using quotient $q = 1$:

\[s = -4 - (1) \times 5 = -9\]

\[t = 21 - (1) \times -26 = 47\]

Step 5: coefficient updates using quotient $q = 2$:

\[s = 5 - (2) \times -9 = 23\]

\[t = -26 - (2) \times 47 = -120\]

Bézout\'s Identity check: \[(-9) \times 240 + (47) \times 46 = 2\]

Formula

Euclidean GCD & Bézout Formulas

a = q \cdot b + r, \quad ax + by = \gcd(a, b)

The standard algorithm computes the remainder r repeatedly until r=0. The Extended algorithm solves for x and y coefficients backward.

Step by step

How the calculation works

1Enter two positive integers (a and b) to calculate their Greatest Common Divisor.
2The division list shows the dividend, quotient, and remainder for each step.
3The extended steps display the Bézout coefficients s and t to solve the linear combination.

Related guides

Learn more about this calculation

Guide

Solve step-by-step divisions with remainders.