Formula Used
The calculator uses the extended Euclidean algorithm to find integers x and y.
Bezout identity: ax + by = gcd(a, b)
Target equation: ax + by = c
A target solution exists only when gcd(a, b) divides c. If x0 and y0 solve ax + by = gcd(a, b), then scaled coefficients solve the target equation:
x = x0(c / gcd), y = y0(c / gcd)
All target solutions use a free integer k:
x = xbase + k(b / gcd), y = ybase - k(a / gcd)
How to Use This Calculator
- Enter the first integer a.
- Enter the second integer b.
- Enter an optional target value c.
- Enter a shift value k to view another valid pair.
- Press Calculate to see the result below the header.
- Use CSV or PDF to download the report.
Example Data Table
| a |
b |
gcd |
x |
y |
Identity |
Target c |
Target possible |
| 252 |
198 |
18 |
4 |
-5 |
252(4) + 198(-5) = 18 |
54 |
Yes |
| 35 |
22 |
1 |
-5 |
8 |
35(-5) + 22(8) = 1 |
7 |
Yes |
| 84 |
30 |
6 |
-1 |
3 |
84(-1) + 30(3) = 6 |
20 |
No |
Understanding Linear Combination GCD
A linear combination uses two integers with two coefficients. It has the form ax plus by. The greatest common divisor is the largest positive integer that divides both inputs. The extended Euclidean method connects these ideas. It finds numbers x and y so the expression equals the gcd.
Why Bezout Coefficients Matter
Bezout coefficients are useful in number theory. They show how the gcd can be built from the original numbers. This matters when solving Diophantine equations. It also matters when checking modular inverses. If the gcd is one, one input may have an inverse modulo the other. The calculator reports that inverse when the modulus is valid.
Working With Targets
Many problems need more than the gcd. You may need to know whether ax plus by can equal a chosen target. A solution exists only when the gcd divides that target. When it does, the base coefficients are scaled. The calculator also lets you apply a shift value. This shows another valid pair from the infinite solution family.
Practical Study Benefits
Manual Euclidean work is easy to misread. A wrong quotient can change every later coefficient. This tool gives the quotient table, the identity check, and the target check together. Students can compare each row with class notes. Teachers can use the output to explain why divisibility controls integer solutions.
Reading the Output
Start with the gcd result. Then read the Bezout identity. Next, inspect the target section. If the target is not divisible by the gcd, there is no integer pair. If it is divisible, the displayed pair verifies the equation. The CSV export helps with records. The PDF export gives a compact report for homework review.
Accuracy Notes
Integer arithmetic is exact for reasonable input sizes. Very large values may exceed server limits. Use whole numbers only. Negative inputs are allowed. The gcd is always shown as positive. Coefficients keep the sign needed for the original equation. This makes the final identity easy to verify.
Common Use Cases
Use it for fraction reduction checks, modular arithmetic, cryptography lessons, and contest practice. It also helps when finding integer combinations for constraints, balances, or repeated measurement units. These checks make abstract number rules feel practical.
FAQs
What is a linear combination of two integers?
It is an expression like ax + by, where a and b are integers and x and y are integer coefficients. This calculator finds coefficients that create the gcd or a chosen target.
What does the gcd result mean?
The gcd is the greatest positive integer that divides both entered values. It is also the smallest positive value reachable by an integer linear combination of the two values.
Why are Bezout coefficients useful?
Bezout coefficients prove how the gcd can be written from the original integers. They are useful for modular inverse work, Diophantine equations, and number theory practice.
Can the calculator solve ax + by = c?
Yes. Enter c as the target. An integer solution exists only when the gcd of a and b divides c. The calculator shows the scaled solution when possible.
What is the shift value k?
The shift value selects another solution from the full solution family. When one solution exists, infinitely many exist, and k moves along that family.
When is a modular inverse available?
A modular inverse is available when the gcd is one and the modulus is greater than one. The calculator reports inverse values from the Bezout coefficients.
Can I use negative integers?
Yes. Negative integers are accepted. The gcd remains positive, while the coefficients keep signs that make the original identity true.
What do the CSV and PDF buttons do?
They download the current calculation report. CSV is useful for spreadsheets. PDF is useful for saving or printing a compact explanation of the result.