Extended Euclidean Algorithm Calculator

Extended Euclidean Algorithm:

\[ \gcd(a, b) = a \times x + b \times y \]

GCD (a, b):

Coefficient x:

Coefficient y:

Unit Converter ▲

Unit Converter ▼

From:	To:

1. What is the Extended Euclidean Algorithm?

The Extended Euclidean Algorithm is an extension of the Euclidean algorithm that computes not only the greatest common divisor (GCD) of two integers a and b, but also the coefficients x and y (called Bézout coefficients) such that gcd(a, b) = a × x + b × y.

2. How Does the Calculator Work?

The calculator uses the Extended Euclidean Algorithm:

\[ \gcd(a, b) = a \times x + b \times y \]

Where:

\( a \) — First integer value
\( b \) — Second integer value
\( \gcd(a, b) \) — Greatest common divisor of a and b
\( x, y \) — Bézout coefficients (integers)

Explanation: The algorithm recursively finds the GCD while keeping track of the coefficients that express the GCD as a linear combination of the original numbers.

3. Importance of Extended GCD

Details: The Extended Euclidean Algorithm is crucial in number theory and cryptography, particularly for computing modular inverses and solving linear Diophantine equations.

4. Using the Calculator

Tips: Enter two positive integers. The calculator will compute their GCD and find integers x and y such that the GCD can be expressed as a linear combination of the input numbers.

5. Frequently Asked Questions (FAQ)

Q1: What are Bézout coefficients?
A: Bézout coefficients are integers x and y such that gcd(a, b) = a × x + b × y. They exist for any pair of integers (a, b) by Bézout's identity.

Q2: How is this different from regular Euclidean algorithm?
A: The regular Euclidean algorithm only computes the GCD, while the extended version also finds the coefficients that express the GCD as a linear combination.

Q3: What's the practical use of this algorithm?
A: It's used in cryptography (e.g., RSA), solving linear congruences, and finding modular inverses which are essential in many cryptographic protocols.

Q4: Can the coefficients be negative?
A: Yes, one or both coefficients can be negative depending on the input values.

Q5: Is the solution unique?
A: No, there are infinitely many pairs (x, y) that satisfy the equation, but the algorithm finds one particular solution.