**4.30** The m integers x [A . . A + m) are different mod m; so their residues (x mod m_{1}, . . . , x mod m_{r}) run through all m_{1} . . . m_{r} = m possible values, one of which must be equal to (a_{1} mod m_{1}, . . . , a_{r} mod m_{r}) 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 b ≡ 1 (mod d). This follows because (a_{m} . . . a_{0})_{b} = a_{m}b^{m} + · · · + a_{0}b^{0} ≡ a_{m} + · · · + a_{0}.

**4.32** The φ(m) numbers { kn mod m | k ⊥ m and 0 ≤ k < m } are the numbers { k | k ⊥ m and 0 ≤ k < m } in some order. Multiply them together and divide by ∏_{0≤k<m, k⊥m} 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.