# How can “ $\small {n \over \varphi(n) } \text{ is integer only if } n=2^r \cdot 3^s$ ” simply be shown?

I've tried to answer the question concerning $\small { 3^n-2^n\over n }$ and wanted to show this simply by referring to the property that $$3^{\varphi (n)}-2^{\varphi (n)}\equiv 0 \pmod n$$ and $$3^{\varphi (n) \cdot m}-2^{\varphi (n) \cdot m}\equiv 0 \pmod n$$ and thus that it is required that $$n = \varphi(n) \cdot m$$ and then $${n \over \varphi(n)}=m$$ is integer. After a short consideration I got aware that I could not really prove easily, that this is in general impossible. The wikipedia-page does not have a short statement about this and a short heuristic indicates, that this is possible only for $n=2^r 3^s \gt 1$ where then $m \in \{ 2 , 3\}$.

Q: What is a short and simple way to prove this?

(Remark: in the referred question there is an answer like "apply Fermat's little theorem repeatedly" - here I'd like an answer which is less abstract)

-
As a general rule, when asking a question, ask a question without lots of motivating stuff. If you want help with the other problem, that's a separate question. The question in the subject is clear, the question in the body of your message is muddled. – Thomas Andrews Jul 2 '12 at 13:25

$\frac{n}{\phi(n)}$ is multiplicative, so if $n=\prod p_i^{a_i}$ is the prime factorization of $n$, then $$\frac{n}{\phi(n)} = \prod \frac{p_i^{a_i}}{p_i^{a_i-1}(p_i-1)} = \prod \frac{p_i}{p_i-1}$$ If $n$ is divisible by two odd primes then the denominator is divisible by $4$ but the numerator cannot be so the result is not an integer. If $n$ is divisible by one odd prime $p$ then the denominator is divisible by $2$ and we must have $n=2^rp^s$ and $n/\phi(n) = 2p/(p-1)$. If $p=3$ this is an integer, otherwise $1<p/(p-1)<3/2$ and it cannot be. If $n$ is not divisible by an odd prime then $n=2^r$.

-
Hmm, both answers (André's included) are quite easily to grasp. I'll "accept" this one because it slips very well into my intuition... – Gottfried Helms Jul 2 '12 at 17:26

It comes down to counting $2$'s. It turns out that usually $\phi(n)$ has more $2$'s in its prime factorization than $n$ does.

Let $2^e$ be the highest power of $2$ that divides $n$. We have $\frac{2^e}{\varphi(2^e)}=2$. Every distinct odd prime factor $p$ of $n$ contributes at least one $2$ to the prime power factorization of $\varphi(n)$. So if $\varphi(n)$ divides $n$, there cannot be two distinct odd primes that divide $n$.

Thus our only candidates have shape $n=2^e p^k$, where $p$ is an odd prime and $k \ge 0$.

If $p-1$ is not a power of $2$, then $p-1$ cannot divide $2^ep^k$. So $p-1$ is a power of $2$. If $p-1$ is a power of $2$ greater than $2$, then the power of $2$ in $\varphi(n)$ is greater than the power of $2$ in $n$. So $p-1=2$.

-