O'Reilly logo

Concrete Mathematics: A Foundation for Computer Science, Second Edition by Oren Patashnik, Donald E. Knuth, Ronald L. Graham

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required