Archive for January, 2012

The Coin Problem for two denominations

January 12, 2012

The Coin Problem for two denominations is a linear diophantine equation

a_{1}x_{1}+a_{2}x_{2}=b

where a1, a2 and b are positive and a1 and a2 are unequal and have a gcd of one.  The solutions are required to be non-negative integers.

It is called a coin problem because it can be likened to the problem ‘in how many ways can change of b dollars be made in coins of denomination a1 and a2 dollars?’

The largest b for which there is no solution is called the Frobenius number, and for the two denomination case the Frobenius number is a1a2 – a1 – a2. This result is attributed to James Joseph Sylvester and a proof follows.

The equation a1x + a2y = b has an integer solution if and only if the line representing it passes through a point in the real plane whose coordinates are integers. We call such a point an integer point. If p, q is any integer point it is obvious that since a1p + a2q is an integer that every integer point lies on a line of the form a1p + a2q = b, where b is some integer. It is not hard to show using analytical geometry that the lines for which b > 0 lie above and to the right of the line a1x + a2y = 0, with a line with greater b lying above and to the right of a line with lesser b. The solutions to the Frobenius equation are integer points lying in (or on the boundaries of) the upper right hand quadrant (see figure).

Since (a1, a2) = 1 then we know from the general solution of the binary linear diophantine equation (see previous post) that if x1, y1 is some integer point on a1x + a2y = b, then so is x2 = x1 + a2t, y2 = y1 – a1t, for any integer t. The distance between these points is = t√(a12 + a22), so the distance between two adjacent integer points on the line is √(a12 + a22), and if x1 y1 is some point on the line, then x1 + a2, y1 – a1 is the point immediately to its right.

Now consider the line a1x + a2y = a1a2 – a1 – a2. The points (-1, a1-1) and (a2 – 1, -1) are adjacent integer points on this line, and since they lie outside the upper right hand quadrant there is no solution when b = a1a2 – a1 – a2, and the Frobenius number is greater than or equal to a1a2 – a1 – a2.

Now (0, a1) and (a2, 0) are adjacent integer points, and lie on the line a1x + a2y = a1a2. This line, and any line above and to the right of it has a segment of  length at least √(a12 + a22) lying in or on the boundaries of the upper right hand quadrant, and therefore must contain at least one integer point lying in or on this quadrant. Thus the Frobenius number is less than a1a2.

Finally, consider lines for which a1a2 – a1 – a2 < b < a1a2. Each such line intersects the parallelogram defined by the points (0, a1), (-1, a1-1), (a2 – 1, -1) and (a2, 0).  It has a segment of length √(a12 + a22) lying in, or on the edges of, the parallelogram and thus contain at least one integer point. However this integer point cannot be in or on the triangular segment of the parallelogram lying to the left of the y-axis (it may be on the y-axis), since the x-coordinates of all such points are greater than -1 and less than 0. Similarly it has no integer point in the triangular segment below the x-axis (but may have one on the x-axis). Thus the integer points must lie in or on the upper right hand quadrant, and thus each of the Frobenius equations for which a1a2 – a1 – a2 < b < a1a2 has a solution. Thus the Frobenius number is a1a2 – a1 – a2.

Advertisements

Binary Linear Diophantine Equations

January 4, 2012

Euclid’s Algorithm (previous post) provides a means of finding solutions, if solutions exist, of the binary linear diophantine equation

a_{1}x_{1} + a_{2}x_{2} = a_{0}

where the ak are unequal integers (if they are equal we are essentially dealing with an equation in one variable) and solutions in integers are sought.

We begin by showing that if n1 > n2 > 0 are integers we can construct integers a1 and a2 such that

a_{1}n_{1}+a_{2}n_{2}=(n_{1}, n_{2})

where (n1, n2) is the greatest common divisor of n1 and n2.  We perform the Euclidean algorithm (as described in the previous post) on n1 and n2.  If the algorithm has only k = 1 step we have

n_{1} = q_{1}n_{2} (q1 an integer) so n_{1} + (1-q_{1})n_{2} = n_{2} = (n_{1}, n_{2})

If the algorithm has k = 2 steps then

n_{1}-q_{1}n_{2}=(n_{1},n_{2})

More generally it is easy to show by induction that if the algorithm completes in k ≥ 2 steps then

a_{1}=c_{k-1}   and  a_{2} = d_{k-1} where

c_{1}=1   ;  d_{1}=-q_{1}   ;  c_{2} = -q_{2}   ;  d_{2}=1+q_{1}q_{2} and

c_{i}=c_{i-2}-q_{i-2}c_{i-1}   ;  d_{i}=d_{i-2}-q_{i-2}d_{i-1} for i ≥ 3

Proof:  The proposition is true for k = 2 and is easily shown to be true for k = 3.  Let Pi be the proposition that

n_{i+2} = c_{i+2}n_{1}+d_{i+2}n_{2}

with ci and di defined as in the proposition, and for 1 ≤ i ≤ k-1.

It is easily seen that P1 is true. Suppose the proposition is true for all values of i up to some fixed value i ≤ k – 2.  Then

n_{i+3}=n_{i+1}-q_{i+1}n_{i+2}=(c_{i+1}-q_{i+1}c_{i+2})n_{1}+(d_{i+1}-q_{i+1}d_{i+2})n_{2}

So Pi+1 is true. Consequently Pk-1 is true and nk+1 = (n1, n2) can be expressed in the form proposed.

The construction can be easily extended to all (unequal) non-zero integers n1 and n2. We simply find integers a’1 and a’2 such that a’1|n1| + a’2|n2| = (n1, n2) then set a’1=(n1/|n1|)a1 and a’2=(n2/|n2|)a2.

The following is an obvious corollary:

Let p, m, n be non-zero integers. If p divides mn and (p, m) = 1 then p divides n.  (There are integers x, y such that xp + my = (p, m) = 1.  Hence xpn + mny = n.  Since p divides the left hand side it must divide n.)

We can now state a criterion for determining whether a solution to the diophantine equation exists and, if it does, provide a method of constructing a solution:

The linear diophantine equation a1x1 + a2x2 = a0 (with a1 and a2 non-zero and unequal) has a solution only if (a1, a2) divides a0.  If x’1 and x’2 are integers such that a1x’1 + a2x’2 = (a1, a2) then

\displaystyle x_{1} = \frac {a_{0}x'_{1}}{(a_{1},a_{2})}   ;   \displaystyle x_{2} = \frac {a_{0}x'_{2}}{(a_{1},a_{2})}   is a solution.

Proof:  if there is a solution then since (a1, a2) divides a1x1 + a2x2 it must divide a0. The rest is clear on substituting.

Knowing one solution, we can now identify all solutions:

If x10, x20 is a solution of a1x1 + a2x2 = a0 (with a1 and a2 non-zero and unequal) then x1, x2 is a solution if and only if

\displaystyle x_{1}=x_{1}^{0}+ \frac {a_{2}t} {(a_{1},a_{2})}   ;   \displaystyle x_{2}=x_{2}^{0}- \frac {a_{1}t} {(a_{1},a_{2})}    where t is any integer

Proof:  the if part is easily seen by substitution.  For the converse, consider first the case a0 = 0, noting that x1 = 0, x2 = 0 is a solution. Then

\displaystyle x_{1}= \frac {-a_{2}x_{2}} {a_{1}} = \frac {-a'_{2}x_{2}} {a'_{1}}   where a1 = a’1(a1, a2) ; a2 = a’2(a1, a2)

Since (a’1, a’2) = 1 (if this were not so and there were a common divisor k > 1 then k(a1, a2) would divide a1 and a2, a contradiction) then a’1 divides x2 so

\displaystyle x_{2} = \frac {-a_{1}t} {(a_{1}, a_{2})} where t is some integer and \displaystyle x_{1} = \frac {a_{2}t} {(a_{1}, a_{2})}

The general case follows easily from the special case on noting that if x10, x20 and x1, x2 are solutions then a1(x10 -x1) + a2( x20 – x2) = 0