Linear Diophantine Equation Solver

Use this Linear Diophantine Equation Solver to enter values, adjust options, and review results in a compact responsive workspace.

Results are calculated automatically as you enter data.

Coefficient a Coefficient b Constant c Find a small solution

Optional bounded solutions

Restrict x and y ranges

x min x max y min y max

GCD condition and solution steps

Result: x

Enter a, b, and c.

Result: y

Enter a, b, and c.

Disclaimer: All tools on this site are intended for educational and informational purposes only. Educational tool only; not professional advice. Integer formulas, counts, and table values are exact for supported inputs, while the graph is a sampled visual aid. See our Terms of Use.

Assumptions and limitations

This Linear Diophantine Equation Solver is for general educational use. Exact arithmetic does not guarantee that an entered model is appropriate or that every visual sample is displayed. Check the formulas, assumptions, bounds, and input values before relying on the result. Use of this calculator is subject to our Terms of Use.

▼ See explanations and tips below ▼

Related Calculators

What Is a Linear Diophantine Equation?

A linear Diophantine equation is an equation where the unknown values must be integers. In two variables, the standard form is:

$$ ax + by = c $$

Here, $a$, $b$, and $c$ are known integers, while $x$ and $y$ are the integer values you want to find.

The word “linear” means that $x$ and $y$ appear only to the first power. There are no terms such as $x^2$, $xy$, $\sqrt{x}$, or $\frac{1}{x}$. The word “Diophantine” means that only integer solutions count. A pair like $(x,y)=(2,3)$ may be valid, while a pair like $(x,y)=(2.5,3)$ is not valid for this type of problem.

Linear Diophantine equations are common in number theory, modular arithmetic, scheduling, packing, counting, and problems where fractional answers do not make sense. For example, if $x$ and $y$ count objects, people, packets, or steps, then an answer with half of an object is usually not useful.

The main question is not just “Can we solve the equation?” It is:

Can we solve the equation using integers, and if so, how do we describe all integer solutions?

Why Linear Diophantine Equations Matter

A usual algebra equation may have real-number solutions even when it has no integer solution. For example, $6x + 10y = 7$ has real-number solutions, but it has no integer solutions. Linear Diophantine equations help separate answers that are algebraically possible from answers that are possible in whole numbers.

This matters when the variables represent quantities that cannot be split into fractions. Typical examples include:

counting combinations of two item sizes;
finding integer coefficients in number theory;
solving modular arithmetic problems;
understanding lattice points on a line;
checking whether a target total can be made from two fixed increments.

The key idea is that divisibility controls whether integer solutions exist. Once one integer solution is found, all the others follow a predictable pattern.

Key Terms to Know

Integer: A whole number, including negative numbers and zero, such as $-4$, $0$, and $17$.
Greatest common divisor: The greatest positive integer that divides two integers. It is written as $\gcd(a,b)$.
Divides: The notation $g \mid c$ means that $c$ is an exact multiple of $g$.
Bézout's identity: A theorem stating that if $g=\gcd(a,b)$, then there are integers $u$ and $v$ such that $au+bv=g$.
Extended Euclidean algorithm: A method that finds $\gcd(a,b)$ and also finds Bézout coefficients $u$ and $v$.
Particular solution: One specific solution pair $(x_0,y_0)$.
General solution: A formula that describes every integer solution using an integer parameter, often called $k$.
Lattice point: A point on the coordinate plane whose coordinates are both integers.

How Solving $ax + by = c$ Works

The first step is to compute:

$$ g = \gcd(a,b) $$

For a nondegenerate equation where $a$ and $b$ are not both zero, integer solutions exist exactly when $g$ divides $c$:

$$ g \mid c $$

If $g$ does not divide $c$, there are no integer solutions.

The reason is simple: if $g$ divides both $a$ and $b$, then $g$ must divide every value of $ax+by$. So if $c$ is not divisible by $g$, the left side can never equal the right side using integers.

If $g$ does divide $c$, the extended Euclidean algorithm finds integers $u$ and $v$ such that:

$$ au + bv = g $$

Then multiply both sides by $\frac{c}{g}$:

$$ a\left(u\frac{c}{g}\right) + b\left(v\frac{c}{g}\right) = c $$

That gives one particular solution:

$$ x_0 = u\frac{c}{g} $$

$$ y_0 = v\frac{c}{g} $$

Once one solution is known, every integer solution is generated by:

$$ x = x_0 + \frac{b}{g}k $$

$$ y = y_0 - \frac{a}{g}k $$

where $k$ can be any integer.

The parameter $k$ moves from one lattice point solution to the next. Each time $k$ increases by $1$, $x$ changes by $\frac{b}{g}$ and $y$ changes by $-\frac{a}{g}$. These changes cancel each other in the expression $ax+by$, so the value of the equation stays equal to $c$.

Bounded solutions

Sometimes all integer solutions are not needed. You may only want solutions where $x$ and $y$ stay within selected ranges:

$$ x_{\min} \le x \le x_{\max} $$

$$ y_{\min} \le y \le y_{\max} $$

Using the general solution, the bounds become restrictions on $k$:

$$ x_{\min} \le x_0 + \frac{b}{g}k \le x_{\max} $$

$$ y_{\min} \le y_0 - \frac{a}{g}k \le y_{\max} $$

Solving these inequalities gives an allowed interval of integer $k$ values. The bounded solutions are exactly the solution pairs produced by those $k$ values.

Examples of Linear Diophantine Equations in Practice

Example 1: A Simple Solvable Equation

Solve:

$$ 35x + 22y = 1 $$

First find the greatest common divisor:

$$ \gcd(35,22)=1 $$

Since $1 \mid 1$, integer solutions exist.

A Bézout identity for $35$ and $22$ is:

$$ 1 = -5(35) + 8(22) $$

So one particular solution is:

$$ x_0=-5, \quad y_0=8 $$

The step sizes are:

$$ \frac{b}{g}=\frac{22}{1}=22 $$

$$ -\frac{a}{g}=-\frac{35}{1}=-35 $$

Therefore, all integer solutions are:

$$ x = -5 + 22k $$

$$ y = 8 - 35k $$

where $k$ is any integer.

For example, if $k=1$, then:

$$ x=17, \quad y=-27 $$

Check:

$$ 35(17) + 22(-27) = 595 - 594 = 1 $$

So $(17,-27)$ is another solution, not a separate coincidence. It is part of the same solution family.

Example 2: A Scaled Equation with Bounds

Suppose you want integer solutions to:

$$ 12x + 18y = 30 $$

The gcd is:

$$ \gcd(12,18)=6 $$

Since $6 \mid 30$, integer solutions exist. Dividing the equation by $6$ gives:

$$ 2x + 3y = 5 $$

One solution is:

$$ x_0=1, \quad y_0=1 $$

because:

$$ 2(1)+3(1)=5 $$

For the original equation, the step sizes are:

$$ \frac{b}{g}=\frac{18}{6}=3 $$

$$ -\frac{a}{g}=-\frac{12}{6}=-2 $$

So the full solution family is:

$$ x = 1 + 3k $$

$$ y = 1 - 2k $$

Now suppose only nonnegative solutions up to $10$ are allowed:

$$ 0 \le x \le 10, \quad 0 \le y \le 10 $$

For $x$:

$$ 0 \le 1 + 3k \le 10 $$

This allows $k=0,1,2,3$.

For $y$:

$$ 0 \le 1 - 2k \le 10 $$

This allows $k=-4,-3,-2,-1,0$.

The only $k$ value in both lists is $k=0$, so the only bounded solution in this range is:

$$ (x,y)=(1,1) $$

Example 3: A No-Solution Case

Consider:

$$ 6x + 10y = 7 $$

The gcd is:

$$ \gcd(6,10)=2 $$

But $2$ does not divide $7$. That means no integer values of $x$ and $y$ can make the equation true.

This does not mean the line has no points. It means the line has no lattice points. Over the real numbers, there are infinitely many points on the line, but none of them have both coordinates as integers.

How to Interpret the Result

A result for a linear Diophantine equation usually falls into one of several types.

Result type	What it means
GCD condition passes	$\gcd(a,b)$ divides $c$, so integer solutions exist.
GCD condition fails	$\gcd(a,b)$ does not divide $c$, so there are no integer solutions.
Particular solution	One specific pair $(x_0,y_0)$ that satisfies the equation.
General solution	A formula that gives every integer solution as $k$ ranges over all integers.
$k$ step	The fixed change in $x$ and $y$ when $k$ increases by $1$.
Bounded count	The number of integer $k$ values that keep $x$ and $y$ inside the selected ranges.

The most important result is the general solution. The particular solution is only a starting point. Unless bounds restrict the possibilities, a solvable nondegenerate two-variable linear Diophantine equation has infinitely many integer solutions.

The graph and table are helpful for seeing individual lattice points, but the formula is the complete answer. In unbounded mode, a table or graph can only show sample points from an infinite family.

Common Mistakes and Misconceptions

A common mistake is to solve $ax+by=c$ as an ordinary real-number equation and assume that any algebraic solution is acceptable. For a Diophantine equation, both $x$ and $y$ must be integers.

Another mistake is to skip the gcd test. The condition $\gcd(a,b) \mid c$ determines whether integer solutions exist. If that condition fails, no amount of rearranging will produce an integer solution.

It is also easy to treat one particular solution as the only answer. In most nondegenerate solvable cases, one solution is just the seed for the full family:

$$ x = x_0 + \frac{b}{g}k, \quad y = y_0 - \frac{a}{g}k $$

A fourth mistake is forgetting that $k$ can be negative, zero, or positive. Restricting $k$ to positive values without a reason may miss valid solutions.

When using bounds, be careful that each minimum is less than or equal to its matching maximum. For example, $x_{\min} \le x_{\max}$ must be true.

Finally, a “small” representative solution is not always unique and does not necessarily minimize ordinary straight-line distance from the origin. In this calculator, small solution mode minimizes the score $|x|+|y|$; the selected representative is included in graph and table samples when those views are available.

When to Use Linear Diophantine Equations

Use a linear Diophantine equation when you need integer solutions to a linear relationship involving two unknowns.

This is especially useful when:

two quantities combine to make a target total;
the variables count whole objects, steps, or choices;
you need to solve a congruence using an equivalent integer equation;
you want to describe all lattice points on a line;
you need to know whether a target value is reachable from two integer increments;
you want to restrict solutions to a practical integer range.

The method is not limited to positive values. Negative coefficients, negative constants, and negative solutions can all occur naturally in algebra and number theory.

Limitations and Things to Keep in Mind

This calculator is designed for two-variable linear Diophantine equations in the exact form:

$$ ax + by = c $$

It does not solve nonlinear equations, equations with more than two variables, rational or real solution sets, or equations involving powers, products of variables, roots, logarithms, or trigonometric functions.

All core values must be integers with at most 1,000 digits, excluding an optional sign. Decimals, fractions, scientific notation, blank inputs, and non-integer values are outside the supported input type.

The mathematical solution formulas are exact. There is no decimal rounding in the solution family, gcd condition, particular solution, or table values. However, a graph is a visual aid, so extremely large integer values may be too large to display clearly or safely as plotted points.

Bounds must also be integers. If bounds are enabled, the calculator restricts the solution family by finding which integer $k$ values keep both $x$ and $y$ in range. For $0x+0y=0$, it counts the bounded Cartesian product directly. In very large bounded ranges, the exact count still describes the full set even when the graph and table show only deterministic representative samples.

Special zero cases should be interpreted carefully:

If $a=0$ and $b=0$ and $c=0$, then every integer pair $(x,y)$ is a solution.
If $a=0$ and $b=0$ and $c \ne 0$, then there are no solutions.
If exactly one of $a$ or $b$ is zero, the equation fixes one variable and leaves the other variable free when the divisibility condition is satisfied.

How to Use This Calculator

Enter integer values for $a$, $b$, and $c$ in the equation $ax+by=c$.
Turn on small solution mode if you want the summary to prefer a small representative solution instead of the reference solution at $k=0$.
Turn on bounds if you only want solutions inside selected integer ranges for $x$ and $y$.
If bounds are enabled, enter $x_{\min}$, $x_{\max}$, $y_{\min}$, and $y_{\max}$.
Review the gcd condition to see whether integer solutions exist.
Use the particular solution and $k$ step to understand how the full solution family is generated.
Check the graph and table to inspect individual lattice points.
Download the graph as a PNG when the graph is available and useful.

Frequently Asked Questions

What makes an equation Diophantine?

An equation is Diophantine when its solutions are required to be integers. The same equation may have many real-number solutions but no integer solutions. For this calculator, the equation must be linear and in two variables: $ax+by=c$.

Why does $\gcd(a,b)$ have to divide $c$?

If $g=\gcd(a,b)$, then $g$ divides both $a$ and $b$. That means $g$ also divides every integer combination $ax+by$. Therefore, if $g$ does not divide $c$, the equation cannot be true for integer $x$ and $y$.

Does one particular solution give all solutions?

One particular solution gives a starting point. All other solutions come from adding $\frac{b}{g}k$ to $x$ and subtracting $\frac{a}{g}k$ from $y$, where $k$ is any integer. The full family is what describes all integer solutions.

What does the parameter $k$ mean?

The parameter $k$ indexes the lattice points on the line. Increasing $k$ by $1$ moves from one integer solution to the next by the fixed step $\left(\frac{b}{g},-\frac{a}{g}\right)$. Negative values of $k$ move in the opposite direction.

Can $a$ or $b$ be zero?

Yes. If one coefficient is zero, the equation becomes a one-variable divisibility problem with the other variable free when a solution exists. If both coefficients are zero, then $0=0$ allows every integer pair, while $0=c$ with $c \ne 0$ has no solutions.

Sources and References

Books and Open Textbooks

Ted Sundstrom. Mathematical Reasoning: Writing and Proof. Grand Valley State University ScholarWorks / Mathematics LibreTexts. Sections 8.1, “The Greatest Common Divisor,” and 8.3, “Linear Diophantine Equations.” Accessed June 28, 2026. Section 8.1 and Section 8.3.
Oscar Levin. Discrete Mathematics: An Open Introduction, 3rd edition. Open Math Books. Section 5.2, “Introduction to Number Theory,” especially “Solving Linear Diophantine Equations.” Accessed June 28, 2026. Source.

Online Educational Sources

Brian Kell. “21-110: The Extended Euclidean Algorithm.” Carnegie Mellon University, last updated February 26, 2010. Accessed June 28, 2026. Source.