Linear Diophantine Equation Solver (ax + by = c) with Euclidean Algorithm Steps

Enter the coefficients of the linear Diophantine equation ax + by = c. The equation below is linked to the input fields, so you can also edit the numbers in it directly. Change "Solutions to find" to keep only the positive integer solutions.

Coefficient a of x

Coefficient b of y

Constant c on the right

Solutions to find

Enter whole numbers only (no decimals or fractions). Negative numbers are fine. If there is no x or y term, enter 0 for its coefficient.

Result and graph

Enter the coefficients a, b and c in the fields on the left and press "Calculate". The integer solutions and a graph will appear here.

[ CLOSE ]

What you can do on this page
What is this calculation used for?
How to Use
Formulas and graphs
Symbols and terms
- Symbols
- Terms
Good to know before you start
How to calculate it in Excel
How to calculate it in Google Sheets
How to calculate it in Python
How to write it in LaTeX and other math languages (copy and paste)
How to have ChatGPT do the calculation
DataChef Features
Related Features
NumberChef Calculators List

What you can do on this page

Enter the integer coefficients $a,\ b,\ c$, and you get the pairs of integers $x,\ y$ that satisfy $ax + by = c$ (the integer solutions)
When $c$ is not a multiple of the greatest common divisor of $a$ and $b$, there are no integer solutions. The page checks this and also shows why
You can follow the division table of the Euclidean algorithm and the table that works backward through the remainders to build a particular solution, row by row
The answer is not just one pair: you get the general solution $x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t$ (where $t$ is any integer) and a table of solutions for different values of $t$
You can keep only the positive solutions or only the nonnegative ones. This solves problems like "how many $50 and $80 tickets add up to exactly $1,000?" directly

Only integers can be used as coefficients (no decimals or fractions). Each coefficient can have up to 15 digits, and $a$ and $b$ cannot both be 0.

What is this calculation used for?

Finding combinations that hit an exact amount or count

Buying only $50 and $80 tickets for exactly $1,000, weighing something with only two kinds of weights, or making an exact length from pieces of fixed lengths: problems like these, "combine things of fixed sizes to hit a target exactly", are exactly the problem of finding integer solutions of $ax + by = c$.
You cannot buy a negative number of tickets, so in practice the answer comes only after you narrow down to the positive integer solutions.

Telling which order sizes can be packed exactly

If you only have boxes of 6 and boxes of 10, whether you can pack an order of exactly $c$ items depends on whether $6x + 10y = c$ has a solution with integers that are 0 or more. The GCD of 6 and 10 is 2, so an order for an odd number of items can never be packed exactly, however you combine the boxes.
In packing food or parts, knowing which counts can be made tells you which orders you can accept and which box sizes to stock.

Measuring an exact amount with unmarked containers

The famous puzzle of measuring exactly 4 gallons with only a 5-gallon jug and a 3-gallon jug matches the integer solutions of $5x + 3y = 4$ ($x$ and $y$ count, with a sign, how many times each jug is poured in or poured out). Since $\gcd(5,\ 3) = 1$, the equation tells you in advance that these two jugs can measure any whole number of gallons.
It is the same math you use in a lab or a kitchen when you ask, "Can I measure the amount I need with only the tools I have?"

Making keys for RSA encryption on the internet

RSA encryption, which protects online banking and online shopping, builds the private key value $d$ from the public key value $e$ by solving the linear Diophantine equation $e d + \varphi k = 1$ ($\varphi$ is an integer that depends on the key). The tool used here is the same extended Euclidean algorithm as on this page.
This procedure solves it instantly even for numbers hundreds of digits long, and that is one of the things that make the encryption practical.

Production planning that uses up all the material

Suppose product A uses $a$ lb of material per unit and product B uses $b$ lb, and you want to use up exactly the $c$ lb you have. This plan is the problem of finding solutions of $ax + by = c$ in integers that are 0 or more. You cannot make half a product, so the answer must be a whole number.
The field that handles planning problems whose answers must be integers is called integer programming. It is used for production planning, staff scheduling, delivery planning and more.

Formulas and graphs

When integer solutions exist

Graph

Standard notation (the usual math form)

$c$ $=$ $\gcd(a,\ b)$ $\times$ $m$

In words (symbols replaced with words)

③ $c$: constant on the right $=$ ① $g$: GCD of $a$ and $b$ $\times$ ② $m$: some integer

The formula in words

① Multiply the $g$: GCD of $a$ and $b$

② by $m$: some integer

③ If this product can be exactly equal to the $c$: constant on the right (that is, if $c$ is a multiple of $g$), integer solutions exist. Otherwise there are none

Quick example

$2x + 4y = 6$ has integer solutions, but $2x + 4y = 5$ has none at all (in both, $\gcd(2,\ 4) = 2$)

constant on the right (6) $=$ GCD (2) $\times$ integer (3)

$\gcd(2,\ 4) = 2$

$6 = 2 \times 3 \quad \Rightarrow \quad 2 \times 1 + 4 \times 1 = 6$

$5 = 2 \times 2 + 1 \quad \Rightarrow \quad 2x + 4y \neq 5$

Key idea

Why must $c$ be a multiple of $g$? Both $a$ and $b$ are multiples of $g$, so you can write $a = g a'$ and $b = g b'$. Then the left side becomes $ax + by = g(a'x + b'y)$ As long as $x$ and $y$ are integers, the left side is always a multiple of $g$ and nothing else. So if $c$ on the right is not a multiple of $g$, no integers you plug in can make the two sides equal. On the other hand, if $c$ is a multiple of $g$, a solution always exists (Bézout's identity, the next formula, guarantees this). On the graph, the difference is whether the line $ax + by = c$ passes through lattice points (points whose $x$ and $y$ coordinates are both integers) or slips through the gaps between them.

Bézout's identity (one pair of integers from the Euclidean algorithm)

Standard notation (the usual math form)

$a x_1$ $+$ $b y_1$ $=$ $\gcd(a,\ b)$

In words (symbols replaced with words)

① $a x_1$: $a$ times the integer $x_1$ from the Euclidean algorithm $+$ ② $b y_1$: $b$ times the integer $y_1$ from the Euclidean algorithm $=$ ③ $g$: GCD of $a$ and $b$

The formula in words

① Add the term $a x_1$: $a$ times the integer $x_1$ from the Euclidean algorithm

② and the term $b y_1$: $b$ times the integer $y_1$ from the Euclidean algorithm

③ and the sum can be made equal to the $g$: GCD of $a$ and $b$ . Such integers $x_1,\ y_1$ always exist, and you find them by working back through the Euclidean algorithm

Quick example

Run the Euclidean algorithm on $7$ and $5$ and work back through the remainders ($\gcd(7,\ 5) = 1$)

$7$ times the integer $-2$ $+$ $5$ times the integer $3$ $=$ GCD (1)

$7 = 5 \times 1 + 2, \quad 5 = 2 \times 2 + 1$

$1 = 5 - 2 \times 2 = 5 - (7 - 5) \times 2 = 3 \times 5 - 2 \times 7$

$7 \times (-2) + 5 \times 3 = -14 + 15 = 1$

Key idea

Every remainder in the Euclidean algorithm can be written as a sum of integer multiples of the two original numbers. Indeed, $2 = 7 - 5$, and if you substitute this for the $2$ in the next step, $1 = 5 - 2 \times 2$, then $1$ becomes a sum of integer multiples of $7$ and $5$. The extended Euclidean algorithm does this step by step for any two numbers. The pair $x_1,\ y_1$ you find makes the GCD $g$, not $c$, so it is not yet a solution of your equation. Multiply both sides by $\dfrac{c}{g}$, and you get one solution of the equation you want. $x_0 = \dfrac{c}{g} x_1, \quad y_0 = \dfrac{c}{g} y_1$ For example, for $7x + 5y = 3$, multiply the equation above by 3 to get $7 \times (-6) + 5 \times 9 = 3$, so $(x_0,\ y_0) = (-6,\ 9)$ is one solution. This calculator shifts the solution it finds to smaller, easier-to-read numbers before showing it (whichever pair you start from, the general solution below gives the same set of solutions).

All integer solutions (general solution)

Graph

Standard notation (the usual math form)

$x$ $=$ $x_0$ $+$ $\dfrac{b}{g}$ $t$

$y$ $=$ $y_0$ $-$ $\dfrac{a}{g}$ $t$

In words (symbols replaced with words)

$x$: integer solution $=$ ① $x_0$: particular solution $+$ ② $\dfrac{b}{g}$: step size of $x$ ③ $t$: any integer

$y$: integer solution $=$ ④ $y_0$: particular solution $-$ ⑤ $\dfrac{a}{g}$: step size of $y$ $t$: any integer

The formula in words

① Start from the $x_0$: particular solution

② and add the $\dfrac{b}{g}$: step size of $x$

③ multiplied by $t$: any integer . This gives the integer solution $x$

④ At the same time, start from the $y_0$: particular solution

⑤ and subtract the $\dfrac{a}{g}$: step size of $y$ multiplied by the same $t$. This gives the integer solution $y$. Each integer you put in for $t$ gives another solution, and together they are all the integer solutions

Quick example

For $3x + 4y = 10$, one solution is $(x_0,\ y_0) = (2,\ 1)$, and $\gcd(3,\ 4) = 1$, so

$x$: integer solution $=$ particular solution (2) $+$ step size (4) integer $t$

$y$: integer solution $=$ particular solution (1) $-$ step size (3) integer $t$

$3 \times 2 + 4 \times 1 = 10$

$x = 2 + 4t, \quad y = 1 - 3t$

$t = 1 \ \Rightarrow \ (x,\ y) = (6,\ -2), \quad 3 \times 6 + 4 \times (-2) = 10$

$t = -1 \ \Rightarrow \ (x,\ y) = (-2,\ 4), \quad 3 \times (-2) + 4 \times 4 = 10$

Key idea

Why does $x$ move only in steps of $\dfrac{b}{g}$, and $y$ only in steps of $\dfrac{a}{g}$? If $(x,\ y)$ and $(x_0,\ y_0)$ are both solutions, subtracting one equation from the other gives $a(x - x_0) = -b(y - y_0)$ Divide both sides by $g$ to get $\dfrac{a}{g}(x - x_0) = -\dfrac{b}{g}(y - y_0)$. Here $\dfrac{a}{g}$ and $\dfrac{b}{g}$ are relatively prime (their only common factor is 1). So the left side must be a multiple of $\dfrac{b}{g}$. Since $\dfrac{a}{g}$ shares no factor with it, $x - x_0$ itself must be a multiple of $\dfrac{b}{g}$. That is, $x - x_0 = \dfrac{b}{g}t$, and the formula for $y$ follows from it. On the graph, the lattice points on the line $ax + by = c$ are lined up at equal spacing: $\dfrac{b}{g}$ across and $\dfrac{a}{g}$ up or down.

Narrowing down to positive integer solutions

Graph

Standard notation (the usual math form)

$x_0$ $+$ $\dfrac{b}{g}$ $t$ $\geq 1$

$y_0$ $-$ $\dfrac{a}{g}$ $t$ $\geq 1$

In words (symbols replaced with words)

① $x_0$: particular solution $+$ ② $\dfrac{b}{g}$: step size of $x$ ③ $t$: any integer $\geq 1$

④ $y_0$: particular solution $-$ ⑤ $\dfrac{a}{g}$: step size of $y$ $t$: any integer $\geq 1$

The formula in words

① The $x_0$: particular solution

② plus the $\dfrac{b}{g}$: step size of $x$

③ times $t$: any integer (that is, the integer solution $x$) must be at least 1, and

④ the $y_0$: particular solution

⑤ minus the $\dfrac{a}{g}$: step size of $y$ times the same $t$ (that is, the integer solution $y$) must also be at least 1. Find the range of $t$ that meets both, and you have every positive integer solution

Quick example

To get exactly 47 items using only packs of 3 and packs of 5 ($3x + 5y = 47$, $(x_0,\ y_0) = (4,\ 7)$):

particular solution (4) $+$ step size (5) integer $t$ $\geq 1$

particular solution (7) $-$ step size (3) integer $t$ $\geq 1$

$3 \times 4 + 5 \times 7 = 47$

$4 + 5t \geq 1 \ \Leftrightarrow \ t \geq -\dfrac{3}{5} \ \Leftrightarrow \ t \geq 0$

$7 - 3t \geq 1 \ \Leftrightarrow \ t \leq 2$

$0 \leq t \leq 2 \ \Rightarrow \ (x,\ y) = (4,\ 7),\ (9,\ 4),\ (14,\ 1)$

Key idea

In problems that count tickets, items or people, the answer must be a positive integer (or an integer that is 0 or more). Put the general solution into inequalities and find the range of $t$, and you keep only the solutions that fit. Since $t$ is an integer, even when a boundary is a fraction such as $t \geq -\dfrac{3}{5}$, you can tighten it to the nearest integer inside (here $t \geq 0$). That is the key step. If $a$ and $b$ have the same sign (for example, both positive), one inequality gives a lower bound and the other gives an upper bound, so there are always finitely many solutions. If the signs differ (for example, $3x - 5y = 1$), both limits point the same way, and there are infinitely many positive integer solutions. If one coefficient is 0 (for example, $0x + 5y = 10$), the other variable has exactly one value, and the variable with the 0 coefficient can be anything. If that one value meets the condition, there are infinitely many solutions; if not, there are none. It can also happen that no $t$ meets the condition at all. In that case the answer is "there is no combination that works".

The linear Diophantine equation $ax + by = c$ has integer solutions only when $c$ is a multiple of $g$, the greatest common divisor of $a$ and $b$. When it does, work back through the Euclidean algorithm to build one particular solution $(x_0,\ y_0)$. Then every other solution is $x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t$ (where $t$ is any integer).

Symbols and terms

Symbols

$a,\ b$	a, b	The coefficients that multiply $x$ and $y$. Letters near the start of the alphabet, $a,\ b,\ c$, are traditionally used for fixed numbers. On this page both are integers.
$c$	c	The constant on the right side of the equation, from the first letter of "constant". It is the total you want to reach, and whether it is a multiple of the GCD decides whether solutions exist.
$x,\ y$	x, y	The unknowns you solve for. Using letters near the end of the alphabet for unknowns is a habit said to have been made popular by Descartes. On this page only integer values count as answers.
$\gcd(a,\ b)$	G-C-D of a and b	The greatest common divisor of $a$ and $b$, from the first letters of "greatest common divisor". In school it is also called the greatest common factor (GCF). Number theory books sometimes shorten it to $(a,\ b)$.
$g$	g	A short name for the greatest common divisor $\gcd(a,\ b)$, from the first letter of "greatest". It keeps formulas short, as in $\dfrac{b}{g}$ and $\dfrac{a}{g}$ in the general solution.
$x_0,\ y_0$	x naught, y naught	The particular solution, that is, the first integer solution you find. The small 0 marks it as the starting point, "solution number 0". Every integer solution is written starting from here.
$x_1,\ y_1$	x sub 1, y sub 1	The pair of integers you find by working back through the Euclidean algorithm. It satisfies $a x_1 + b y_1 = g$. Multiply it by $\dfrac{c}{g}$ to get the particular solution $(x_0,\ y_0)$.
$t$	t	A variable that can be any integer (a parameter). It lets one formula describe all the integer solutions at once. Each integer you put in for $t$ gives another integer solution.
$m$	m	The integer that tells how many times $g$ goes into $c$. Letters such as $m$, $n$ and $k$ are often used for integers, and $m$ is said to come from "multiple". Integer solutions exist when $c = g \times m$ can be written, and only then.
$q$	q	The quotient of a division, from the first letter of "quotient". In the Euclidean algorithm table, it is the $2$ in $13 = 5 \times 2 + 3$.
$r$	r	The remainder of a division, from the first letter of "remainder". In the Euclidean algorithm table, it is the $3$ in $13 = 5 \times 2 + 3$. The algorithm stops when this remainder reaches 0.
$\geq$	is greater than or equal to	The inequality sign for "the left side is greater than or equal to the right side". $x \geq 1$ says that $x$ is 1 or more. Its partner $\leq$ says "less than or equal to".

Terms

linear Diophantine equation	A linear equation with two unknowns but only one equation, such as $ax + by = c$. Over the real numbers, every point on the line is a solution, so the solution is not unique. Even if you keep only integer solutions, there are usually infinitely many.
Diophantine equation	The name for equations whose answers must be integers. It comes from Diophantus, a mathematician of ancient Greece. The linear Diophantine equation on this page is the most basic kind.
integer solution	A solution of the equation where both $x$ and $y$ are integers. In problems about amounts that cannot be split, such as numbers of tickets, items or people, only integer solutions make sense.
particular solution	The first pair you find among the infinitely many integer solutions. Any pair will do. Starting from it, the general solution describes all the solutions.
general solution	All the integer solutions written as one formula using an integer $t$. Each integer you put in for $t$ gives another solution.
greatest common divisor (GCD)	The largest positive integer that divides each of two or more integers. It is also called the greatest common factor (GCF). In a linear Diophantine equation, this value decides both whether solutions exist and how far apart they are.
Euclidean algorithm	A way to find the greatest common divisor by dividing the larger number by the smaller one and replacing the pair with the divisor and the remainder, again and again. The divisor at the step where the remainder reaches 0 is the GCD. It appears in Euclid's "Elements" from around the 3rd century BC and is often called the oldest algorithm in the world.
extended Euclidean algorithm	A way to write the greatest common divisor in the form $a x_1 + b y_1$ by substituting the division equations of the Euclidean algorithm back in, from the bottom up. It is used to build a particular solution of a linear Diophantine equation.
Bézout's identity	The theorem that there always exist integers $x_1,\ y_1$ with $a x_1 + b y_1 = \gcd(a,\ b)$. It is named after the French mathematician Bézout. It is the reason a linear Diophantine equation can be solved.
relatively prime	Two integers are relatively prime (or coprime) when their greatest common divisor is 1. For example, 3 and 4 are relatively prime. $\dfrac{a}{g}$ and $\dfrac{b}{g}$ are always relatively prime, and this is why the solutions are equally spaced.
multiple	A number you get by multiplying an integer by another integer. The multiples of $10$ are $\dots,\ -20,\ -10,\ 0,\ 10,\ 20,\ \dots$. Zero and negative numbers count as multiples too.
remainder	What is left over when an integer division does not come out even. $13 \div 5$ has a quotient of $2$ and a remainder of $3$. The Euclidean algorithm works only with these remainders.
quotient	In integer division, the whole number of times the divisor fits. In $13 = 5 \times 2 + 3$, the quotient is $2$.
lattice point	A point on the coordinate plane whose $x$ and $y$ coordinates are both integers, like the corners of the squares on graph paper. The integer solutions of a linear Diophantine equation are exactly the lattice points on the line $ax + by = c$.
parameter	A variable you are free to change, used to write a whole set of solutions as one formula. On this page, $t$ is the parameter.
coefficient	The number in front of a letter. In $3x$, the coefficient is $3$. When no number is written, as in $x$, the coefficient is 1.
inequality	A statement that compares the size of two values, such as $t \geq 0$. It is used to narrow down to the positive integer solutions.

Good to know before you start

Here is what helps you use the calculation on this page with real understanding, not just by pressing the button.
If you get stuck, going back to these topics is the quickest way forward.

Division with remainders (Grades 4–6)	Knowing that $13 \div 5$ is "quotient $2$, remainder $3$", and being able to rewrite it as one equation, $13 = 5 \times 2 + 3$ Knowing that the remainder is always smaller than the divisor (at least $0$ and less than the divisor)
Factors, multiples and the GCF (Grades 4–6)	Being able to switch between "$6$ is a multiple of $3$" and "$3$ is a factor of $6$" Being able to find that the greatest common factor of $12$ and $18$ is $6$ (prime factorization is fine too) Knowing that two numbers whose GCF is $1$ are called "relatively prime"
Expressions and linear equations (Grades 6–8)	Knowing that in an expression like $ax + by$, $a$ and $b$ are coefficients and $x$ and $y$ are unknowns Being able to solve an equation like $3 \times 2 + 5y = 1$ for $y$ Being able to factor out a common number, as in $4x + 6y = 2(2x + 3y)$
Linear equations in two variables and their graphs (Grade 8)	Knowing that $ax + by = c$ is a straight line on the coordinate plane Knowing that with two unknowns and only one equation there is no single answer, and every point on the line is a solution
Inequalities (Grades 7–9)	Being able to rewrite $5t \geq 1$ as $t \geq \dfrac{1}{5}$ Knowing that dividing both sides by a negative number flips the inequality sign Knowing that if $t \leq \dfrac{5}{3}$ and $t$ is an integer, you can tighten it to $t \leq 1$
Working with fractions (Grades 5–7)	Being able to simplify a fraction such as $\dfrac{80}{10} = 8$ Being able to compare negative fractions such as $-\dfrac{3}{8}$ on a number line

How to calculate it in Excel

Copy the whole table below and paste it into cell A1 in Excel. It works as is.

Table to check whether integer solutions exist

Coefficient a of x	50
Coefficient b of y	80
Constant c on the right	1000
GCD g	=GCD(B1,B2)
Remainder of c ÷ g	=MOD(B3,B4)
Integer solutions?	=IF(B5=0,"Solutions exist","No solutions")

Table to check Bézout's identity

Coefficient a of x	50
Coefficient b of y	80
x1 from the Euclidean algorithm	-3
y1 from the Euclidean algorithm	2
a×x1 + b×y1	=B1B3+B2B4
GCD g	=GCD(B1,B2)

Table to get solutions from the general solution

Coefficient a of x	50
Coefficient b of y	80
Constant c on the right	1000
GCD g	=GCD(B1,B2)
Particular solution x0	4
Particular solution y0	10
Integer t	1
x = x0 + (b/g)×t	=B5+(B2/B4)*B7
y = y0 − (a/g)×t	=B6-(B1/B4)*B7
Check a×x + b×y	=B1B8+B2B9

Table to narrow down to positive integer solutions

Coefficient a of x	50
Coefficient b of y	80
GCD g	=GCD(B1,B2)
Particular solution x0	4
Particular solution y0	10
Lower bound of t (from x ≥ 1)	=-INT((B4-1)/(B2/B3))
Upper bound of t (from y ≥ 1)	=INT((B5-1)/(B1/B3))
Number of positive integer solutions	=MAX(0,B7-B6+1)

After pasting, the upper rows (coefficients and the particular solution) are your inputs, and the lower rows are calculated automatically. GCD gives the greatest common divisor, MOD gives the remainder of a division, and INT drops the decimal part (rounds down).
The first table uses the example 50x + 80y = 1000. The GCD is 10, and 1000 ÷ 10 leaves a remainder of 0, so it shows "Solutions exist". Change 1000 to 1001, and it changes to "No solutions".
The second table checks that x1 = −3 and y1 = 2, found by working back through the Euclidean algorithm, really satisfy Bézout's identity. 50×(−3) + 80×2 = 10, which matches the GCD.
The third table takes one solution from the general solution. Enter 1 for t, and you get x = 12 and y = 5, and the check row comes back to 1000. Try other integers for t.
The fourth table narrows down to the positive integer solutions. The lower bound of t is 0 and the upper bound is 1, so there are 2 positive integer solutions (t = 0 and t = 1). These two formulas are for the case where a and b are both positive. With a negative coefficient, the direction of the inequality flips, so be careful.

How to calculate it in Google Sheets

Copy the whole table below and paste it into cell A1 in Google Sheets. It works as is.

Table to check whether integer solutions exist

Coefficient a of x	50
Coefficient b of y	80
Constant c on the right	1000
GCD g	=GCD(B1,B2)
Remainder of c ÷ g	=MOD(B3,B4)
Integer solutions?	=IF(B5=0,"Solutions exist","No solutions")

Table to check Bézout's identity

Coefficient a of x	50
Coefficient b of y	80
x1 from the Euclidean algorithm	-3
y1 from the Euclidean algorithm	2
a×x1 + b×y1	=B1B3+B2B4
GCD g	=GCD(B1,B2)

Table to get solutions from the general solution

Coefficient a of x	50
Coefficient b of y	80
Constant c on the right	1000
GCD g	=GCD(B1,B2)
Particular solution x0	4
Particular solution y0	10
Integer t	1
x = x0 + (b/g)×t	=B5+(B2/B4)*B7
y = y0 − (a/g)×t	=B6-(B1/B4)*B7
Check a×x + b×y	=B1B8+B2B9

Table to narrow down to positive integer solutions

Coefficient a of x	50
Coefficient b of y	80
GCD g	=GCD(B1,B2)
Particular solution x0	4
Particular solution y0	10
Lower bound of t (from x ≥ 1)	=-INT((B4-1)/(B2/B3))
Upper bound of t (from y ≥ 1)	=INT((B5-1)/(B1/B3))
Number of positive integer solutions	=MAX(0,B7-B6+1)

The same formulas as in Excel work as is (GCD, MOD, INT, MAX and IF all have the same names and do the same thing). Copy the whole table, paste it into cell A1, and replace the coefficients with your own numbers.

How to calculate it in Python

from math import gcd

# coefficients of ax + by = c (integers)
a, b, c = 50, 80, 1000

def extended_gcd(x, y):
    # extended Euclidean algorithm: returns gcd and s, t with x*s + y*t = gcd
    if y == 0:
        return x, 1, 0
    g, s, t = extended_gcd(y, x % y)
    return g, t, s - (x // y) * t

g = gcd(a, b)
if c % g != 0:
    print(f"{c} is not a multiple of {g}, so there are no integer solutions")
else:
    _, s, t = extended_gcd(a, b)
    x0, y0 = s * (c // g), t * (c // g)   # particular solution (one integer solution)
    step_x, step_y = b // g, a // g       # step size of x and step size of y
    # shift until x is the smallest value that is 0 or more, for an easier-to-read solution
    n = x0 // step_x
    x0, y0 = x0 - n * step_x, y0 + n * step_y
    print(f"Particular solution: (x, y) = ({x0}, {y0})")
    print(f"General solution: x = {x0} + {step_x}t, y = {y0} - {step_y}t (t is any integer)")
    for k in range(-2, 3):
        print(f"  t = {k:2}: (x, y) = ({x0 + step_x * k}, {y0 - step_y * k})")
    # keep only the positive integer solutions (x >= 1 and y >= 1)
    t_low = -((1 - x0) // -step_x)
    t_high = (y0 - 1) // step_y
    print("Positive integer solutions:", [(x0 + step_x * k, y0 - step_y * k)
                                        for k in range(t_low, t_high + 1)])

It needs only math.gcd from the standard library and a recursive extended Euclidean algorithm. This example is 50x + 80y = 1000. Running it prints the particular solution (4, 10), the general solution x = 4 + 8t, y = 10 − 5t, and the positive integer solutions [(4, 10), (12, 5)]. Change the coefficients and try it (the last part, for positive integer solutions, is written for the case where a and b are both positive).

How to write it in LaTeX and other math languages (copy and paste)

When integer solutions exist

c = gcd(a, b) × m

c = \gcd(a, b) \times m

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>c</mi>
    <mo>=</mo>
    <mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>&#xD7;</mo>
    <mi>m</mi>
  </mrow>
</math>

c = gcd(a, b) * m

Mod[c, GCD[a, b]] == 0

irem(c, igcd(a, b)) = 0;

mod(c, gcd(a, b)) == 0

c = gcd(a,b) × m

Bézout's identity (one pair of integers from the Euclidean algorithm)

a·x₁ + b·y₁ = gcd(a, b)

a x_1 + b y_1 = \gcd(a, b)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>a</mi><msub><mi>x</mi><mn>1</mn></msub>
    <mo>+</mo>
    <mi>b</mi><msub><mi>y</mi><mn>1</mn></msub>
    <mo>=</mo>
    <mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
  </mrow>
</math>

a*x_1 + b*y_1 = gcd(a, b)

ExtendedGCD[a, b]

igcdex(a, b, x1, y1);

[g, x1, y1] = gcd(a, b);

a x_1 + b y_1 = gcd(a,b)

All integer solutions (general solution)

x = x₀ + (b/g)t, y = y₀ − (a/g)t

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

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>x</mi><mo>=</mo><msub><mi>x</mi><mn>0</mn></msub>
    <mo>+</mo>
    <mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>,</mo><mspace width="1em"/>
    <mi>y</mi><mo>=</mo><msub><mi>y</mi><mn>0</mn></msub>
    <mo>&#x2212;</mo>
    <mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
  </mrow>
</math>

x = x_0 + (b/g)t, y = y_0 - (a/g)t

Solve[a x + b y == c, {x, y}, Integers]

isolve(a*x + b*y = c);

S = solve(a*x + b*y == c, [x y], 'Integer', true);

x = x_0 + (b/g)t, y = y_0 - (a/g)t

Narrowing down to positive integer solutions

x₀ + (b/g)t ≥ 1 and y₀ − (a/g)t ≥ 1

x_0 + \frac{b}{g} t \geq 1, \quad y_0 - \frac{a}{g} t \geq 1

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <msub><mi>x</mi><mn>0</mn></msub>
    <mo>+</mo>
    <mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>&#x2265;</mo><mn>1</mn>
    <mo>,</mo><mspace width="1em"/>
    <msub><mi>y</mi><mn>0</mn></msub>
    <mo>&#x2212;</mo>
    <mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>&#x2265;</mo><mn>1</mn>
  </mrow>
</math>

x_0 + (b/g)t >= 1 and y_0 - (a/g)t >= 1

Solve[a x + b y == c && x >= 1 && y >= 1, {x, y}, Integers]

isolve({a*x + b*y = c, x >= 1, y >= 1});

S = solve([a*x + b*y == c, x >= 1, y >= 1], [x y], 'Integer', true);

x_0 + (b/g)t ≥ 1, y_0 − (a/g)t ≥ 1

How to have ChatGPT do the calculation

You are a math calculation assistant for number theory (properties of integers). Do the following calculation by actually running Python code, and base your answer only on the numbers from the execution result (do not answer by mental math or guessing).

Find the integer solutions of the linear Diophantine equation 50x + 80y = 1000.
Show each of the following:
1. The greatest common divisor of 50 and 80, and whether 1000 is a multiple of it
2. The division steps of the Euclidean algorithm (until the remainder is 0), and the x1, y1 with 50×x1 + 80×y1 = GCD found by working back through them
3. A particular solution (x0, y0) and the general solution x = x0 + (b/g)t, y = y0 − (a/g)t
4. All integer solutions where both x and y are 1 or more

In Python, use math.gcd and the extended Euclidean algorithm to calculate exactly, and show the formulas you used and the numbers from the execution result.

How to Use

1

Enter your numbers

Type the numbers you want to calculate with into the input fields
2

Calculate

Press the "Calculate" button
3

Check the result

The result appears on the spot. The same page also explains the idea behind the calculation and the formula

DataChef Features

Easy and Free

Unlimited conversions for free.
No technical knowledge required.
Intuitive and user-friendly operation.

No Registration Required

Available immediately after access.
Can be used without registering personal information.

Safe and Secure

Fully SSL encrypted communication.
Automatic file deletion by clicking "download".

Fast

High-speed site access
and rapid file conversion.

No Watermark

No watermark.
No attribution required.

Commercial Use Available

Free for commercial use.
No need to contact us for commercial use permission.

\(a,\ b\)	a, b	The coefficients that multiply \(x\) and \(y\). Letters near the start of the alphabet, \(a,\ b,\ c\), are traditionally used for fixed numbers. On this page both are integers.
\(c\)	c	The constant on the right side of the equation, from the first letter of "constant". It is the total you want to reach, and whether it is a multiple of the GCD decides whether solutions exist.
\(x,\ y\)	x, y	The unknowns you solve for. Using letters near the end of the alphabet for unknowns is a habit said to have been made popular by Descartes. On this page only integer values count as answers.
\(\gcd(a,\ b)\)	G-C-D of a and b	The greatest common divisor of \(a\) and \(b\), from the first letters of "greatest common divisor". In school it is also called the greatest common factor (GCF). Number theory books sometimes shorten it to \((a,\ b)\).
\(g\)	g	A short name for the greatest common divisor \(\gcd(a,\ b)\), from the first letter of "greatest". It keeps formulas short, as in \(\dfrac{b}{g}\) and \(\dfrac{a}{g}\) in the general solution.
\(x_0,\ y_0\)	x naught, y naught	The particular solution, that is, the first integer solution you find. The small 0 marks it as the starting point, "solution number 0". Every integer solution is written starting from here.
\(x_1,\ y_1\)	x sub 1, y sub 1	The pair of integers you find by working back through the Euclidean algorithm. It satisfies \(a x_1 + b y_1 = g\). Multiply it by \(\dfrac{c}{g}\) to get the particular solution \((x_0,\ y_0)\).
\(t\)	t	A variable that can be any integer (a parameter). It lets one formula describe all the integer solutions at once. Each integer you put in for \(t\) gives another integer solution.
\(m\)	m	The integer that tells how many times \(g\) goes into \(c\). Letters such as \(m\), \(n\) and \(k\) are often used for integers, and \(m\) is said to come from "multiple". Integer solutions exist when \(c = g \times m\) can be written, and only then.
\(q\)	q	The quotient of a division, from the first letter of "quotient". In the Euclidean algorithm table, it is the \(2\) in \(13 = 5 \times 2 + 3\).
\(r\)	r	The remainder of a division, from the first letter of "remainder". In the Euclidean algorithm table, it is the \(3\) in \(13 = 5 \times 2 + 3\). The algorithm stops when this remainder reaches 0.
\(\geq\)	is greater than or equal to	The inequality sign for "the left side is greater than or equal to the right side". \(x \geq 1\) says that \(x\) is 1 or more. Its partner \(\leq\) says "less than or equal to".

Division with remainders (Grades 4–6)	Knowing that \(13 \div 5\) is "quotient \(2\), remainder \(3\)", and being able to rewrite it as one equation, \(13 = 5 \times 2 + 3\) Knowing that the remainder is always smaller than the divisor (at least \(0\) and less than the divisor)
Factors, multiples and the GCF (Grades 4–6)	Being able to switch between "\(6\) is a multiple of \(3\)" and "\(3\) is a factor of \(6\)" Being able to find that the greatest common factor of \(12\) and \(18\) is \(6\) (prime factorization is fine too) Knowing that two numbers whose GCF is \(1\) are called "relatively prime"
Expressions and linear equations (Grades 6–8)	Knowing that in an expression like \(ax + by\), \(a\) and \(b\) are coefficients and \(x\) and \(y\) are unknowns Being able to solve an equation like \(3 \times 2 + 5y = 1\) for \(y\) Being able to factor out a common number, as in \(4x + 6y = 2(2x + 3y)\)
Linear equations in two variables and their graphs (Grade 8)	Knowing that \(ax + by = c\) is a straight line on the coordinate plane Knowing that with two unknowns and only one equation there is no single answer, and every point on the line is a solution
Inequalities (Grades 7–9)	Being able to rewrite \(5t \geq 1\) as \(t \geq \dfrac{1}{5}\) Knowing that dividing both sides by a negative number flips the inequality sign Knowing that if \(t \leq \dfrac{5}{3}\) and \(t\) is an integer, you can tighten it to \(t \leq 1\)
Working with fractions (Grades 5–7)	Being able to simplify a fraction such as \(\dfrac{80}{10} = 8\) Being able to compare negative fractions such as \(-\dfrac{3}{8}\) on a number line

Linear Diophantine Equation Solver (ax + by = c) with Euclidean Algorithm Steps

Table of Contents

What you can do on this page

What is this calculation used for?

Formulas and graphs

Symbols and terms

Symbols

Terms

Good to know before you start

How to calculate it in Excel

How to calculate it in Google Sheets

How to calculate it in Python

How to write it in LaTeX and other math languages (copy and paste)

How to have ChatGPT do the calculation

How to Use

DataChef Features

Related Features

Greatest Common Factor (GCF / GCD) Calculator

Finds the greatest common factor of two or more integers, explained with prime factorization and the Euclidean algorithm

Least Common Multiple (LCM) Calculator

Finds the least common multiple of two or more integers, and shows how it relates to the GCF

Prime Factorization Calculator

Breaks an integer down into a product of primes. Also handy for checking whether two numbers are relatively prime

System of Equations Calculator (Elimination and Substitution with Steps)

Solves a system of two linear equations with step-by-step elimination and substitution, a graph of both lines, and checks for no solution or infinitely many

Modulo Calculator (a mod n, Congruence and Modular Exponentiation)

Finds a mod n, checks whether a ≡ b (mod n) and computes modular powers, with negative numbers and repeated squaring steps

Recommended

Probability and random number

Averages and statistics

Percentage and ratio

Speed

Density and concentration

Physics and electricity

Unit conversion

Integer and signed number

Fraction, decimal and rounding

Equation and inequality

Polynomial

Square root and nth root

Exponent and logarithm

Complex number

Function and graph

Sequence

Vector

Matrix

Plane geometry

Solid geometry

Date and time

Finance and economics

Web marketing and ad metric

Health and fitness

Sports

Weather

Computer

Household energy and budget

Car

Solar power and battery

Home and DIY

Remove Ads