# Application of PHP in Number theory

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.

• $(2)$ Yes, sure. Even on this site you can find this. As an example, see this post. Have a look for more examples. $(1)$ There is a proof via Euclid by considering $n!+1$, too. Here some steps still have to be justified. For example "Which isn't the case" - why? Jan 19 at 15:39
• – KCd
Jan 19 at 15:44

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.