# Extended Euclidean Algorithm (ax + by = gcd(a, b))

Bézout coefficients for any-sign integers with the full division-step table, lcm, and optional linear Diophantine solving (particular + general solution).

> Canonical page: https://elysiatools.com/en/tools/extended-euclidean-algorithm

- **Category:** Math & Numbers

- **Keywords:** extended euclidean, bezout identity, bezout coefficients, gcd, diophantine equation, linear diophantine, number theory, back substitution

## Overview

The Extended Euclidean Algorithm tool calculates the greatest common divisor (gcd), least common multiple (lcm), and Bézout coefficients (x, y) satisfying ax + by = gcd(a, b) for any pair of signed integers. It generates full step-by-step division tables and optionally solves linear Diophantine equations of the form ax + by = c with particular and general solution families.

## Inputs

- **Value a** (text): First integer; negative values are supported.
- **Value b** (text): Second integer; negative values are supported.
- **Right-hand side c (optional, solves ax + by = c)** (text): Optional target: solves ax + by = c when gcd(a, b) divides c.
- **Output style** (select)

## When to use

- When computing Bézout coefficients to find modular multiplicative inverses in cryptography or number theory.
- When solving linear Diophantine equations ax + by = c to find integer solutions and general parametric forms.
- When verifying discrete math or algebra homework with step-by-step Euclidean division and remainder tracking.

## How it works

- Enter two non-zero integers a and b (negative values are accepted).
- Optionally enter integer c to solve the linear Diophantine equation ax + by = c.
- Choose between a concise result summary or the full division-step table.
- The tool computes the quotients, remainders, Bézout coefficients, gcd, and lcm, verifying the resulting equations.

## Use cases

- Modular arithmetic computations such as calculating private exponents in RSA encryption.
- Classroom teaching and academic grading to demonstrate step-by-step back-substitution in the Euclidean algorithm.
- Solving word problems that require integer constraints, such as coin combinations or scheduling periods.

## Frequently asked questions

### What is the Bézout identity?

It is a theorem stating that for integers a and b with gcd(a, b) = d, there exist integers x and y such that ax + by = d.

### Can I use negative integers for a and b?

Yes, negative integers are supported; the algorithm tracks signs appropriately and outputs positive gcd values.

### What happens if gcd(a, b) does not divide c?

The tool will state that no integer solutions exist for the equation ax + by = c.

### How does the tool calculate the general solution to ax + by = c?

Given a particular solution (x₀, y₀), the general solution is expressed as x = x₀ + (b/d)t and y = y₀ - (a/d)t, where d = gcd(a, b) and t ∈ ℤ.

### Does the tool output the least common multiple (lcm)?

Yes, the least common multiple is calculated alongside the gcd using the relation lcm(a, b) = |a · b| / gcd(a, b).

## Related tools

- [Boolean Algebra Simplifier (Karnaugh Map)](https://elysiatools.com/en/tools/boolean-algebra-simplifier): Minimal SOP via Quine–McCluskey with essential prime implicants, exact minimum cover, Gray-coded Karnaugh map, and full-assignment verification.
- [Dilution Ratio Converter (1:X ↔ 1/X ↔ %)](https://elysiatools.com/en/tools/dilution-ratio-converter): Convert dilution notations 1:X ↔ 1/X ↔ percent, with dilution factor, parts, and mixing volumes.
- [Modular Inverse Calculator (Extended Euclidean Algorithm)](https://elysiatools.com/en/tools/modular-inverse-calculator): a⁻¹ mod m via extended Euclid with Bézout coefficients, an optional step table, and an a × a⁻¹ ≡ 1 (mod m) verification; RSA-sized inputs supported.
- [Modular Arithmetic Calculator (Add / Subtract / Multiply / Inverse / Power)](https://elysiatools.com/en/tools/modulo-arithmetic-converter): Exact BigInt modular arithmetic for values up to 10¹⁸: (a ± b) mod m, (a × b) mod m, a⁻¹ mod m via extended Euclid, and aᵇ mod m via fast exponentiation.
- [Truth Table Generator](https://elysiatools.com/en/tools/truth-table-generator): Complete truth table (≤ 6 variables, 64 rows) with alphabetical variable order, per-row function values, and canonical Σm/ΠM forms.
- [Angular Velocity Converter (rad/s / rpm / deg/s / Hz)](https://elysiatools.com/en/tools/angular-velocity-converter): Convert angular velocity (angular speed) between radian per second (rad/s, SI base), revolutions per minute (rpm = 2π/60 rad/s), degrees per second (deg/s = π/180 rad/s), and hertz (Hz, used as revolution per second = 2π rad/s). Converts via rad/s to the target unit and lists all four equivalents. Note: 1 Hz in angular-frequency context means one full revolution per second, so 1 Hz = 2π rad/s ≈ 6.283185307 rad/s. Reference: vinyl LP 33⅓ rpm ≈ 3.49 rad/s, car engine idle ~800 rpm ≈ 83.8 rad/s.
- [Duct Size Calculator (Flow Rate × Velocity)](https://elysiatools.com/en/tools/duct-size-calculator): Size a duct cross-section from the air flow rate Q and the design mean velocity v: area A = Q/v. Circular duct diameter D = √(4A/π). Rectangular duct with aspect ratio r = a/b gives b = √(A/r) and a = r·b, plus the ASHRAE equivalent diameter D_eq = 1.30·(a·b)^0.625/(a+b)^0.25. Flow rate in m³/s/m³/h/CFM, velocity in m/s; dimensions reported in mm and inches.
- [Fatigue Limit Calculator (Goodman / Gerber / Soderberg)](https://elysiatools.com/en/tools/fatigue-limit-calculator): Mean-stress fatigue correction under cyclic loading. Given stress amplitude σ_a, mean stress σ_m, and material σ_uts / σ_-1 (endurance limit) / σ_y, compute safety factors from three classical criteria: Modified Goodman (linear, conservative), Gerber (parabolic, better for ductile metals), and Soderberg (uses σ_y, most conservative). Reports the governing (smallest) value and whether the operating point lies inside the Goodman line.

## Samples

- [Web Image Processing Python Samples](https://elysiatools.com/en/samples/web-image-processing-python): Web Python image processing examples using PIL/Pillow including reading, saving, resizing, and format conversion
- [Android Image Processing Java Samples](https://elysiatools.com/en/samples/android-image-processing-java): Android Java image processing examples including reading/saving images, scaling, and format conversion
- [Android Image Processing Kotlin Samples](https://elysiatools.com/en/samples/android-image-processing-kotlin): Android Kotlin image processing examples including reading/saving images, scaling, and format conversion
- [Web Image Processing Rust Samples](https://elysiatools.com/en/samples/web-image-processing-rust): Web Rust image processing examples including image read/save, scaling, and format conversion