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