91Ó°ÊÓ

Solve the following linear congruences: (a) \(25 x=15(\) mod 29\()\). (b) \(5 x=2(\bmod 26)\) (c) \(6 x=15(\bmod 21)\). (d) \(36 x=8(\bmod 102)\). (c) \(34 x \equiv 60(\) mod 98 ). (f) \(140 x \equiv 133\) (mod 301). \([\) Hint: \(\operatorname{gcd}(140,301)=7.1\)

Use the binary exponentiation algorithm to compute both \(19^{53}(\bmod 503)\) and \(141^{47}\) \((\bmod 1537)\)

(a) Find the remainders when \(2^{50}\) and \(41^{65}\) are divided by 7 . (b) What is the remainder when the following sum is divided by 4 ? $$ 1^{5}+2^{5}+3^{5}+\cdots+99^{5}+100^{5} $$

Solve the linear congruence \(17 x \equiv 3\) (mod \(2 \cdot 3 \cdot 5 \cdot 7)\) by solving the system $$ \begin{array}{ll} 17 x \equiv 3(\bmod 2) & 17 x \equiv 3(\bmod 3) \\ 17 x=3(\bmod 5) & 17 x=3(\bmod 7) \end{array} $$

(a) Obtain three consecutive integers, cach having a square factor. [Hint: Find an integer \(a\) such that \(2^{2}\left|a, 3^{2}\right| a+1,5^{2} \mid a+2\).] (b) Obtain three consecutive integers, the first of which is divisible by a square, the second by a cube, and the third by a fourth power.

(Brahmagupta, 7 th century A.D.) When eggs in a basket are removed \(2,3,4,5,6\) at a time there remain, respectively, \(1,2,3,4,5\) eggs. When they are taken out 7 at a time, none are left over. Find the smallest number of eggs that could have been contained in the basket.

The basket-of-eggs problem is often phrased in the following form: One egg remains when the eggs are removed from the basket \(2,3,4,5\), or 6 at a time; but, no eggs remain if they are removed 7 at a time. Find the smallest number of eggs that could have been in the basket.

Verify that \(0,1,2,2^{2}, 2^{3} \ldots . .2^{9}\) form a complete set of residues modulo 11 , but that \(0.1^{2} .2^{2} .3^{2} \ldots \ldots 10^{2}\) do not.

Assuming that 495 divides \(273 \times 49 y 5\), obtain the digits \(x\) and \(y\).

The International Standard Book Number (ISBN) used in many libraries consists of nine digits \(a_{1} a_{2} \ldots a_{9}\) followed by a tenth check digit \(a_{10}\), which satisfies $$ a_{10}=\sum_{k=1}^{9} k a_{k}(\bmod 11) $$ Determine whether each of the ISBNs below is correct: (a) \(0-07-232569-0\) (United States). (b) \(91-7643-497-5\) (Sweden). (c) 1-56947-303-10 (England).