The Coin Problem for two denominations

The Coin Problem for two denominations is a linear diophantine equation

where a₁, a₂ and b are positive and a₁ and a₂ 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 a₁ and a₂ 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 a₁a₂ – a₁ – a₂. This result is attributed to James Joseph Sylvester and a proof follows.

The equation a₁x + a₂y = 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 a₁p + a₂q is an integer that every integer point lies on a line of the form a₁p + a₂q = 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 a₁x + a₂y = 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 (a₁, a₂) = 1 then we know from the general solution of the binary linear diophantine equation (see previous post) that if x₁, y₁ is some integer point on a₁x + a₂y = b, then so is x₂ = x₁ + a₂t, y₂ = y₁ – a₁t, for any integer t. The distance between these points is = t√(a₁² + a₂²), so the distance between two adjacent integer points on the line is √(a₁² + a₂²), and if x₁ y₁ is some point on the line, then x₁ + a₂, y₁ – a₁ is the point immediately to its right.

Now consider the line a₁x + a₂y = a₁a₂ – a₁ – a₂. The points (-1, a₁-1) and (a₂ – 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 = a₁a₂ – a₁ – a₂, and the Frobenius number is greater than or equal to a₁a₂ – a₁ – a₂.

Now (0, a₁) and (a₂, 0) are adjacent integer points, and lie on the line a₁x + a₂y = a₁a₂. This line, and any line above and to the right of it has a segment of  length at least √(a₁² + a₂²) 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 a₁a₂.

Finally, consider lines for which a₁a₂ – a₁ – a₂ < b < a₁a₂. Each such line intersects the parallelogram defined by the points (0, a₁), (-1, a₁-1), (a₂ – 1, -1) and (a₂, 0).  It has a segment of length √(a₁² + a₂²) 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 a₁a₂ – a₁ – a₂ < b < a₁a₂ has a solution. Thus the Frobenius number is a₁a₂ – a₁ – a₂.

Binary Linear Diophantine Equations

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

where the a_k 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 n₁ > n₂ > 0 are integers we can construct integers a₁ and a₂ such that

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

(q₁ an integer) so

If the algorithm has k = 2 steps then

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

  and  where

  ;    ;    ;  and

  ;  for i ≥ 3

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

with c_i and d_i defined as in the proposition, and for 1 ≤ i ≤ k-1.

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

So P_i+1 is true. Consequently P_k-1 is true and n_k+1 = (n₁, n₂) can be expressed in the form proposed.

The construction can be easily extended to all (unequal) non-zero integers n₁ and n₂. We simply find integers a’₁ and a’₂ such that a’₁|n₁| + a’₂|n₂| = (n₁, n₂) then set a’₁=(n₁/|n₁|)a₁ and a’₂=(n₂/|n₂|)a₂.

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 a₁x₁ + a₂x₂ = a₀ (with a₁ and a₂ non-zero and unequal) has a solution only if (a₁, a₂) divides a₀.  If x’₁ and x’₂ are integers such that a₁x’₁ + a₂x’₂ = (a₁, a₂) then

  ;     is a solution.

Proof:  if there is a solution then since (a₁, a₂) divides a₁x₁ + a₂x₂ it must divide a₀. The rest is clear on substituting.

Knowing one solution, we can now identify all solutions:

If x₁⁰, x₂⁰ is a solution of a₁x₁ + a₂x₂ = a₀ (with a₁ and a₂ non-zero and unequal) then x₁, x₂ is a solution if and only if

  ;      where t is any integer

Proof:  the if part is easily seen by substitution.  For the converse, consider first the case a₀ = 0, noting that x₁ = 0, x₂ = 0 is a solution. Then

  where a₁ = a’₁(a₁, a₂) ; a₂ = a’₂(a₁, a₂)

Since (a’₁, a’₂) = 1 (if this were not so and there were a common divisor k > 1 then k(a₁, a₂) would divide a₁ and a₂, a contradiction) then a’₁ divides x₂ so

where t is some integer and

The general case follows easily from the special case on noting that if x₁⁰, x₂⁰ and x₁, x₂ are solutions then a₁(x₁⁰ -x₁) + a₂( x₂⁰ – x₂) = 0

Euclid’s Algorithm

Suppose that a and b are integers with b non-zero.  If there is an integer q such that a = qb, then we say that b divides a.

We can visualise the real numbers as lying in increasing order from left to right along a line.  If b is some non-zero integer, then the integers qb, where q runs through all the integers, divide the number line into segments of length |b| and all real numbers other than the qb lie inside one of these segments. Thus we can regard the following as self-evident:

Proposition (The Division Identity): If s is some real number and b is a non-zero integer, then either s = qb for some integer q (b divides s) or there is a unique integer q such that qb < s < qb + |b|.

Any integer that divides each of the integers m and n is called a common divisor or common factor of m and n. If m,n are not both zero we can assume that the set of all common divisors of m and n has a greatest member which is unique and call it the greatest common divisor of m and n and denote it as (m,n) or gcd(m,n). It is clear from the definition that: (m,n) = (|m|, |n|).

An algorithm for finding the gcd of two positive integers was given in Euclid’s Elements around 300 BC. Suppose the integers are n₁, n₂ with n₁ > n₂. It is easy to see as a consequence of the Division Identity that either n₁ = q₁n₂ and consequently n₂ = (n₁, n₂), or n₁ = q₁n₂ + n₃ with n₂ > n₃ > 0. We iterate this process to obtain a set of relations

n_i = q_in_i+1 + n_i+2 (1 < i< k)

n_k=q_kn_k+1

The process must terminate because the n_i form a descending, finite sequence of positive numbers and if it has not terminated beforehand, the condition n_i+2 = 1 forces it to terminate at the next step.

Now n_k+1 = (n_k, n_k+1) and if n_k+1 = (n_i, n_i+1) then n_k+1 = (n_i-1, n_i) (i > 1) because certainly n_k+1 divides both these latter numbers and if there were a larger number that divided both of them it would also be a common divisor of n_i and n_i+1, generating a contradiction.   Thus n_k+1 = (n₁, n₂).

We can obtain a measure of the efficiency of the Euclidean algorithm. Suppose there are k ≥ 3 steps, and that i < k. If n_i+1 ≤ n_i/2 then since n_i+2 < n_i+1 then n_i+2 ≤ n_i/2. If n_i+1 > n_i/2 then since 1 = n_i+2/n_i +q_in_i+1/n_i we must have q_i = 1 and n_i+2 ≤ n_i/2 also. Hence when 2j + 1 < k we have

Set 2j + 1 = k – s where s = 1 or 2 depending whether k is even or odd. Then

Forms of Proof

Ideally, mathematical proofs would start with statements that are known, or assumed to be, true and proceed through a series of steps to a final theorem. At each step a new statement would be shown to be true as a consequence of previous statements. However, in number theory in particular, it is often necessary to resort to less direct methods of proof.

Suppose P and Q are certain statements. If the truth of P implies that Q is true, we cannot assume the converse, that is, that Q implies that P is true. For example x = 1 implies that x² = 1, but if x² = 1, x is not necessarily 1. If the converse does happen to be true, we say that “P is true if and only if Q is true”, or that the statements P and Q are logically equivalent. For example, as can be easily shown, n is odd if and only if n² is odd for all integers n.

Although the statement “If P is true then Q is true” does not imply its converse, it does imply the contrapositive, namely “If Q is false then P is false”. For example if x² ≠ 1 then x ≠ 1. In number theory, propositions are often proved by proving the contrapositive.

If the truth of P implies Q is true, then the truth of Q is a necessary condition for P to be true, that is, P cannot be true unless Q is true, and it is not possible for P to be true if Q is false. If the truth of Q implies P is true, then Q is a sufficient condition for P to be true. That is, instances of Q being true can provide us with instances of P being true, but not necessarily all such instances. If Q is both necessary and sufficient then it is the logical equivalent of P. P is true on precisely those occasions when Q is true.

Reductio ad absurdum is a variant of the contrapositive. Suppose P is a proposition that it is desired to prove true. This method of proof starts with the proposition that P is false and shows that this leads to a conclusion that is either known to be false, or contradicts the proposition that P is false. This is considered to negate the proposition that P is false and hence prove that P is true.

As an example of its use (and also the use of the contrapositive), we prove that √2 is irrational. Start by assuming the contrary, that is, that √2 = p/q for some positive integers p, q . Because a number can be represented as a fraction in infinitely many ways, assume that it is possible to cancel out common multiples of 2 from p and q until at least one of p and q is odd (it is not necessary to assume that this process results in p and q being unique). p² = 2q² so p² is even. But if p is odd p² is odd so p must be even. Thus p² = 4k² for some positive integer k. Thus q² is even, so q is even, a contradiction. Therefore our starting proposition must be false.

Infinite descent is a specific form of reductio ad absurdum. It was used by Pierre de Fermat around 1640 to prove that there are no non-zero integer solutions to the equation x⁴ + y⁴ = z⁴ where z,y,z are positive integers, and has been widely used in other problems. It assumes the negative of the proposition, that is that there is a solution for some z, and shows that the existence of a solution for any value of z implies the existence of a solution for a smaller value of z, which is impossible because there is a least value of z (i.e. 1) beyond which no further solutions can exist.

Suppose that there is a (finite or infinite) sequence of propositions P₁, P₂, and so on. The Principle of Induction states that if P₁ is true and if we can demonstrate that if P_k were true for any given k then P_k+1 would be true, then all of P₁, P₂, … are true.

It is sometimes more practical to use the following corollary. If P₁ is true and if we can demonstrate that if for any given k, P_i were true for all 1 ≤ i ≤ k, then P_k+1 would be true, then all of P₁, P₂, … are true.

For let P’_k be the proposition that P_i is true for all 1 ≤ i ≤ k. If P₁ is true then P’₁ = P₁ is true. If the truth of P’_k implies the truth of P_k+1 then it implies the truth of P’_k+1. Therefore by induction all the P’ are true and so all the P are true.

Walter Ledermann – Encounters of a Mathematician

For about 20 years from the 1940s the Edinburgh publisher Oliver and Boyd published a series of very high standard pocket-sized texts in mathematics and mathematical physics entitled ‘University Mathematical Texts.’

Among my favourites, purchased as an undergraduate and still referred to forty years later, was ‘Finite Groups’ by Walter Ledermann.

For years Ledermann remained a name on a bookcover for me, until, through the magic of the internet, I chanced upon his reminisces, which begin here, full of warmth and humour.

Ledermann was a German Jew who was lucky enough to emigrate to Britain in the early 1930s, and to be able to follow his chosen career as a mathematician until he was well into his eighties.  The account of his PhD student from Afghanistan is particularly humorous and touching.

Zeta function for even positive integers

In 1735 Euler showed that

and later that

    when k > 0

By definition (see earlier post)

  at least when |x| < 2π

Also

Now (see pdf here for explanation)

When |y| < π we can write

Because the series is absolutely convergent we can change the order of summation

The result follows on putting y = x/2 and equating the coefficients of powers of x.

Generating function for the Bernoulli Polynomials

A generating function is a power series whose coefficients are a sequence of interest.   The Bernoulli Polynomials have the generating function

at least when |t| < 2π

The derivation of this result is shown here.

A generating function often enables properties of the sequence to be easily exposed.  Here the generating function enables us to show simply that the odd Bernoulli numbers B_2k+1 are zero (k > 0). This is necessarily the case if

is an even function of t. This is so since

Even and odd Bernoulli numbers

The first few Bernoulli numbers are B₀ = 1, B₁ = 1/2 and then 1/6, 0, -1/30, 0, 1/42, 0, -1/30, 0, 5/66, 0 -691/2730 and so on. This suggests that the odd-indexed Bernoulli numbers other than B₁ are zero. In the pdf here we show that this is so and also derive the following efficient formula for calculating B_2k

(k > 1)

where [k/2] is the largest integer less than or equal to k/2.

The method is taken from the chapter ‘Summation of Series’ of Barnard and Child (see Books page for a brief description of and link to this text).

Bernoulli numbers and sums of positive powers of integers

Let

and in general

We define the Bernoulli Numbers B_k as

;   (k > 0)

so B₁ = -1/2 ; B₂ = 1/6; B₃ = 0 and so on. We define the Bernoulli Polynomials B_k(x) as

Then

The derivation of this result is shown in the pdf here.

Prime powers in integers, least common multiples, factorials and binomial coefficients

The following theorems are usually considered so elementary by professional mathematicians that they are stated without proof.  For hobbyists like me, to whom they may not be so transparent, proofs are provided in the attached pdf.  In what follows (1) ind_pn represents the index of the prime p in the prime composition of n – for example ind₂ 24 = 3, ind₃ 24 = 1, ind₅ 24 = 0  (2) [n] is the largest integer less than or equal to n and (3) L_n is the least positive integer divisible by each of 1, 2, … , n.