Calculator
Example Data Table
| a | b | gcd(a,b) | x | y | Identity |
|---|---|---|---|---|---|
| 48 | 18 | 6 | -1 | 3 | 48(-1) + 18(3) = 6 |
| 252 | 198 | 18 | 4 | -5 | 252(4) + 198(-5) = 18 |
| 119 | 34 | 17 | 1 | -3 | 119(1) + 34(-3) = 17 |
| -81 | 57 | 3 | 7 | 10 | -81(7) + 57(10) = 3 |
Formula Used
The calculator uses the Extended Euclidean Algorithm. It finds the greatest common divisor and the Bézout coefficients for the identity below.
gcd(a,b) = ax₀ + by₀
After finding one base solution (x₀, y₀), the calculator also gives the full family of solutions.
x = x₀ + k(b / gcd(a,b))
y = y₀ - k(a / gcd(a,b))
Here, k is any integer. The Euclidean division chain is also shown, because the gcd comes from repeated quotient and remainder steps.
How to Use This Calculator
- Enter any whole number for
a. - Enter any whole number for
b. - Choose an integer value for
k. - Press the calculate button.
- Read the gcd, the base coefficients, and the adjusted coefficients.
- Check the Euclidean table and graph for the remainder pattern.
- Use CSV or PDF export if you need a saved copy.
About GCD Linear Combinations
A gcd linear combination calculator helps you express the greatest common divisor of two integers as a combination of those same integers. This idea matters in number theory, algebra, modular arithmetic, cryptography, and proof writing. When two integers are given, the gcd is the largest positive integer dividing both values without leaving a remainder. The Extended Euclidean Algorithm goes further and returns coefficients that make Bézout’s identity true.
For example, if the gcd of two numbers is 18, the calculator finds integers x and y so that ax + by = 18. That is useful when solving Diophantine equations, simplifying ratios, checking divisibility structure, and finding modular inverses when the gcd equals 1. The repeated quotient and remainder pattern also shows why the algorithm is fast, even for large inputs.
This calculator accepts positive or negative integers and reports a positive gcd. It also includes a free parameter k, so you can move from one valid pair of coefficients to another. That matters because Bézout coefficients are not unique. Once one pair is known, infinitely many others follow from the standard solution formulas.
The remainder graph gives a visual view of how the Euclidean Algorithm shrinks values toward zero. The result section appears above the form after submission, so the identity, solution family, and steps are visible immediately. Export tools make it easier to keep a worksheet copy, share a result, or compare several examples while practicing integer methods.
FAQs
1. What does this calculator compute?
It finds gcd(a,b), one Bézout pair, another pair using k, and the Euclidean remainder steps.
2. Why are there coefficients x and y?
They show how the gcd can be written as a linear combination of the two integers.
3. Can I enter negative numbers?
Yes. The gcd is reported as positive, and the coefficients are adjusted to match the original signs.
4. What does the parameter k do?
It generates another valid solution from the full family of coefficient pairs.
5. Why is the Euclidean table useful?
It shows each quotient and remainder step, making the gcd process transparent and easy to verify.
6. When does a modular inverse exist?
It exists when gcd(a,b) equals 1. Then one coefficient can be used in modular inverse work.
7. What happens if one input is zero?
The calculator still works. The nonzero input becomes the gcd, and a valid coefficient pair is shown.
8. Why export CSV or PDF?
Exports help with homework records, teaching examples, worksheet creation, and saving verified step tables.