Lecture Notes for College Discrete Mathematics

Section3.3Constructive proofs

In this section we deal with several problems for which a method can be provided to create a solution. We consider the coin problem (known also as the Frobenius problem). Let us be given a currency system with \(k\geq 2\) distinct integer denominations \(a_1\lt a_2\lt \ldots\lt a_k\text{.}\) Which amounts can be changed? This question yields the following linear Diophantine equation

where \(x_1,\ldots,x_k\) are non-negative integers. Now we study the case \(k=2\text{,}\) that is, our equation is

There are some natural questions to pose:

• Does the equation possess integer solutions?

• How many solutions does it have?

• How to determine all solutions?

In what follows we consider the above problem but we allow integer solutions instead of non-negative integer solutions. We will use these results to answer the original question.

Assume that \(\gcd(a_1,a_2)=d\text{.}\) Since \(d\) divides \(a_1x_1+a_2x_2\) we easily get that \(d\) divides \(n\text{,}\) if there is a solution in integers. For example, if we consider the equation

then 2 divides \(6x_1+8x_2\text{,}\) but 2 does not divide 5. Therefore there is no solution in integers.

Now suppose that \((u_1,u_2)\) is a solution, that is, \(a_1u_1+a_2u_2=n\text{.}\) Assume that there exists a different solution, say \((v_1,v_2)\text{.}\) We have that

It implies that

Let \(b_1=a_1/d\) and \(b_2=a_2/d\text{.}\) Since \(d\) is the largest common divisor of \(a_1\) and \(a_2\text{,}\) we obtain that \(\gcd(b_1,b_2)=1\text{.}\) We simplify the above equation by \(d\) to get

It is clear that \(b_1\) divides \(v_2-u_2\text{,}\) since \(\gcd(b_1,b_2)=1\text{.}\) So we have \(v_2-u_2=b_1t\) for some \(t\in\mathbb{Z}\text{.}\) Thus

and

It follows that there are infinitely many integer solutions. We have proved that there is no solution if \(\gcd(a_1,a_2)\) does not divide \(n\text{,}\) and if there is a solution, then there are infinitely many integer solutions. In Section 1.3 we showed that one can use the Euclidean algorithm to determine integers \(x,y\) for which \(a_1x+a_2y=\gcd(a_1,a_2)=d\text{.}\) Now assume that \(d\) divides \(n\text{,}\) that is, \(n=n_1d\) for some \(n_1\text{.}\) We obtain the following equation

Therefore \((xn_1,yn_1)\) is a solution of the equation \(a_1x_1+a_2x_2=n\text{.}\) Let us summarize what we obtained.

We apply the previous method to determine all integer solutions of the equation

First we find the greatest common divisor of 132 and 187. We use the Euclidean algorithm:

That is, \(\gcd(132,187)=11\text{.}\) Since 11 divides 55 we know that there are infinitely many integer solutions. The next step is to construct a solution to the equation \(132x+187y=11:\)

We obtained that \(x=-7, y=5\) is a solution to the equation \(132x+187y=11\text{.}\) Hence we have

It implies that \(x_1=-35,x_2=25\) is a solution to the equation \(132x_1+187x_2=55\text{.}\) Our theorem yields that

are solutions of the equation \(132x_1+187x_2=55\text{.}\)

We can handle equations of the form \(a_1x_1+a_2x_2=n\) in \(x_1,x_2\in\mathbb{Z}\text{.}\) If we have \(\gcd(a_1,a_2)=1\text{,}\) then we can solve the equation for any \(n\) in integers. What can we say about this equation if we allow only non-negative integers? Let us deal with the equation

From the Euclidean algorithm we get that

Thus we have that

is a solution to the equation \(7x_1+11x_2=n\text{.}\) From this particular solution we get infinitely many solutions:

We would like to have non-negative solutions, hence

So we have the following inequalities

If there is an integer contained in the interval \([\frac{-2n}{7},\frac{-3n}{11}]\text{,}\) then \(n\) can be represented in the form \(7x_1+11x_2\text{.}\) Denote by \(I_n\) the set \(\halmazvonal{t}{ \frac{-2n}{7}\leq t\leq \frac{-3n}{11}, t\in\mathbb{Z}}\text{.}\)

We can find 7 consecutive integers indicated in the table for which the set \(I_n\) is not empty, that is, those integers can be represented in the form \(7x_1+11x_2:\)

Given a solution for \(n=60\) we can easily find a solution for \(n=67\) and \(n=74\) etc. We use this idea to provide solutions for all \(n>59\text{.}\) The Division algorithm says that if we divide an integer by 7, then the remainder is between 0 and 6.

If the remainder is 0, then from the equation \(63=7\cdot 9+11\cdot 0\) we get

That is, if we have an integer \(n\geq 63\) divisible by 7, then it can be written in the form \(7x_1+11x_2\) with \(x_1,x_2\geq 0\text{.}\)

If the remainder is 1, then we use the equation \(64=7\cdot 6+11\cdot 2\) to obtain

In a similar way one computes the general solutions for the remaining cases.

How to deal with equations with more than two variables? We show how to reduce equations in three unknowns to equations in two unknowns. So the techniques applied previously can be used here. Consider the equation

Introduce a new variable \(y_1=4x_1+5x_2\text{,}\) then the equation can be written as

A particular solution is \((n,0)\text{,}\) hence all the integer solutions can be parametrized as follows

for some \(t\in\mathbb{Z}\text{.}\) It remains to determine the integer solutions of the equation \(y_1=4x_1+5x_2=n+7t\text{.}\) The first thing to do is to find a particular solution. It is easy to check that

is a solution. Applying the techniques used in case of two variables we get the following parametrization of integral solution

for some \(s,t\in\mathbb{Z}\text{.}\) As a concrete example consider the equation \(4x_1+5x_2+7x_3=23\text{.}\) Then we obtain integer solutions by substituting concrete integral values into the above formulas. Some solutions are indicated in the following table

What about non-negative integer solutions? That is, if one asks for solutions such that \(x_1,x_2,x_3\in\mathbb{N}\cup\halmaz{0}\text{.}\) In case of the equation \(4x_1+5x_2+7x_3=n\) we determined the parametrization of the integral solutions, so we get the following inequalities

That is, we immediately see that \(t\leq 0\text{.}\) We try to eliminate \(s\) from the first and the second equations. So we multiply by 4 the first equation and by 5 the second one and we get

That is, we obtain that

It remains to determine a lower bound and an upper bound for \(s\text{.}\) We have

hence \(s\geq -\frac{2n}{7}\text{.}\) Similarly, we have

therefore \(s\leq -\frac{n}{5}\text{.}\) Let us denote the two intervals as \(I_s=[-\frac{2n}{7},-\frac{n}{5}]\) and \(I_t=[-\frac{n}{7},0]\text{.}\) To have a non-negative integer solution we need an integer contained in the interval \(I_s\) and another one contained in \(I_t\text{.}\) If the length of the interval \(I_s\) is at least 1 and similarly for \(I_t\text{,}\) then for sure there will be such integers. The length of \(I_s\) is \(-\frac{n}{5}+\frac{2n}{7}=\frac{3n}{35}\) and the length of \(I_t\) is \(\frac{n}{7}\text{.}\) We have that the length of \(I_s\) is at least 1 if \(n\geq 12\) and the length of \(I_t\) is at least 1 if \(n\geq 7\text{.}\) If \(n\geq 12\text{,}\) then an integer solution is guaranteed. It means that if \(n\geq 12\text{,}\) then the equation \(4x_1+5x_2+7x_3=n\) has non-negative integer solution. Now we deal with the remaining cases \(1\leq n\leq 11\text{.}\)

We proved that if \(n>6\text{,}\) then the equation \(4x_1+5x_2+7x_3=n\) has non-negative integer solution.