Modular Arithmetic/The Pigeonhole Principle

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Previously we learned some basic properties of the congruence relation (≡), and how to perform basic arithmetic with congruences (addition, subtraction, multiplication and division, under specific conditions).

In this chapter, we will learn one of the most important theorems in math, the Pigeonhole Principle. This seemingly simple theorem is surprisingly very powerful, as it can prove shocking facts, such as the fact that there are at least two people in London with the same number of hairs on their head - what??!! And even the fact that if you add a new baby to 365 babies, who were all born on different days of the year, there is a baby in the group that was born in the same day of the year as the new baby (well, this one is more obvious and less surprising).

We will learn how to use the powerful Pigeonhole Principle in modular arithmetic.