Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

2 Answers

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.