4.30 The m integers x [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 b ≡ 1 (mod d). This follows because (am . . . a0)b = ambm + · · · + a0b0 ≡ am + · · · + a0.
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 the O’Reilly learning platform.
O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.