Euler Totient Function - show that if $q$ is prime and divides $m$, then $\phi(qm) = q\phi(m)$,

Question

Show that if $q$ is prime and divides $m$, then $\phi(qm) = q\phi(m)$, while if $q$ doesn't divide $m$, then $\phi(qm) = (q-1)\phi(m)$ where $\phi$ is the Euler totient function, i.e. $\phi(m) = n \prod_{i=1}^n \left(1 - \frac{1}{p_i}\right)$ with $m=p_1^{e_1} \times \cdots \times p_k^{e_k}$

I am a bit stuck with this.

I have tried this: $$\phi(qm) = qm \prod_{i=1}^n \left(1 - \frac{1}{p_i}\right)\left(1-\frac{1}{q}\right) = q\left(1-\frac{1}{q}\right)m\prod_{i=1}^n \left(1 - \frac{1}{p_i}\right)$$However, this gives the second result in the case where $q$ doesn't divide $m$. I can't seem to get the first result and I don't think I have used so far that $q$ does not divide $m$.

The formula $\phi(qm) = q\phi(m) - \phi(m)$ seems to suggest that if $q$ divides $m$, then $\phi(m) = 0$, which I can't also seem to understand, as I think $\phi(m)$ is independent of $q$...?

Answer 1

Note that if $q \mid m$ then we have that $q$ appears in the prime factorization of $m$. So we get that:

$$\phi(qm) = qm\left(1 - \frac 1q\right)\left( 1 - \frac 1{p_1}\right) \cdots \left(1 - \frac 1{p_n}\right) = q\phi(m)$$

If $q \not \mid m$ it doesn't appear in the prime factorization then we have that $\phi(m) = m\left( 1 - \frac 1{p_1}\right) \cdots \left(1 - \frac 1{p_n}\right)$, so we get that $\phi(qm) = q\left(1 - \frac 1q \right)\phi(m) = (q-1)\phi(m)$

Answer 2

When you write $$ \prod_{i=1}^n \left(1 - \frac{1}{p_i}\right)\left(1-\frac{1}{q}\right)$$ you are assuming that $q \neq p_i$ for all $i$, which is the assumption that $q$ does not divide $m$.

When $q|m$ then $q=p_i$ for some $i$, so the first equality should be $$\phi(qm) = qm \prod_{i=1}^n \left(1 - \frac{1}{p_i}\right)$$

Answer 3

I'll give a more direct proof not using the formula for $\phi$ in terms of prime factorization (and in fact you could then use this proof to derive that formula for $\phi$).

For the first case, suppose $q \mid m$. Overview of proof: In this case, the numbers less than $qm$ relatively prime to $qm$ are just the numbers less than $m$ relatively prime to $m$, repeated $q$ times and translated upwards by small multiples of $m$.

Full proof: In this case, or any $n$, we have $\gcd(n, qm) = 1$ if and only if $\gcd(n, m) = 1$. (For the forward direction, clearly $\gcd(n, m) \mid \gcd(n, qm)$; for the reverse direction, if $\gcd(n, m) = 1$, then we also have $\gcd(n, q) = 1$ since $q \mid m$, so $\gcd(n, qm) = 1$.)

However, we also have $\gcd(n, m) = \gcd(n ~ \mathbf{mod} ~ m, m)$, so $\gcd(n, qm) = 1$ if and only if $\gcd(n ~ \mathbf{mod} ~ m, m) = 1$. Now, consider the bijection $$f : \{ n \in \mathbb{N} \mid 0 \le n < qm \} \to \{ n \in \mathbb{N} \mid 0 \le n < q \} \times \{ n \in \mathbb{N} \mid 0 \le n < m \}, \\ n \mapsto \left(\left\lfloor \frac{n}{m} \right\rfloor, n ~ \mathbf{mod} ~ m \right).$$ Then by the preceding argument, the image under $f$ of $\{ n \in \mathbb{N} \mid 0 \le n < qm, \gcd(n, qm) = 1 \}$ is exactly $\{ n \in \mathbb{N} \mid 0 \le n < q \} \times \{ n \in \mathbb{N} \mid 0 \le n < m, \gcd(n, m) = 1 \}$. From this, it follows that $\phi(qm) = q \phi(m)$. $\square$

---

Now for the second case, suppose $q \nmid m$. Overview of proof: In this case, using the Chinese Remainder Theorem, choosing a small number relatively prime to $qm$ is equivalent to choosing a remainder $\pmod q$ which is nonzero, and then choosing a remainder $\pmod m$ which is relatively prime to $m$.

Full proof: In this case, for any $n$, we have $\gcd(n, qm) = 1$ if and only if $\gcd(n, q) = 1$ and $\gcd(n, m) = 1$. (The forward direction is again easy, and the reverse direction follows from the fact that $\gcd(q, m) = 1$.) Now, from the Chinese Remainder Theorem, we get a bijection $$f : \{ n \in \mathbb{N} \mid 0 \le n < qm \} \to \{ n \in \mathbb{N} \mid 0 \le n < q \} \times \{ n \in \mathbb{N} \mid 0 \le n < m \}, \\ n \mapsto (n ~ \mathbf{mod} ~ q, n ~ \mathbf{mod} ~ m).$$ By the previous observation, the image under $f$ of $\{ n \in \mathbb{N} \mid 0 \le n < qm, \gcd(n, qm) = 1 \}$ is exactly $\{ n \in \mathbb{N} \mid 0 \le n < q, \gcd(n, q) = 1 \} \times \{ n \in \mathbb{N} \mid 0 \le n < m, \gcd(n, m) = 1 \}$. It follows that $\phi(qm) = \phi(q) \phi(m) = (q-1) \phi(m)$. $\square$

(In fact, pretty much the same proof shows that if $\gcd(a, b) = 1$, then $\phi(ab) = \phi(a) \phi(b)$.)