Ken Ward's Mathematics Pages

Number Theory Indeterminate Equations

Number Theory Contents

Page Contents

1. Rationale
2. Example 1
3. Example 2
4. Chinese Problem

Rationale

This page deals with solving certain problems, which have been popular world-wide for centuries. Normally, they are equations which have at least one more unknown than the number of equations, so they are, theoretically, indeterminate. These problems may have one solution, several solutions, an infinite number of solutions or no solutions at all. Most of these problems could be solved much more easily and economically using more theory than we use here. However, the problems on this page are solved using a very simple technique. Another page demonstrates how problems 1 and 2 would be solved using modular arithmetic.

Basically, an expression is obtained for the problem which contains only integers. The solutions of this kind of problem usually involve positive integers, so we can obtain expressions giving limits on the possible answers. So, in general, we reduce the equation or equations to integers and a fraction, replacing the fraction by another variable which is an integer. We continue in this manner until we have no fractions left in the equations.

We then substitute our last variable in the original equations and obtain expressions for the limits of the solutions, obtaining zero, one or many solutions.

Example 1 (Single solution)

We can write the following equation (multiplying the prices by 100):
[1.1]
Where x and y are non-negative integers which represent the number of doughnuts and the number of éclairs respectively.

From 1.1 we get an expression for x:
[1.2]

In the above, as x is an integer, then the second part must also be an integer.

Reducing the right-hand side to integers and fractions:
[1.3]

We find:
[1.4]

Where t is an integer, because 1.3 must be integral.

By rearranging 1.4, we obtain an expression for y in terms of t:
[1.5]

Because y is a positive integer (no negative numbers of cakes!), then 1.5 must be greater than or equal zero
[1.6]

Similarly, we substitute t in 1.3, to obtain an expression for x:
[1.7]

Simplifying gives:
[1.8]

Because x is a non-negative integer, then 1.8 must be greater than or equal to zero. For this to be so, we need:
[1.9]

Combining 1.6 and 1.9, we obtain:
[1.10]

Where the only value for t is 0 (because t is an integer).

Using t=0, we find from [1.8,] x=15, and from [1.5], y=29. Therefore, Jack bought 15 doughnuts at 0.95, and Jill bought 29 éclairs at 0.97. So, Jack must pay 14.25 and Jill, 28.13
■

Example 2

A restaurant claims to have provided 53 meals over a period. The management do not believe this is a correct figure. They assume that for each meal (which really reflects a bill) a new table cloth is provided. The management know that the laundry bill for table cloths and sundry items for the period is 705.08, and the cost of laundering a table cloth is 3.98, and each sundry item is charged 7.16. What is required is the number of table cloths laundered over the period.

Let x be the number of table cloths and y the number of sundry items. The equation is:
3.98x+7.16y=705.08

For our convenience, we multiply throughout by 100 to remove the decimals:

[2.1]

Arrange to find an expression for x, (x because it has the smaller coefficient):
[2.2]

Divide throughout to find the fraction:
[2.3]
Let integer t equal the fraction:
[2.4]
Dividing throughout by 2:
[2.5]

Multiplying throughout by 199:
[2.6]

Rearranging:
[2.7]

More rearranging to find y:
[2.8]
Let the fraction be equal to u, an integer:
[2.9]
Rearranging to find t:
[2.10]

Let v, an integer, equal the fraction:
  [2.11]
Rearranging to find u in terms of v:
[2.12]

We can now express t (from 2.10) in terms of integers, as v is an integer:
[2.13]

[2.14]

Using this value for t in Equation 2.8, to find y:
[2.15]
Simplifying:
[2.16]

Using the values for t (2.14) and y (2.16) in Equation 2.8:
[2.17]
Simplifying:
[2.18]

From 2.16, for y to be a positive integer:
[2.19]

And from 2.18, for x to be a positive integer:
[2.20]

The only value for v is 1. So, substituting in 2.18, we find x=98, and substituting in 2.16, we find y=44. That is the number of table cloths would be 98, and the sundry items, 44. The theory that approximately one table-cloth wash equals one bill appears disproved.
■

Chinese Problem

(The fact that the divisors aren't relatively prime does not matter, so long as the number of eggs exists, which it does. If the divisors were relatively prime, this would guarantee the number exists). These problems have an infinite number of solutions, so here we seek the minimum number that satisfies the conditions.

Setting up the equations

Let the number of eggs be X.
If she had 1 left over, when they were taken 2 at a time, then we can say, for nonnegative integer s:
2s+1=X [3.1]

Similarly, for 3 at a time with 2 left over and nonnegative integer t:
3t+2=X [3.2]

For the rest, with integers, with nonnegative integers u and v:
4u+3=X [3.3]

5v+4=X [3.4]

Solving the Equations

Equations 1 and 2

Successively, we equate the first equation with each of the others, so we build up a relationship in one equation that satisfies the conditions of the problem. Finally, we find the minimum value of X.
First equate the first two equations 3.1 and 3.2:
2s+1=3t+2

Giving:
s=t+(t+1)/2 [3.5]

Let a, an integer, be such that:
a=(t+1)/2

So (rearranging):
2a=t+1
t=2a-1 [3.6]

Substitituing this value for t in 3.5, to find s in terms of a:
s=2a-1+a
s=3a-1 [3.7]
As s is an integer, s>0, and therefore 3a-1>0, a>1/3, so the least value of a is 1. So, from 3.7, s=2, and 2s+1=5. The minimum number dividing by 2 and leaving 1 and dividing by 3 and leaving 2 is 5. (This is just a check!)

Equations 1 and 3

Equating equations 3.1 and 3.3, we have:
2s+1=4u+3
Simplified and as an expression for s:
s=(4u+2)/2
s=2u+1 [3.8]

At this point, we can note that the s value meets the conditions 1 and 3, but not the second condition. We need to incorporate our previous equation for s (Equation 3.7) so that all the conditions so far (1, 2, and 3) are satisfied.

Our previous equation for s in terms of t is 3.7, and equating this with 3.8 to produce an equation that meets all the conditions so far, we have:
2u+1=3a-1
Solving for u, as this has the lowest coefficient:
u=(3a-2)/2
u=a-1+a/2 [3.9]

b=a/2
Where b is a positive integer.
a=2b
Substituting in 3.9:
u=2b-1+b
u=3b-1 [3.10]

And substituting this in 3.8, to get a value for s:
s=2(3b-1)+1
s=6b-1 [3.11]

As u is a positive integer, u>0, 3b-1>0, so b>1/3, giving a minimum value for b=1.
Substituting b=1 in 3.10:
u=2.
Substituting this u value in 3.8:
s=5
And 2s+1=11
We note that, as a check, 11 leaves 1 when divided by 2, 2 when divided by 3 and 3 when divided by 4.

Equations 1 and 5

Equating equations 1 and 5:
2s+1=5v+4

s=(5v+3)/2
s=2v+1+(v+1)/2 [3.12]

c=(v+1)/2
Where c is a positive integer.
2c=v+1
v=2c-1 [3.13]

Substituting the value for v in terms of c in 3.12:
s=2(2c-1)+1+c
s=5c-1 [3.14]

This equation meets conditions 1 and 5, but not conditions 3 and 4. To incorporate the condtions 3 and 4 we need to incorporate our previous equation for s, which satisfies conditions 1, 2, 3 and 4, that is Equation 3.11, in our running formula.

We equate 3.15 with our previous value for s in 3.11:

5c-1=6b-1
c=6b/5=b+b/5 [3.15]

Let d=b/5, b=5d
So c=5d+d
c=6d
Substituting for c in 3.14
s=5·6d-1
s=30d-1
As s is an integer, s>0, and 30d-1>0, d>1/30. Taking d=1 as the minimum value:
s=29
2s+1=59
That is, our number is 59. We can check that this number leaves 1 on division by 2; 2 on division by 3; 3 on division by 4; and 4 on division by 5.

The minimum number of eggs the woman was taking to market was therefore 59.
■


















Ken Ward's Mathematics Pages

---

---

Faster Arithmetic - by Ken Ward