Problem 1: Show that $\phi(n)$ is even for all $n \geq 3$.

Proof: Assume that n is a power of 2, let us say that $n=2^k$, with $k \geq 2$. By the Phi Function Formula, we have $\phi(n) = \phi(2^k)=2^k - 2^{k-1}=2^k(1/2)=2^{k-1}$, which $\phi(n)$ is an even integer.

If n isn't a power of 2, then it is divisible by an odd prime p. Thus, $n=p^km$, where $k \geq 1$ and $gcd(p^k,m)=1$. By the theorem $\phi(mn)=\phi(n)\phi(m)$,


which is 2|p-1, since p is odd prime.

Problem 2: Describe, with proof, all $n$ for which $\phi(n)$ is divisible by $2$, but not by $4$.

How would you solve this problem? Can you use Problem 1?


HINT: If $p$ is prime, $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$. If $m$ and $n$ are relatively prime, then $\varphi(mn)=\varphi(m)\varphi(n)$. And every $n\ge 1$ is a product of powers of distinct primes. These facts make the first question very easy to answer and are sufficient to answer the second question as well.

You might find it helpful to look at some numerical data while you’re thinking about the problem:

$$\begin{array}{c|c|c} n&\text{prime factorization}&\varphi(n)\\ \hline 2&2^1&1\\ 3&\color{blue}{3^1}&2\\ 4&2^2&2\\ 5&\color{blue}{5^1}&4\\ 6&2^1\cdot\color{blue}{3^1}&2\\ 7&\color{blue}{7^1}&6\\ 8&2^3&4\\ 9&\color{blue}{3^2}&6\\ 10&2^1\cdot\color{blue}{5^1}&4\\ 11&\color{blue}{11^1}&10\\ 12&2^2\cdot\color{blue}{3^1}&4\\ 13&\color{blue}{13^1}&12\\ 14&2^1\cdot\color{blue}{7^1}&6\\ 15&\color{blue}{3^1}\cdot\color{blue}{5^1}&8\\ 16&2^4&8\\ 17&\color{blue}{17^1}&16\\ 18&2^1\cdot\color{blue}{3^2}&6\\ 19&\color{blue}{19^1}&18\\ 20&2^2\cdot\color{blue}{5^1}&8\\ \hline 25&\color{blue}{5^2}&20\\ \hline 27&\color{blue}{3^3}&18\\ \hline 30&2^1\cdot\color{blue}{3^1}\cdot\color{blue}{5^1}&8 \end{array}$$

You might also find this article useful.

| cite | improve this answer | |
  • $\begingroup$ I don't understand how to apply the prime concept to where n isnt prime $\endgroup$ – Username Unknown Jul 27 '13 at 20:59
  • 3
    $\begingroup$ @DramaFreak: That’s the point of the second sentence of my answer. $\endgroup$ – Brian M. Scott Jul 27 '13 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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