Concrete Mathematics: A Foundation for Computer Science, Second Edition

4.30 The m integers x [A . . A + m) are different mod m; so their residues (x mod m₁, . . . , x mod m_r) run through all m₁ . . . m_r = m possible values, one of which must be equal to (a₁ mod m₁, . . . , 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₀)_b = a_mb^m + · · · + a₀b⁰ ≡ a_m + · · · + a₀.

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