Linear Diophantine Equation Solver

Existence of Integer Solutions

Not every equation of the form a x + b y = c has an integer solution. The key quantity is the greatest common divisor (gcd) of a and b. Denote g = gcd(a, b).

The fundamental criterion is:

• If g divides c (written g | c), then there are infinitely many integer solutions (x, y).
• If g does not divide c, then there is no integer solution.

This can be expressed precisely as:

The calculator automatically checks this condition. If the gcd does not divide c, it will state that no integer solution exists.

How to use: Using the Linear Diophantine Equation Calculator

Step-by-step instructions

1. Identify your equation in the form a x + b y = c.
2. Enter the integer coefficient of x into the field labeled Coefficient a.
3. Enter the integer coefficient of y into the field labeled Coefficient b.
4. Enter the integer constant term into the field labeled Constant term c.
5. Click Solve to compute a gcd, a particular solution, and the general integer solution.

Interpreting the output

• gcd(a, b): Used to determine whether any integer solution is possible.
• Particular solution (x₀, y₀): One concrete solution the algorithm finds.
• General solution: A formula in terms of a parameter t that describes all integer solutions.

To generate specific solutions, substitute integer values of t (such as t = -2, -1, 0, 1, 2) into the general formulas for x and y.

Worked Example: Solvable Equation

Consider the equation:

12 x + 18 y = 30.

1. Compute gcd(12, 18) = 6.
2. Check divisibility: 6 divides 30, so solutions exist.
3. Use the extended Euclidean algorithm (or the calculator) to find integers u and v such that 12 u + 18 v = 6. One such pair is u = -1, v = 1, since 12 (-1) + 18 (1) = 6.
4. Scale to reach c = 30. Because 30 / 6 = 5, set x₀ = 5 u = 5 (-1) = -5 and y₀ = 5 v = 5 (1) = 5.
5. Verify: 12 (-5) + 18 (5) = -60 + 90 = 30, so (x₀, y₀) = (-5, 5) is a valid solution.

Now describe all solutions. With g = 6, the general solution is:

• x = -5 + (18 / 6) t = -5 + 3 t
• y = 5 - (12 / 6) t = 5 - 2 t

Each integer t yields a different solution pair. For example:

• t = 0: x = -5, y = 5
• t = 1: x = -2, y = 3
• t = -1: x = -8, y = 7

Example with a Zero Coefficient

Sometimes one coefficient is zero, such as:

0 x + 9 y = 27.

Here a = 0, b = 9, c = 27. The equation simplifies to 9 y = 27. The gcd is gcd(0, 9) = 9, and 9 divides 27, so integer solutions exist.

Solving directly, y = 3, and x can be any integer. Written in parametric form, one convenient solution is x₀ = 0, y₀ = 3, and all solutions are:

• x = t (any integer)
• y = 3

The calculator handles this type of degenerate case by following the same gcd logic.

Comparison of Typical Cases

Applications and Interpretation

Linear Diophantine equations model many integer-constrained problems. A few examples:

• Coin change problems: If you have coins of denominations a and b and want a total of c units, the integer solutions represent ways to combine coins to reach c.
• Scheduling and resource allocation: Tasks or items may need to be grouped in bundles of sizes a and b. An equation a x + b y = c models how many groups of each size are needed to reach a target total.
• Number theory and modular arithmetic: Solving congruences like a x ≡ c (mod m) often reduces to solving a linear Diophantine equation in two variables.

In these contexts you often care about extra constraints, such as requiring x ≥ 0 and y ≥ 0 (you cannot use a negative number of coins). The calculator provides the full integer solution set; you then restrict to values of t that make x and y satisfy your practical constraints.

Assumptions and Limitations

• Integer inputs only: The tool is designed for integer coefficients a, b, and c. If you enter decimals, they are treated according to how your browser handles the numeric input, and the mathematical theory described here assumes integers.
• Two variables: The solver handles a single equation in two unknowns x and y. It does not directly solve systems of several linear Diophantine equations or problems with three or more variables.
• Range and size of coefficients: Very large integers may cause performance or overflow issues in some environments. For typical educational and practical values (within standard 64-bit integer range), the method is reliable.
• Case a = b = 0: If both coefficients are zero, the equation is 0 x + 0 y = c. If c ≠ 0, there is no solution. If c = 0, every integer pair (x, y) is a solution. Some implementations choose to treat this as a special case and may simply report that the equation is indeterminate or that every pair is a solution.
• Sign of coefficients: Negative values of a, b, and c are fully supported by the theory. The gcd is always taken to be non-negative, and sign changes are absorbed into the particular solution.
• No built-in bounds on x and y: The tool returns unbounded parametric solutions. If you need solutions with additional constraints (for example, 0 ≤ x ≤ 100), you must manually choose appropriate integer values of t that satisfy those bounds.

FAQ and Troubleshooting

What does it mean when the tool says there is no integer solution?

This means that gcd(a, b) does not divide c. There is no pair of integers (x, y) that satisfies the equation exactly. Adjusting the coefficients slightly (for example, changing c to a nearby multiple of gcd(a, b)) may make the equation solvable.

Can I force x and y to be positive?

The calculator itself does not enforce sign constraints. However, once you have the general solution in terms of t, you can identify which integer values of t produce positive (or non-negative) values of x and y.

What if one coefficient is zero?

If a = 0, the equation reduces to b y = c. An integer solution exists only if b divides c. In that case, y = c / b and x can be any integer. The situation is symmetric if b = 0.

Formula: Is this tool suitable for modular inverse calculations?

Yes, computing the modular inverse of a modulo m (when it exists) is equivalent to solving a x + m y = 1. If the calculator finds integer x and y, then x is a modular inverse of a modulo m.

How the Extended Euclidean Algorithm Helps

The extended Euclidean algorithm is the main tool used internally by this solver. It not only computes g = gcd(a, b), but also finds integers u and v such that:

a u + b v = g.

This identity is called Bézout's relation. Once we know such integers u and v, we can scale the identity to obtain a particular solution of the target equation, provided that g divides c.

If c is a multiple of g, write c = g k for some integer k. Multiplying Bézout's relation by k gives:

a (k u) + b (k v) = g k = c,

so a particular solution is:

x₀ = k u = (c / g) u, y₀ = k v = (c / g) v.

General Form of All Solutions

Once one solution (x₀, y₀) is known, all solutions can be described parametrically. Let t be any integer. Then every solution can be written as:

• x = x₀ + (b / g) t
• y = y₀ - (a / g) t

The calculator reports one particular solution and the corresponding parametric family. Each integer value of t generates a different integer pair (x, y) that satisfies the equation.

Worked Example: No Integer Solution

Consider:

6 x + 10 y = 7.

1. Compute gcd(6, 10) = 2.
2. Check whether 2 divides 7. It does not.

Therefore, no integer pair (x, y) can satisfy the equation. The calculator will display that there is no integer solution. This is not a numerical failure; it reflects a genuine mathematical impossibility under the integer constraint.