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

Extended Euclidean Algorithm (ax + by = gcd(a, b)) | Online Free Tool | Elysia Tools

Tool usage guide

Learn when to use this tool, what it supports, and how real users apply it.

Key facts

Category: Math & Numbers
Input types: text, select
Output type: text
Sample coverage: 4
API ready: Yes

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.

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

1Enter two non-zero integers a and b (negative values are accepted).
2Optionally enter integer c to solve the linear Diophantine equation ax + by = c.
3Choose between a concise result summary or the full division-step table.
4The 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.

Examples

1. Finding Bézout Coefficients with Step-by-Step Table

Computer Science Student

Background

A student needs to show each division step when computing gcd(240, 46) and finding integers x and y for 240x + 46y = gcd(240, 46).

Problem

Manual forward division and back-substitution are prone to sign errors.

How to use

Set Value a to 240, Value b to 46, leave c empty, and select 'Show division steps'.

Outcome

Displays the full table of remainders r = a·s + b·t, confirming gcd(240, 46) = 2, Bézout identity 240·(-9) + 46·47 = 2, and lcm = 5520.

2. Solving a Linear Diophantine Equation

Math Educator

Background

An instructor wants to provide worked examples for the integer equation 240x + 46y = 4.

Problem

Needs both the particular integer solution and the parametric general solution family for the lecture notes.

How to use

Input 240 for Value a, 46 for Value b, 4 for target c, and choose 'Result and verification'.

Outcome

Identifies that 2 divides 4, producing particular solution x = -18, y = 94, and general solution x = -18 + 23t, y = 94 - 120t for t ∈ ℤ.

FAQ

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).

Run this tool

Examples that match this tool

Continue with connected tools and hubs

Learn when to use this tool, what it supports, and how real users apply it.

Key facts

Overview

When to use

How it works

Use cases

Examples

1. Finding Bézout Coefficients with Step-by-Step Table

2. Solving a Linear Diophantine Equation

FAQ

Web Image Processing Python Samples

Android Image Processing Java Samples

Android Image Processing Kotlin Samples

Web Image Processing Rust Samples

Boolean Algebra Simplifier (Karnaugh Map)

Dilution Ratio Converter (1:X ↔ 1/X ↔ %)

Modular Inverse Calculator (Extended Euclidean Algorithm)

Modular Arithmetic Calculator (Add / Subtract / Multiply / Inverse / Power)