Linear Diophantine Equation Solver

When ax + by = c Has Integer Solutions

For a linear Diophantine equation a x + b y = c, the deciding quantity is the greatest common divisor of a and b. Write g = gcd(a, b).

The solvability criterion for this equation 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 condition for a linear Diophantine equation can be expressed precisely as:

The solver checks this gcd condition automatically. When the gcd does not divide c, its result explains that the entered equation has no integer solution.

Using the Linear Diophantine Equation Solver

This Linear Diophantine Equation Solver takes the three integer coefficients in a x + b y = c and returns the gcd test and solution family.

Entering coefficients for ax + by = c

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.

Reading the Diophantine solver result

• gcd(a, b): Determines whether the entered constant can be reached by an integer pair.
• Particular solution (x₀, y₀): One concrete integer pair found by the algorithm.
• General solution: A formula using a parameter t that describes every integer pair for the equation.

To generate individual solutions from the reported family, substitute integer values of t, such as t = -2, -1, 0, 1, 2, into its formulas for x and y.

Worked Linear Diophantine Example: 12x + 18y = 30

This solvable linear Diophantine example begins with the equation 12 x + 18 y = 30.

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

For this equation, use g = 6 to describe every solution:

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

Each integer t gives a different pair for 12x + 18y = 30. For example:

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

Linear Diophantine Example with a Zero Coefficient

A linear Diophantine equation can still be solved when one coefficient is zero, as in 0 x + 9 y = 27.

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 solver handles this zero-coefficient case with the same divisibility principle, while displaying the resulting parametric form.

Linear Diophantine Solver Outcomes by Case

The table summarizes how the solver classifies the main forms of a x + b y = c.

Applications of Linear Diophantine Solutions

Linear Diophantine equations model problems where the quantities represented by x and y must be integers. 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.

These uses of a Diophantine solution commonly add extra constraints, such as requiring x ≥ 0 and y ≥ 0 because a coin count cannot be negative. The solver supplies the full integer family; restrict t afterward to obtain pairs that meet those practical conditions.

Linear Diophantine Solver Assumptions and Limitations

This Linear Diophantine Equation Solver applies the integer theory of one equation a x + b y = c, subject to the following limits.

• Integer inputs only: The tool requires integer coefficients a, b, and c. Decimal entries are rejected because the Diophantine theory and the reported solution family concern 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: The calculation uses JavaScript numeric values, so very large integers can lose exact precision. Use coefficients within JavaScript's safe-integer range when exact integer results matter.
• 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; the solver reports these cases separately.
• Sign of coefficients: Negative values of a, b, and c are supported. The gcd is taken as non-negative, with coefficient signs reflected in 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, choose integer values of t that satisfy those bounds.

Linear Diophantine Solver FAQ and Troubleshooting

These answers address common questions about entering and interpreting an equation of the form a x + b y = c.

Why ax + by = c can have no integer solution

For the entered equation, no integer solution means that gcd(a, b) does not divide c. No integer pair (x, y) can satisfy it exactly. Changing c to a multiple of gcd(a, b) would make the divisibility condition hold.

Restricting Diophantine solutions to positive x and y

The solver does not enforce sign constraints. Once it provides the general solution in terms of t, identify the integer values of t that make x and y positive or non-negative.

Solving ax + by = c when one coefficient is zero

If a = 0, the equation reduces to b y = c. An integer solution exists only if b divides c. Then y = c / b and x can be any integer; the result is symmetric when b = 0.

Using this solver for a modular inverse

Yes. Finding the modular inverse of a modulo m, when one exists, is equivalent to solving a x + m y = 1. If the solver finds integers x and y, then x is a modular inverse of a modulo m.

Extended Euclidean Algorithm for ax + by = c

The Linear Diophantine Equation Solver uses the extended Euclidean algorithm to work with the coefficients a and b. It computes g = gcd(a, b) and finds integers u and v such that:

a u + b v = g.

This identity is called Bézout's relation. Once integers u and v are known, it can be scaled into a particular solution of the target equation whenever g divides c.

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

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

so one particular solution for the entered equation is:

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

General Form of Linear Diophantine Solutions

After the solver finds one solution (x₀, y₀) to a x + b y = c, it can express all solutions with an integer parameter t. Every solution has the form:

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

The solver reports a particular solution and this matching parametric family. Each integer value of t produces an integer pair (x, y) satisfying the equation.

Worked Linear Diophantine Example with No Integer Solution

This unsolvable linear Diophantine example uses 6 x + 10 y = 7.

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 this equation. The solver displays that there is no integer solution; this result is a mathematical consequence of the gcd test, not a numerical failure.