Application of PHP in Number theory

Question

Context : Me and my friend are taking a basic number theory course for undergrads. I was thinking of Euclid's proof of infinitude of primes and my friend thought of a way to prove it using Pigeon Hole Principle.

Thm : There are infinitely many primes in $\mathbb{N}$.

Proof : Suppose there are finite number of primes and let this number be $m$. Let p be the largest prime. Create m holes and we have p pigeons (i.e primes). Now the natural number $p!+1$ should belong to one of the $m$ holes which isn't the case. So there exists a $(m+1)th$ hole for $p!+1$. This means there are infinitely many primes in $\mathbb{N}$.

I tried to explain to him that this is both redundant and overkill. I wish to know

(1) if my friend is right here

(2) is there any elementary theorems in Number theory in which PHP is used.

Answer 1

Your friend's proof is essentially the same as Euclid's, but it is convoluted and does not really use the pigeonhole principle. The $m$ holes presumably correspond to the $m$ primes, with a number in a hole when it's divisible by the corresponding prime. The numbers are the pigeons, but the analogy breaks down because a number can be in more than one hole.

Then he's looking at $p! +1$ where Euclid looks at $1$ plus the product of all the $m$ primes. In either case you've found a number not in any of the $m$ holes. That's the opposite of what the pigeonhole principle asserts when used properly: it says that some hole contains more than one pigeon.

For (2) there are many elementary number theory arguments that do use the pigeonhole principle. You will probably encounter some in your course.