HW #5 – due Thursday October 13

Chapter 5

2. Square root of 142884

This number is more than 100^2 and less than 1000^2 so its square root has 3 digits: 100a+10b+c.

To find a 300^2 = 90000, 400^2 = 160000. So a =3.

142884 – 90000 = 52884 which is >= 2*(100a)*10b = 6000b + 100b^2.

If b = 7, 6000b + 100b^2 = 46900. If b = 8, this last quantity = 54400, which is too large.

So b = 7. 52884 -46900 = 5984, which should = 200ac + 20bc + c^2 = 600c + 140c + c^2.

So 740c < 5984. The largest c that works = 8. 740*8 + 8^2 = 5920 + 64 = 5984.

So the answer is 378.

4. Channel 1 fills the reservoir 3 times in a day, channel 2 1 time, channel 3 2/5, channel 4 1/3 and channel 5 1/5. All together they fill 74/15 per day. So it will take them 15/74 of a day to fill it once.

13. Let x = the number of measures in a bundle of the best grain, y the ordinary and z the worst.

Then 2x + y = 1, 3y + z = 1; x + 4z = 1.

2 0 1

1 3 0

0 1 4

1 1 1

Subtracting 2* column 3 from column 1 gives

0 0 1

1 3 0

-8 1 4

-1 1 1

now subtract column 2 from 3 * column 1, giving

0 0 1

0 3 0

-24 1 4

- 4 1 1

z = 4/25, y = 7/25, x = 9/25.

20. M = 11*5*9*8*7 = 27720

N is a multiple of 11, 5, and 7. We only need to use the Euclidean algorithm for 9 and 8.

For 9, M/9 = 3080 = 342* 9 + 2; so 2 = 3080 – 342*9

9 = 4*2 + 1; so 1 = 9 – 4*2 = 9 – 4* (3080 – 342*9) = 1369*9 – 4*3080.

So 4*3080 = -1 mod 9. Then 5 * 3080 = 1 mod 9. So x = 5

For 8, M/8 = 3465 = 433*8 + 1. So x = 1.

Then M = 5*4*3080 + 6*3465 = 82390, which = 26950.

This number checks out for the proper congruences.

22. The gcd of 2 numbers can be expressed as a linear combination of them. If Pi and mi are relatively prime, the gcd is 1. The Euclidean algorithm provides the coefficients and Qin records those coefficients (or their absolute values) in his diagram.

Chapter 6

7. N = 808 mod 1096 and = 0 mod 3. So N = 1096x + 808 = 3y. 3y -808 = 1096x

= (365*3 + 1)x. So 3(y -365x) – 808 = 1x. x +808

Let t = y – 365x. Then 1*x + 808 = 3t. x = 2, t = 270. y = 365*2 + 270 = 1000.

So N = 1096*2 + 808 = 3000 .

8. N = 137x + 23 = 60y. Following the steps in the example on page 146, we get

60y – 23 = 137x = (2*60 + 17)x. So 60 (y-2x) -23 = 17x. 60t = 17x +23

(3*17 + 9)t= 17x + 23. 17(x-3t) = 9t – 23. 17u = 9t – 23. (1*9 + 8)u = 9t – 23.

(t-u)*9 -23 = 8u. 8u + 23 = 9v = (1*8 + 1)v.

8(u-v) + 23 = v, 8w + 23 = v. v – 23 = 8w. w = 1, v = 31.

Then u = 31 + 1 = 32; t = u + v = 63. x = 3t + u = 189 + 32 = 221; y = 2x + t = 2*221 + 63 = 505

N = 505*60 = 30300 = 137*221 +23.

30300 = 5640 mod 137*60.

12 . N + 10 mod 137 and N =0 mod 60.

137 = 2*60 + 17. 17 = 137 – 2*60.

60 = 3*17 + 9 9 = 60 –3*17 = 60 – 3*(137-2*60) = 7*60 - 3*137.

17 = 9 + 8 ; 8 = 17 -9 = 137 – 2*60 – (7*60 – 3*137) = 4*137 – 9*60.

9 = 8 + 1 ; 1 = 9 – 8 = 7*60 – 3*137 – (4*137 – 9*60) = 16*60 - 7*137.

So 16*60 + 1 mod 137. X = 16.

N = 10*16*60 = 9600 = 1380 mod (137*60).

Both methods use the Euclidean algorithm., and work it backwards to find the coefficients. The Chinese method works on several congruences at once while the Indian one does them two at at a time. The Indian method as presented is more algebraic.