Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question
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
up vote 4 down vote accepted

$\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$.

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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