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.

Let $\phi(n)$ be the Euler's phi function and $p>q,m>1$, $\phi(m^p)>\phi(m^q)$


My intuition tells me this is true but I am not sure how to prove it. I know little about Euler's phi function.

share|improve this question
3  
Hint: In general, $n$ and $m^k$ are relatively prime if and only if $n$ and $m$ are relatively prime. –  Thomas Andrews Dec 7 '11 at 21:45

3 Answers 3

up vote 2 down vote accepted

For $t \in \mathbb{P}$ and $n \in \mathbb{N}^+$, write $v_t(n)$ for the maximum $k \in \mathbb{N}$ such that $t^k \mid n$. Then $\phi(m^p)/\phi(m^q) = \prod_{t \in \mathbb{P}} t^{(p-q)\;\! v_t(m)} > 1$, since $p > q$ and $v_t(m) \ge 1$ for at least one $t \in \mathbb{P}$ (as far as $m \ge 2$).

share|improve this answer
    
Which can be conveniently shortened, under inspiration of André Nicolas' answer, recognizing that $\prod_{t \in \mathbb{P}} t^{(p-q)\;\! v_t(m)} = m^{p-q}$. –  Salvo Tringali Dec 7 '11 at 22:46

We can do a little better. Recall that $\varphi(n)$ counts the integers from $0$ to $n-1$ that are relatively prime to $n$. Note also that if $e$ is positive, then $x$ and $m$ are relatively prime iff $x$ and $m^e$ are relatively prime. This is because $x$ and $m$ are relatively prime iff they have no common prime factor. But that is the case iff $x$ and $m^e$ have no common prime factor.

Let $0 \le x < m$, where $m>1$. Then $x$ is relatively prime to $m$ iff $x+m$ is relatively prime to $m$ iff $x+2m$ is relatively prime to $m$, and so on. It follows that for any $a$, the number of integers in the chunk $[a,a+m-1]$ that are relatively prime to $m$ is the same as the number of integers in the chunk $[a+m,a+2m-1]$ that are relatively prime to $m$.

Divide the interval from $0$ to $m^p-1$ into $m^{p-1}$ equal-sized chunks. Each chunk has $\varphi(m)$ numbers relatively prime to $m$. So up to $m^p-1$ there are $\varphi(m)\,m^{p-1}$ numbers relatively prime to $m$. It follows that $$\varphi(m^p)=\varphi(m)\,m^{p-1}.$$ Similarly, $\varphi(m^q)=\varphi(m)\,m^{q-1}$. It follows that $$\frac{\varphi(m^q)}{\varphi(m^p)}=m^{q-p}.$$

share|improve this answer

It's immediate from $$\varphi(n) =n \prod_{p\mid n}\left(1- \frac{1}{p}\right)$$ because the powers of $m$ have the same set of prime divisors.

share|improve this answer
    
The formula $\varphi(m^k)=\varphi(m)m^{k-1}$ given by André Nicolas is perhaps a better expression of this idea. –  lhf Dec 7 '11 at 22:39

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.