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. Number Theory

Integers are central to the discrete mathematics we are emphasizing in this book. Therefore we want to explore the theory of numbers, an important branch of mathematics concerned with the properties of integers.

We tested the number theory waters in the previous chapter, by introducing binary operations called ‘mod’ and ‘gcd’. Now let’s plunge in and really immerse ourselves in the subject.

In other words, be prepared to drown.

4.1 Divisibility

We say that m divides n (or n is divisible by m) if m > 0 and the ratio n/m is an integer. This property underlies all of number theory, so it’s convenient to have a special notation for it. We therefore write

(The notation ‘m|n’ is actually much more common than ‘m\n’ in current mathematics ...

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