Frobenius Equation in Two Variables
Frobenius Equation in Two Variables
The Frobenius equation in two variables is a Diophantine equation , where and . The Frobenius number of the coefficients and , where and are relatively prime, is the largest for which the equation has no non-negative solutions. Sylvester (1884) showed that .
ax+by=c
a>0
b>0
a
b
a
b
c
ax+by=c
c=ab-a-b
The equation has the intercept form and only two non-negative solutions and (brown points). The difference between the solutions (as vectors) is .
ax+by=ab
x/b+y/a=1
(b,0)
(0,a)
(b,-a)
The Diophantine equation , where and are relatively prime, has at least one solution, and the difference between two consecutive solutions is . If , , and , the equation has, because of this difference, at least one non-negative solution.
ax+by=c
a
b
±(b,-a)
a>0
b>0
c≥ab
The equation can be written in the form and has solutions and (the magenta points). It has no non-negative solution. Any equation , has exactly one non-negative solution (the green point). It is inside the parallelogram determined by brown and magenta points.
ax+by=ab-a-b
(x+1)/b+(y+1)/b=1
(b-1,-1)
(-1,a-1)
ax+by=ab-d
d=1,...,a+b-1