6
$\begingroup$

Let $\varphi: \mathbb{N} \to \mathbb{N}$ be the totient function.

Is there an integer $N > 0$ such that there are infinitely many integers $n > 0$ such that $$\varphi(n) = N?$$

$\endgroup$
  • 1
    $\begingroup$ Pardon me? Is not the totient function invertible? $\endgroup$ – Megadeth Aug 28 '14 at 14:50
  • $\begingroup$ Hint: $n > \varphi(n) > \sqrt{\frac{n}{2}}$ so $n<N-1$ and $n>2N^2$ cannot be solutions to $\varphi(n) = N$ $\endgroup$ – Winther Aug 28 '14 at 15:03
  • $\begingroup$ @Winther: Useful, hitting the point. But where is the lower bound from? $\endgroup$ – Megadeth Aug 28 '14 at 15:06
  • $\begingroup$ Click on "Hint". It's a fairly simple proof, you can also find it in on the last page in this paper. btw much stronger bounds are found here and reads $\varphi(n) > \frac{n}{e^\gamma \log\log n + \frac{3}{\log\log n}}$ $\endgroup$ – Winther Aug 28 '14 at 15:08
  • $\begingroup$ Thanks! I have just found a stronger lower bound that $\varphi(n) \geq \sqrt{n}.$ Please see mathworld.wolfram.com/TotientFunction.html $\endgroup$ – Megadeth Aug 28 '14 at 15:21
8
$\begingroup$

No. Let $M\in\mathbb{Z}^{+}$ and let $p$ be the smallest prime such that $p> M+1$. Let $n\in\mathbb{Z}$ such that $\varphi(n)=M$. Now, suppose $q\ge p$ is a prime factor of $n$. Then, write $n=q^k\cdot m$, fro some $k\ge 1$ and $q\nmid m$. Then, we get $$\varphi(n)=\varphi(q^k\cdot m)=\varphi(q^k)\varphi(m)\ge q-1\ge p-1>M,$$ contradiction. Thus, no prime divisor of $n$ can be greater than $M+1$.

Thus, the prime divisors of $n$ make up a finite set, say $\{p_1,\ldots,p_m\}$. Now, write $n=p_1^{e_1}\cdots p_m^{e_m}$, for $e_i>0$. Then,

$$\varphi(n)=\varphi(p_1^{e_1})\cdots\varphi(p_m^{e_m})=\prod_{i=1}^{m}p_i^{e_i-1}(p_i-1).$$ Now, note that for each prime $p_i$, we have $\varphi(n)\ge p_i^{e_i-1}(p_i-1)>M$ for a sufficiently large choice of $e_i$. Thus, for each $p_i$ there are only finitely many valid choices for the $e_i$, and it follows that the set of all $n$ s.t. $\varphi(n)=M$ is finite.

$\endgroup$
  • $\begingroup$ Why you first assume $\varphi(n) = M$ and later have $\varphi(n) > M$? $\endgroup$ – Megadeth Aug 28 '14 at 14:54
  • $\begingroup$ @Brian That yields a contradiction allowing us to say that no prime dividing $n$ is greater than $M+1$. $\endgroup$ – tc1729 Aug 28 '14 at 15:02
  • $\begingroup$ Ah yes, I just saw the "for suff. large ...". $\endgroup$ – Megadeth Aug 28 '14 at 15:04
  • $\begingroup$ Where is the first contradiction? $\endgroup$ – Jossie Calderon Feb 21 at 5:22
6
$\begingroup$

No.

We use the fact that if $n = p_1^{e_1} \cdots p_k^{e_k}$, with the $p_i$ different primes and the $e_i$ positive, we have $\phi(n) = p_1^{e_1-1}(p_1-1) \cdots p_k^{e_k-1}(p_k-1)$.

Now consider an integer $N>0$ and suppose that $\phi(n) = N$. Then $n$ cannot be divisible by primes larger than $N+1$, since if $q > N+1$ divides $n$, we have $N+1 \leq q-1 \mid \phi(n) = N$, contradiction. The set of primes that may divide $n$, therefore, is finite. Let $p$ be such a prime. Then if $p^k \mid n$ we have $p^{k-1} \mid N$, which leaves a finite number of possibilities for $k$. Thus the number of primes that may divide $n$ is bounded and the exponent of each prime is bounded as well, thus there are at most finitely many $n$ for which $\phi(n) = N$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.