# Proving the set of prime numbers in $\mathbb{Z+}$ is infinite

I'm trying to prove that for any $N \in \mathbb{Z^+}$, there exists only finite many integers $n$ with $\varphi(n) = N$ (i.e. finite amount of numbers that have $N$ numbers relatively prime to them)

I started by addressing the lower bound of $\varphi(n)$ as the set of primes $P = \{0<p\leq n~|~\varphi(p) = p-1\}$ from $0$ to $n$ If I can prove that this lower bound increases as $n$ increases, then I can say that $N$ eventually is excluded from the bounds of the function and so the amount of $n$ has to be finite.

For any $k\in \mathbb{Z^+}$ there is a prime factorization $k = \prod p_i^{\alpha_i}$

For $|P|$ (the lower bound) to remain finite and less than $N$, $p_i$ must also be finite.

This leads to the reasoning that for all $k \in \mathbb{Z^+}$ there must exist a finite amount of distinct prime factors $p_i$. This is where I'm stuck.

How can I prove that there must be an infinite amount of primes to represent an infinite amount of integers?

• Well, using your notation, $\varphi(k)=\prod p_i^{a_i-1}\times \prod (p_i-1)$. Thus you need $p_i-1\leq N$, so only finitely many primes, and you need $p_i^{a_i-1} \leq N$ so only finitely many $a_i$. – lulu Apr 20 '16 at 16:18
• how did you get $\prod (p_i - 1)$? Isn't it just $\prod p_i$ because $p_i^{a_i -1} \times p_i = p_i^{a_i}$? – obliv Apr 20 '16 at 16:25
• No. $\varphi (p^a) = p^{a-1}(p-1)$ if $p$ is prime. – lulu Apr 20 '16 at 16:29

## 2 Answers

You're just trying to prove that there are infinitely many primes? I recommend this classic proof by contradiction, which is part of a proof attributed to Euclid:

Suppose there are finitely many primes, say $p_1, \dots, p_n$. Note that every one of these primes divides the product $p_1 \cdots p_n$. Consider the number $p_1 \cdots p_n + 1$. It can't be prime because it's larger than the largest prime. So it must be divisible by at least one prime, call it $p_k$. Then $p_k$ divides $p_1 \cdots p_n$ and $p_k$ divides $p_1 \cdots p_n + 1$, which means $p_k$ divides $(p_1 \cdots p_n + 1) - (p_1 \cdots p_n) = 1$, a contradiction.

• Euclid did not use contradiction – Henry Apr 20 '16 at 16:21
• @Henry, you should update the wiki page then. en.wikipedia.org/wiki/Euclid%27s_theorem#Euclid.27s_proof – tilper Apr 20 '16 at 16:22
• That page already says correctly "Euclid is often erroneously reported to have proved this result by contradiction, ..." – Henry Apr 20 '16 at 16:23
• Splendid. Then can you update my ability to read? – tilper Apr 20 '16 at 16:23
• For example, take a look at Chapter 2 in Number Theory: An Introduction via the Distribution of Primes by Benjamin Fine and Gerhard Rosenberger. – Robert Soupe Apr 21 '16 at 2:15

I don't have enough reputation to comment, but see this Wiki page. You're asking for a proof of Euclid's Theorem

https://en.wikipedia.org/wiki/Euclid%27s_theorem