This example is the same one solved on a previous page.
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.
Rewriting Equation 1.1: 95x+97y=4238 (mod 97) We can cast out the 97's: 95x≡67 (mod 97)
[1.1a]
It is more straightforward to solve these equations using
Euclid's
Extended Algorithm. Using plain modular arithmetic sometimes works out
easily, as in this example, but it is often very difficult.
So a possible number of doughnuts is 15 (Or 15+97k, where
k=0...97...)
Substituting x≡15 in Equation 1.1, we
find y≡29, so the number of chocolate éclairs appears
to be 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.
So these are the respective numbers of cakes bought, because
the other possible numbers (For example 15+97) would not accord with the bill,
or with normal cake eating!
As the numbers are still quite large, we canuseEuclid's Algorithm to solve the problem. We write: 95x+97q=67, [1.2],
which is [1.1] rewriting y as q 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) By casting
out the 398's, we have: 318y≡62 (mod 398) [2.2]
Now, we have simplified the numbers. We procede using judgment to try and
make the equation solvable.
Adding 199 to the right hand side (to make it divisible by 5):
5y≡220 (mod 199)
Dividing by 5 which is relatively prime to 199
Hence, y≡44 (mod 199)
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.
Dividing throughtout by 2, because 2 is not relatively
prime to 398
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
one solution to 2.4=31•(-5)=-155≡44 (mod 199) 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.
[1.1]
[2.1]