Frobenius Equation in Two Variables

a

5

b

7

d

1

zoom

5x+7y35-d

The Frobenius equation in two variables is a Diophantine equation

ax+by=c

, where

a>0

and

b>0

. The Frobenius number of the coefficients

a

and

b

, where

a

and

b

are relatively prime, is the largest

c

for which the equation

ax+by=c

has no non-negative solutions. Sylvester (1884) showed that

c=ab-a-b

.

The equation

ax+by=ab

has the intercept form

x/b+y/a=1

and only two non-negative solutions

(b,0)

and

(0,a)

(brown points). The difference between the solutions (as vectors) is

(b,-a)

.

The Diophantine equation

ax+by=c

, where

a

and

b

are relatively prime, has at least one solution, and the difference between two consecutive solutions is

±(b,-a)

. If

a>0

,

b>0

, and

c≥ab

, the equation has, because of this difference, at least one non-negative solution.

The equation

ax+by=ab-a-b

can be written in the form

(x+1)/b+(y+1)/b=1

and has solutions

(b-1,-1)

and

(-1,a-1)

(the magenta points). It has no non-negative solution. Any equation

ax+by=ab-d

,

d=1,...,a+b-1

has exactly one non-negative solution (the green point). It is inside the parallelogram determined by brown and magenta points.