4.30 The m integers x Image [A . . A + m) are different mod m; so their residues (x mod m1, . . . , x mod mr) run through all m1 . . . mr = m possible values, one of which must be equal to (a1 mod m1, . . . , ar mod mr) by the pigeonhole principle.

4.31 A number in radix b notation is divisible by d if and only if the sum of its digits is divisible by d, whenever b1 (mod d). This follows because (am . . . a0)b = ambm + · · · + a0b0am + · · · + a0.

4.32 The φ(m) numbers { kn mod m | km and 0 k < m } are the numbers { k | km and 0 k < m } in some order. Multiply them together and divide by 0k<m, km k.

4.33 Obviously h(1) = 1. If m

Get Concrete Mathematics: A Foundation for Computer Science, Second Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.