The Frobenius Coin Problem. Consider the equation ax + by = c where a, b, c, x,

Question

The Frobenius Coin Problem. Consider the equation ax + by = c where a, b, c, x, y are natural numbers. We can think of $a and $b as two denominations of coins and $c as some value that we want to pay. The equation has a solution (x, y) are elements of N2 if and only if we can make change for $c, and in this case we say that c is (a, b)-representable. More generally, we will consider the set of (a, b)-representations of c:

Ra,b,c := {(x, y) are elements of N2 : ax + by = c}. The problem is trivial when ab = 0 so we will always assume that a and b are both nonzero.

Consider natural numbers a, b, c are elements of N with d = gcd(a, b), where a = da' and b = db' .

(a) If d does NOT divide c prove that Ra,b,c = the empty set.

(b) If d divides c with c = dc' prove that Ra,b,c = Ra' ,b' ,c'. [Unlike the case of Diophantine equations, it is possible that both of these sets could be empty.] The previous result allows us to restrict our attention to coprime a and b.

Explanation / Answer

a) Let d does not divide c, then c/d is not an integer.

Suppose d divides a and b, such that a = da' and b = db'

Then the equation ax+by=c implies that

da'x+db'y=c

d(a'x+b'y)=c

(a'x+b'y)=c/d (This is not an integer)

This implies that there does not exist integers (x, y) such that ax+by=c, Hence the set, R_a, b, c is emptly.

b) if d divides c then there exists an integer c' such that c=dc'

then R_a, b, c gives the equation,

ax+by=c

which implies,

da'x+db'y=dc'

a'x+b'y=c'

Hence this represents the set R_a', b', c'.

That means for each element (x, y) in R_a, b, c there exist and element a', b', c' if d is a divisor of a, b, and c, such that (x, y) is also an element of R_a', b', c'.

That means, R_a, b, c= R_a', b', c'

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.