  # Ken Ward's Mathematics Pages

## Number Theory Indeterminate Equations

Number Theory Contents

### 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)

Jack and Jill visit the cake shop every day, and Jack always buys jam doughnuts, and Jill chocolate éclairs. The jam doughnuts cost 0.95 each and the chocolate éclairs cost 0.97. At the end of the  week the non-itemised bill from the cake shop is 42.38. How much must each pay?

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

A horseman accidentally knocked a woman carrying a basket of eggs that she was taking to the market to sell, smashing them all. She screeched at him, saying she was a witch and would curse him. Frightened, the horseman offered to pay for the eggs at double the market price. The angry witch said he could pay for them, and she wouldn't curse him, if he could solve a puzzle, and tell her how many eggs she had. He could them pay her £1.50 an egg.
She said that:

When she took the eggs out 2 at a time, she ended up with one left over.
When she took them out three at a time, she had 2 left over.
When she took them out 4 at a time, she had 3 left over.
And when she took them out 5 at a time, she had 4 left over.
How many eggs did she have?

(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

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle: 