I want to show that for every $m \in \mathbb{N}$ only finitely many $n \in \mathbb{N}$ exist such that $\varphi(n) = \varphi(m)$. Here $\varphi$ defines the totient function. To achieve this I tried to find a lower bound of the totient function, but I am not too sure if what I did is indeed valid:
Let $k$ be an arbitrary (non prime) positive integer, we have that:
$$\forall p \in \mathbb{P} \quad \frac{k}{2}<p<k \Rightarrow gcd(p,k)=1$$
Let $U_k$ be the set of all prime numbers $p$ of this form: $\Rightarrow |U_k|\leq|\mathbb{Z}_k^*|$
Here the problem arises since the cardinality of $U$ depends on $k$ and we don't know much if anything at all about $|U|$ for values greater than $k$… Now, since $\mathbb{N},\mathbb{P}$ are unbounded, $|U|$ can get arbitrarily big. Hence I want to conclude something like: $$\forall \varphi(l) \in \mathbb{N}: \exists N \in \mathbb{N} \text{ such that }\varphi(n)>\varphi(l)\, \forall n \geq N$$
This however is only true if $|U_n|>\varphi(l)\, \forall n$
But it could be possible that $|U_n|\geq |U_{n+1}|$…so should I just discard my whole idea?
Best Answer
I thought I might be able to contribute a new idea to creating this lower bound: using the Prime Number Theorem. It states that $$\lim_{n\to\infty}\frac{\pi(n)}{\frac{n}{\log(n)}} = 1$$ where $\pi(n)$ is the number of primes between 1 and $n$. This implies, for example, that there is an integer $N_0$ such that for all $n>N_0$ we have $$\left| \frac{\pi(n)}{\frac{n}{\log(n)}}-1\right|<0.1 \iff \frac{0.9n}{\log(n)}<\pi(n)<\frac{1.1n}{\log(n)}$$ and for all $n>2N_0$ we can say the same thing where we replace $n$ by $n/2$. Thus for all $n>2N_0$, we have $$\pi(n)-\pi(n/2) > \frac{0.9n}{\log(n)}-\pi(n/2) > \frac{0.9n}{\log(n)}-\frac{0.55n}{\log(n/2)} = g(n)$$ which is also a strictly increasing function of $n$. As you pointed out, all these primes between $n/2$ and $n$ will be coprime to $n$ and so $\phi(n)\geq g(n)$.
So to be clear, we have shown a lower-bound on $\phi(n)$ for sufficiently large $n$. There are a few things to keep in mind about this result:
The Prime Number Theorem, at least in the form above, doesn't give any specification about how big $N_0$ will be for this $0.1$-bound, we simply know that that it exists. This is still enough to prove what you want though! We know that $\phi(n)$ takes on finitely many values below $N_0$ and then above it, we know a lower bound on $\phi(n)$ and so we know that $\phi(n)$ only takes on the value of each $k\in\mathbb{N}$ finitely many times.
$g(n)$ is really slow growing! However, this can't really be avoided - there just aren't that many primes between $n/2$ and $n$.
While the PNT isn't very elementary (as most standard proofs use complex analysis), using it pays off because this bound is actually fairly reflective of the number of primes between $n/2$ and $n$.