Linear Diophantine equation

Summary

A linear Diophantine equation in two unknowns is an equation $a x + b y = c$ with given integers $a$, $b$ and $c$. Its solutions are the pairs of integers $(x, y)$ that satisfy it. When $a$ and $b$ are not both $0$, the equation has an integer solution if and only if $\gcd(a, b)$ divides $c$. In this case, let $d = \gcd(a, b)$ and let $(x_0, y_0)$ be one solution. Then the solutions are the pairs $(x_0 + k b / d, \; y_0 - k a / d)$ with $k$ an integer.

Remarks

Bézout's identity gives the existence of a solution, and the extended Euclidean algorithm computes one. For example, $6 x + 10 y = 7$ has no integer solution, because $\gcd(6, 10) = 2$ does not divide $7$. The equation is a special case of a Diophantine equation.

Explanations

L1 human

Ask whether you can pay $c$ with coins of value $a$ and $b$, when you can also get coins back as change. Each amount that you can pay is a multiple of $\gcd(a, b)$, and each such multiple is possible. For example, $3 x + 5 y = 1$ has the solution $x = 2$, $y = -1$.