Linear Diophantine Equations in Two Variables

a

5

b

7

c

33

zoom

show arrows

A linear Diophantine equation in two variables has the form

ax+by=c

, with

a

,

b

, and

c

integers, where solutions are sought in integers. The corresponding homogeneous equation is

ax+by=0

, and it always has infinitely many solutions

(

x

k

,

y

k

)=k(-b,a)/gcd(a,b)

, where

k

is an integer. If

(x,y)

is a solution of the nonhomogeneous equation, all of its solutions are of the form

(x,y)+(

x

k

,

y

k

)

. Suppose

a

and

b

are positive and relative prime. Then the distance between two consecutive solutions is

2

a

+

2

b

, so the equation always has a solution in non-negative integers if

c≥ab

.