Calculator
Example Data Table
| a | b | gcd | One linear combination | Use case |
|---|---|---|---|---|
| 252 | 198 | 18 | 18 = (252)(4) + (198)(-5) | Euclidean algorithm practice |
| 99 | 78 | 3 | 3 = (99)(-11) + (78)(14) | Bezout identity check |
| 391 | 299 | 23 | 23 = (391)(-3) + (299)(4) | Modular arithmetic lesson |
Formula Used
The calculator uses Bezout identity. For integers a and b, there are integers x and y such that:
gcd(a, b) = ax + by
The extended Euclidean algorithm finds x and y while it finds the gcd. It repeatedly applies:
dividend = divisor * quotient + remainder
All coefficient pairs are generated with:
x(t) = x0 + (b / gcd)t y(t) = y0 - (a / gcd)t
How to Use This Calculator
- Enter the first integer in the a field.
- Enter the second integer in the b field.
- Choose a t range for alternate coefficient pairs.
- Press the calculate button.
- Read the gcd, coefficients, and verification line.
- Download the CSV or PDF report when needed.
GCD as Linear Combination Guide
What the Identity Means
The gcd as a linear combination is a core idea in number theory. It shows that the greatest common divisor of two integers can be written as ax plus by. Here a and b are the chosen integers. The values x and y are Bezout coefficients.
How the Algorithm Works
This calculator follows the extended Euclidean algorithm. It divides larger remainders by smaller remainders until the final nonzero remainder appears. That final value is the gcd. The same steps also move backward through the divisions. This backward track finds the coefficients that rebuild the gcd from the original numbers.
Why This Tool Is Useful
A normal gcd tool only gives one answer. This tool gives the gcd, coefficients, a verification line, a division table, and extra valid combinations. The extra combinations help students see why Bezout coefficients are not usually unique. When g is the gcd, every solution can be changed by adding b divided by g to x. It also subtracts a divided by g from y.
Input Rules
Negative inputs are handled carefully. The gcd is shown as a positive value. Coefficients are adjusted so the displayed equation still works with the signs you entered. Zero is also supported when only one input is zero. The pair zero and zero is rejected, because its gcd is not defined.
Learning Uses
Use the tool for algebra practice, modular arithmetic, Diophantine equations, and cryptography lessons. It is useful before solving congruences or checking whether a linear equation has integer solutions. If c is divisible by gcd a comma b, then ax plus by equals c has integer solutions.
Export and Review
The step table is designed for audit work. Each row shows the dividend, divisor, quotient, and remainder. This makes mistakes easier to find. The alternate combination table shows nearby coefficient pairs. You can set a small t range to explore them.
The CSV export stores the main answer and tables. The PDF option saves the visible report. Both options help keep homework, notes, and worked examples organized. For deeper study, compare the first coefficient pair with the generated families. Notice how the gcd remains unchanged. This pattern explains why the algorithm is reliable. It also shows how simple integer division can solve larger number problems without guessing. Use exact integers when possible for best clarity.
FAQs
What is a gcd as a linear combination?
It is a way to write the greatest common divisor as ax plus by. The numbers x and y are integer coefficients.
What are Bezout coefficients?
Bezout coefficients are the integers x and y that make gcd(a, b) equal to ax plus by.
Can the coefficients be negative?
Yes. Bezout coefficients are often negative. A negative coefficient still gives a valid linear combination when the equation verifies the gcd.
Are x and y unique?
No. One pair is found first. Infinitely many other pairs can be generated with the t based formulas shown in the result.
Can I enter negative integers?
Yes. The calculator keeps the gcd positive and adjusts coefficients so the identity matches your signed inputs.
What happens if one number is zero?
The gcd equals the absolute value of the nonzero number. The calculator still gives a valid coefficient pair.
Why is gcd(0, 0) not allowed?
Every integer divides zero. Because there is no greatest positive divisor, gcd(0, 0) is undefined.
Why download CSV or PDF files?
CSV is useful for spreadsheets. PDF is useful for sharing or printing the visible solution report.