If there are more pigeons than pigeonholes and every pigeon goes into a pigeonhole, then some pigeon hole must have more than one pigeon in it. This is called the *Pigeonhole Principle*. We now wan to describe it mathematically. To do so, we need to define some notions such as sets and functions. A *set* is an unordered collection of objects without duplicates. Given a set $A$ we write that an object $a$ is an element of $A$ (or $a$ belongs to $A$) as $a\in A$, and that $a$ is not an element of $A$ as $a\notin A$. A *function* from one set to another is a rule that associates each member of the first set with exactly one member of the second set. If $f$ is a function from a set $X$ to another set $Y$ (denoted by $f:X\longrightarrow Y$) and $x\in X$, then $f(x)$ is the member of $Y$ that $f$ associates with $x$. We refer to $x$ as the *argument* of $f$ and $f(x)$ as the *value of $f$* *on that argument*.

*Example*. Let $P=\{\mbox{Annie, Ben, Charlie, David, Evely, Franz, Greg, Marie}\}$ and $D=\{\mbox{Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}\}$. $b:P\longrightarrow D$ is the function that associates each of the eight people with the day of the week on which he or she was born. If Marie was born on Wednesday, then $b(\mbox{Marie})=\mbox{Wednesday}$.

A function $f: X\longrightarrow Y$ is also called a *mapping* or a *map* from $X$ to $Y$, and $f$ is said to map an element $x\in X$ to the element $f(x)\in Y$.

Now we are ready to describe the Pigeonhole Principle mathematically. Let $f: X\longrightarrow Y$ be a function from (a finite set) $X$ to (a finite set) $Y$. If $|X|>|Y|$ ($|X|$ is the number of elements of $X$), then there are elements $x_1,x_2\in X$ such that $x_1\ne x_2$ and $f(x_2)=f(x_2)$.

More generally we have the following *Extended Pigeonhole Principle*.

*Theorem*. For any finite sets $X$ and $Y$ and any positive integer $k$ such that $|X|>k|Y|$, if $f: X\longrightarrow Y$, then there are at least $k+1$ distinct members $x_1,\cdots,x_{k+1}\in X$ such that $f(x_1)=f(x_2)=\cdots=f(x_{k+1})$.

An integer $p$ divides another integer $q$, we write it as $p|q$, if $q=pk$ for some integer $k$. ($3|6$ because $6=2\cdot 3$.) We write $p\not|q$ if $p$ does note divide $q$. For example, $3\not|7$. If $x$ is a real number, we write $\lfloor x\rfloor$ for the greatest integer less than or equal to $x$. $\lfloor x\rfloor$ is called the *floor* of $x$. For example, $\left\lfloor\frac{17}{3}\right\rfloor=5$. $\lceil x\rceil$ is the smallest integer greater than or equal to $x$. $\lceil x\rceil$ is called the *ceiling* of $x$. $\lceil 3.7\rceil=4$.

*Theorem*. (Extended Pigeonhole Principle, Alternate version) Let $X$ and $Y$ be finite sets and let $f: X\longrightarrow Y$. Then there exists $y\in Y$ such that $f(x)=y$ for at least $\left\lceil\frac{|X|}{|Y|}\right\rceil$ values of $x$.

*Proof*. Let $m=|X|$ and $n=|Y|$. If $n|m$ then this is the Extended Pigeonhole Principle with $k=\frac{m}{n}-1=\left\lceil\frac{m}{n}\right\rceil-1$. If $n\not|m$, then again this is the Extended Pigeonhole Principle with $k=\left\lceil\frac{m}{n}\right\rceil-1$ since that is the largest integer less than $\frac{|X|}{|Y|}$.

If $p|q$ then $p$ is said to be a *factor* or a *divisor* of $q$. A prime number is an integer greater than 1 that is divisible only by itself and 1. For example, 7 is prime but 6 is not because $6=2\cdot 3$.

*Theorem*. (The Fundamental Theorem of Arithmetic) There is one and only one way to express a positive integer as a product of distinct prime numbers in increasing order and with positive integer exponents.

The *prime decomposition* (or *prime factorization*) of $n$ is $$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$$ where $p_1<p_2<\cdots<p_k$, all the $p_i$ are prime and the $e_i$ are positive integer exponents.

*Example*. $180=2^2\cdot 3^2\cdot 5^1$.

*Theorem*. If $m,n$ are integers greater than 1 that are relatively prime (we write $(m,n)=1$), $p$ is prime and $p|m\cdot n$, then either $p|m$ or $p|n$.

*Proof*. By Fundamental Theorem of Arithmetic there is one and only one way to write $m\cdot n$ as $$m\cdot n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$$ where the $p_i$ are prime. Since $p|m\cdot n$, $p$ must be one of the $p_i$, and each $p_i$ must appear in the unique prime decomposition of either $m$ or $n$. This completes the proof.

*Remark*. The condition $(m,n)=1$ is crucial for the above theorem to hold. Without it the statement is not necessarily true. For example, let $m=6$ and $n=9$. Then $(m,n)=3\ne 1$. 3 is prime and $3|m\cdot n=2^1\cdot 3^3$ but $3|m$ and $3|n$.

*Theorem*. There are arbitrary large prime numbers.

*Proof*. Pick some value of $k$ for which we know there are at least $k$ primes. (Since $p_1=2$, $p_2=3$, $p_3=5$, we could for example take $k=3$.) Let $P_1,\cdots,p_k$ be the first $k$ primes in increasing order. We now show how to find a prime number greater than $p_k$. This proces can be repeated indefinitely so there must be infinitely many primes. Let $N=p_1p_2\cdots p_k+1$. Then $N$ has no prime divisor less than or equal to $p_k$. Then either $N$ is not prime but has a prime factor greater than $p_k$ or $N$ is prime itself. This completes the proof.

*Example*. In $k=3$ case, $N=2\cdot 3\cdot 5+1=31$ itself is prime.

*Example*. Choose $m$ distinct numbers between $2$ and $40$ inclusive where $m\geq 13$. Then at least two of the numbers have some common divisor greater than 1.

*Solution*. There are 12 prime numbers between 2 and 40 inclusive. They are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Let $P$ be the set of these 12 prime numbers. Consider a set $X$ of 13 distinct numbers between 2 and 40 inclusive. Define $f: X\longrightarrow P$ by $f(x)=\mbox{the smallest prime that divides}\ x$. For example, $f(16)=2$, $f(17)=17$, $f(21)=3$. By the Pigeonhole Principle, since $31>12$, for at least two distinct members of $X$, the values of $f$ must be equal. Therefore, at least two members of $x$ have a common (prime) divisor (so obviously is greater than 1).

*References*.

[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019