2
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ Hint: In general, $n$ and $m^k$ are relatively prime if and only if $n$ and $m$ are relatively prime. $\endgroup$ Commented Dec 7, 2011 at 21:45

3 Answers 3

6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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}$. $\endgroup$ Commented Dec 7, 2011 at 22:46
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The formula $\varphi(m^k)=\varphi(m)m^{k-1}$ given by André Nicolas is perhaps a better expression of this idea. $\endgroup$
    – lhf
    Commented Dec 7, 2011 at 22:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .