Ken Ward's Mathematics Pages

Number Theory Using Modular Arithmetic to Solve Indeterminate Equations

On this page, we look at the problems we solved using simple techniques, to compare the previous techniques with the use of modular arithmetic.

Number Theory Contents

See also page:

• Indeterminate Equations

Page Contents

1. Example 1
2. Example 2

Example 1 (Single solution)

This example is the same one solved on a previous page.
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.

Rewriting Equation 1.1:
95x+97y=4238 (mod 97)
We can cast out the 97's:
95x≡67 (mod 97)

As the numbers are still quite large, we need to try Euclid's Algorithm to solve the problem. We write:
95x+97q=67,  [1.2]
as the equation we wish to solve, and
95x+97q=1, [1.3]
as the one we will solve first.

Solve 95x+97q=1
k	qk	xk	r	qk
1	1	0	97
2	0	1	95	1
3	1	-1	2	47
	-47	48	1

The solution to 1.3, is x=48.

The solution to 1.2 is
x=48•67=3216≡15 (mod 97)

Therefore the number of doughnuts is 15. Substituting x=15 in Equation 1.1, we find y=29, so the number of chocolate éclairs is 29.
Jack must therefore pay 15•0.95=14.25,
And Jill must pay 29•0.97=28.13.
The total to pay is 42.38, which accords with the total bill.
■

Example 2

This example comes from this page.
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]

As in Example 1, we can take 2.1 mod 398:
716y≡70508 (mod 398)
318y≡62 (mod 398) [2.2]
The gcd(318,398)=2, which divides 62, so the equation has 2 solutions. Dividing by 2
159y≡31 (mod 199) [2.3]

The numbers are smaller, but still we need to use Euclid:
The equation we wish to solve is:
159y+199q=31, [2.4]
But first we will solve
159y+199q=1,  [2.5]

159y+199q=1
k	qk	yk	r	qk
1	1	0	199
2	0	1	159	1
3	1	-1	40	3
4	-3	4	39	1
5	4	-5	1

The solution to 2.5 is y=-5, and the solution to 2.4=31•(-5)=-155≡44 (mod 199)
There are 2 solutions because gcd(716,398)=2, one is y=44, and the other is y=234, but only y=44 fits the problem.
Substituting y=44 in 2.1, and solving for x, we find x=98. That is, 98 table cloths were washed and 44 sundry items. The theory that approximately one table-cloth wash equals one bill appears disproved.






Number Theory Contents

Ken Ward's Mathematics Pages

---

---

Faster Arithmetic - by Ken Ward