Theorem

Integer solutions of $a x + b y = c$

Algebra • Equations • Linear Equations

Formula

x = x_{0} + b t, y = y_{0} - a t (t an integer)

For integers

a, b, c

with

a, b

not both zero,

a x + b y = c

has an integer solution if and only if

HCF (a, b)

divides

c

. When

HCF (a, b) = 1

and

(x_{0}, y_{0})

is any one integer solution, every integer solution is

x = x_{0} + b t

y = y_{0} - a t

for some integer

t

, and distinct

t

give distinct solutions.

How to use it

1Find one solution by trying $x = 0, 1, 2, \dots$ until $c - a x$ is a multiple of $b$ ; that search ends within $b$ steps.
2Then write the whole family with the step $(+ b, - a)$ — the coefficients swap sides, and one of them changes sign.
3To count solutions inside given bounds, impose the bound on each variable separately, intersect the two ranges of $t$ , and remember both endpoints are solutions.

Worked example

Find all integer solutions of

3 x + 5 y = 11

Step-by-step

1
$HCF (3, 5) = 1$ , which divides $11$
Why: So integer solutions exist.
2
$x = 2, y = 1$ works: $6 + 5 = 11$
Why: Testing $x = 0, 1, 2$ finds the first fit.
3
$x = 2 + 5 t, y = 1 - 3 t$
Why: Step by $(+ b, - a) = (+ 5, - 3)$ , which leaves $3 x + 5 y$ unchanged.

Answer

x = 2 + 5 t, y = 1 - 3 t

for every integer

t

Watch out

The step is

(+ b, - a)

, not

(+ a, - b)

— swapping them loses every solution but the one you started from. When

HCF (a, b) = d > 1

, divide the whole equation by

d

first; using the undivided coefficients as the step skips

d - 1

out of every

d

solutions. And

HCF (a, b) ∤ c

means there are no integer solutions at all, which is a legitimate answer.

Builds on

Coprime means no shared prime factor Dividend

=

divisor

\times

quotient

+

remainder

Also known as

linear diophantine equation, integral solutions of ax+by=c, integer solutions of a linear equation in two variables, diophantine, general solution of ax+by=c

Appears in past papers

2020 (I)

Q42