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

392 Views Asked by At

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?

2

There are 2 best solutions below

7
On BEST ANSWER

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.

0
On

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