Solvability of a linear Diophantine equation in two unknowns

Builds on Greatest common divisor Linear Diophantine equation

Statement

Let $m$ , $n$ and $c$ be positive integers. Consider the linear Diophantine equation $a m + b n = c$ in the unknowns $a$ and $b$ , where $a$ and $b$ may be any integers, negative ones included.

This equation has an integer solution $(a, b)$ if and only if $c$ is a multiple of the greatest common divisor of $m$ and $n$ .

Remarks

One direction is easy. The number $\gcd(m, n)$ divides $a m + b n$ for all integers $a$ and $b$ , so it divides $c$ when a solution exists.

The other direction follows from Bézout's identity. If $c = k \gcd(m, n)$ , multiply a Bézout pair by $k$ .

For example, $6a + 10b = 7$ has no solution, since $\gcd(6, 10) = 2$ does not divide $7$ . But $6a + 10b = 8$ has the solution $a = -2$ , $b = 2$ .

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Divisibility definition
Linear Diophantine equation concept
Greatest common divisor definition
Solvability of a linear Diophantine equation in two unknowns statement

Tag	`DK7W1HZDDG`
URI	`m2://DK7W1HZDDG`
Kind	statement, theorem
Writing	W1 stated
MSC	11D04, 11A05
Status	This copy of the site has no build data. Run `m2 status DK7W1HZDDG`.
About	Linear Diophantine equation
Uses	Greatest common divisor, Linear Diophantine equation
Changed	4 November 2026

Solvability of a linear Diophantine equation in two unknowns

Statement

Remarks

Reading path

Further reading

What this page needs for W2

What links here