Chapter 8 Number Theory298
(a)Explain why (8.40) does not follow immediately from Euler’s Theorem.(b)Prove that
d^13 d .mod10/ (8.41)for 0 d < 10.
(c)Now prove the congruence (8.40).Problem 8.38. (a)Ten pirates find a chest filled with gold and silver coins. There
are twice as many silver coins in the chest as there are gold. They divide the gold
coins in such a way that the difference in the number of coins given to any two
pirates is not divisible by 10. They will only take the silver coins if it is possible
to divide them the same way. Is this possible, or will they have to leave the silver
behind? Prove your answer.
(b)There are also 3 sacks in the chest, containing 5, 49, and 51 rubies respec-
tively. The treasurer of the pirate ship is bored and decides to play a game with the
following rules:
He can merge any two piles together into one pile, and
he can divide a pile with an even number of rubies into two piles of equal size.He makes one move every day, and he will finish the game when he has divided the
rubies into 105 piles of one. Is it possible for him to finish the game?
Exam Problems
Problem 8.39.
The sum of the digits of the base 10 representation of an integer is congruent mod-
ulo 9 to that integer. For example,
763 7 C 6 C3 .mod9/:This is not always true for the base 11 representation, however. For example,
.763/ 11 D 7 112 C 6 11 C 3 3 6 5 7 C 6 C3 .mod11/:For exactly what integersk 2 .1;10çis it true that the sum of the digits of the
base 11 representation of every nonnegative integer is congruent modulokto that
integer?