For what integers $n$ does $\varphi(n)=n-5$?

Question

What I have tried so far: $n$ certainly can't be prime. It also can't be a power of prime as $\varphi(p^k)=p^k-p^{k-1})$ unless it is $25=5^2$. From here on, I am pretty stuck. I tried considering the prime factorization of $n$, or perhaps looking for some contradiction, which would show $n$ must be a power of a single prime, but cannot make progress: Let $n=p_1^{e_1}...p_k^{e_k}$. Then $$n(1-\frac 1{p_1})...(1-\frac 1{p_k})=p_1^{e_1}...p_k^{e_k}-5.$$ Do I need to consider modulo 5? I also thought about considering whether or not $5\mid n$ or whether $n$ is even/odd, but cannot seem to make progress.

---

I found this similar question asked on StackExchange a while ago, but since the RHS is $n-2$, they could consider restrictions with parity. I also don't get why they could assume that $n=pq$ is a product of exactly 2 distinct primes only for the contradiction.

Answer 1

Hint: Let $p$ be a prime dividing $n = \displaystyle\prod_{j}p_j^{e_j}$. Then, $$n-5 = \phi(n) = n\prod_{j}(1-\tfrac{1}{p_j}) \le n(1-\tfrac{1}{p}),$$ and thus, $1-\tfrac{5}{n} \le 1-\tfrac{1}{p}$, i.e., $\tfrac{n}{p} \le 5$.

Since $\tfrac{n}{p}$ must be an integer, we have $\tfrac{n}{p} \in \{1,2,3,4,5\}$. Hence, $n$ must be in the form $n = p, 2p, 3p, 4p, 5p$ for some prime $p$.

Can you try out each of these cases?

Answer 2

I think you've got the only solution. As you said, $n$ can't be prime and as pointed out in a comment, if $n>2$, the totient of $n$ is even. So $n$ must be odd and composite. If we assume that $n$ is the product of 2 distinct odd primes, we have $$n-\phi(n)=p_1p_2-(p_1-1)(p_2-1)=p_1+p_2-1=5$$

But the smallest odd primes we can pick are 3 and 5. And adding more distinct primes to the mix is going to make the minimum value of $n-\phi(n)$ much larger. So $n$ can't be the product of distinct primes.

Finally, if $n$ is a multiple of $p^2$ for some prime $p$, then the totient will be a multiple of $p$. If $p|n$ and $p|\phi(n)$, then $p|[n-\phi(n)]$, so $p|5$. There might be a few gaps, but it's pretty clear the only solution is $5^2=25$.

Answer 3

If $n\ge 6$ (to make $n-5$ positive) is prime then $\phi(n)=n-1\not=n-5$. Otherwise $n$ has to have a prime factor $q\le\sqrt{n}$ forciing

$\phi(n)\le n\left(1-\dfrac1{q}\right)\le n-\sqrt{n}.$

So

$\phi(n)=n-5\implies n\not\in\mathbb{P}\text{ and }6\le n\le25.$

Also $\phi(n)$ is even for $n\ge 3$ so

$\phi(n)=n-5\implies n\in2\mathbb{N}+1.$

So $n$ must be odd, composite, at least $6$ and at most $25$. Only $9,15,21,25$ survive as candidates and among these, only $25$ checks affirmatively.