91Ó°ÊÓ

Without performing the divisions, determine whether the integers \(176,521,221\) and \(149,235,678\) are divisible by 9 or 11 .

Find all solutions of the linear congruence \(3 x-7 y=11(\bmod 13)\).

Establish the following divisibility criteria: (a) An integer is divisible by 2 if and only if its units digit is \(0,2,4,6\), or 8 . (b) An integer is divisible by 3 if and only if the sum of its digits is divisible by 3 . (c) An integer is divisible by 4 if and only if the number formed by its tens and units digits is divisible by \(4 .\) [Hint: \(10^{k} \equiv 0(\bmod 4)\) for \(\left.k \geq 2 .\right]\) (d) An integer is divisible by 5 if and only if its units digit is 0 or 5 .

(a) Obtain three consecutive integers, each having a square factor. [Hint: Find an integer \(a\) such that \(\left.2^{2}\left|a, 3^{2}\right| a+1,5^{2} \mid a+2 .\right]\) (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.

Prove that no integer whose digits add up to 15 can be a square or a cube. [Hint: For any \(a, a^{3} \equiv 0,1\), or 8 (mod 9).]

(Ancient Chinese Problem.) A band of 17 pirates stole a sack of gold coins. When they tried to divide the fortune into equal portions, 3 coins remained. In the ensuing brawl over who should get the extra coins, one pirate was killed. The wealth was redistributed, but this time an equal division left 10 coins. Again an argument developed in which another pirate was killed. But now the total fortune was evenly distributed among the survivors. What was the least number of coins that could have been stolen?

(a) Find an integer having the remainders \(1,2,5,5\) when divided by \(2,3,6,12\), respectively. (Yih-hing, died 717). (b) Find an integer having the remainders \(2,3,4,5\) when divided by \(3,4,5,6\), respectively. (Bhaskara, born 1114 ). (c) Find an integer having the remainders \(3,11,15\) when divided by \(10,13,17\), respectively. (Regiomontanus, \(1436-1476)\).

Use the theory of congruences to verify that $$ 89 \mid 2^{44}-1 \quad \text { and } \quad 97 \mid 2^{48}-1 $$

Obtain the two incongruent solutions modulo 210 of the system $$ \begin{aligned} &2 x \equiv 3(\bmod 5) \\ &4 x \equiv 2(\bmod 6) \\ &3 x=2(\bmod 7) \end{aligned} $$