Euler's phi function $\phi(n)$ is even for all $n \geq 3$; when is it not divisible by $4$?

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

$\phi(n)=\phi(p^km)=\phi(p^k)\phi(m)=p^k(p-1)\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}$$

• I don't understand how to apply the prime concept to where n isnt prime Jul 27 '13 at 20:59
• @DramaFreak: That’s the point of the second sentence of my answer. Jul 27 '13 at 21:08

Let's get one small case out of the way. For $$n = 4$$, $$\phi(n) = 2$$ which is not divisible by 4.

Now let's tackle the general cases.

Let n be a number whose prime factorization is

$$2^{k_0}*p_1^{k_1}*p_2^{k_2}...p_r^{k_r}$$

Note that each term in the above product is pairwise co-prime as they are powers of primes.

We can find $$\phi(n)$$ using the co-prime product rule:

$$\phi(n) = max(1, 2^{k_0 - 1})*(p_1^{k_1} - p_1^{k_1 - 1})*...(p_r^{k_r} - p_r^{k_r - 1})$$

The "max" term is used because if $$k_0 = 0, 2^{k_0 - 1}$$ is fractional.

For $$\phi(n)$$ to be divisible by 4, the total number of 2's in the above expression should be at least 2. Additionally, any of the terms being divisible by 4 will also suffice.

Note that odd primes/numbers can only be 1 or 3 mod 4. If $$n$$ has a prime divisor $$p_i$$ which is 1 mod 4, then both terms in the expression $$p_i^{k_i}-p_i^{k_i - 1}$$ are 1 mod 4, so the expression is divisible by 4.

Note that for any prime, the term $$p_i^{k_i}-p_i^{k_i - 1}$$ will be even as it's the difference of two odd numbers. So we can't have more than one odd prime factor.

We also can't have $$k_0 \geq 3$$, as that automatically adds a $$2^2 = 4$$ in the expression.

Basically, we have to limit $$\phi(n)$$ to one or zero 2s as factors.

To satisfy the condition:

$$4 \nmid \phi(n) = max(1, 2^{k_0 - 1})*(p_1^{k_1} - p_1^{k_1 - 1})*...(p_r^{k_r} - p_r^{k_r - 1})$$,

1. $$k_0 = 2$$ and n has no odd prime factors, i.e. n = 4
2. $$k_0 \in \{0,1\}$$ and n has only one odd prime factor of the form $$4k+3$$. This prime factor can take any integral power k, because $$p^k - p^{k-1}$$ reduced mod 4 is $$3^k - 3^{k-1}$$ which is $$(-1)^k - (-1)^{k-1}$$ . One of $$k,k-1$$ is even and the other is odd, so we have either $$-1 - 1 = -2$$ or $$1 - (-1) = 2$$ mod 4.

So the values of $$n$$ for which $$\phi(n)$$ is not divisible by 4 are:

1. $$n = 4$$
2. $$n = 2p^k$$ where $$p$$ is a prime of the form $$4k+3$$.

This is a simple direct a priori argument that does not seem to rely on expressing $$\phi{(n)}$$ in terms of the prime factorization of $$n$$. It only uses the definition of $$\phi{(n)}$$ as the number of positive integers prime to $$n$$: If $$n>2$$, and $$t\in{[1,n]}$$ is such that $$\gcd{(t,n)}=1$$, then it must be the case that $$\gcd{(n-t,n)}=1$$. So the positive integers that are prime to $$n$$ occur in pairs. This proves that $$\phi{(n)}$$ is even when $$n$$ is odd. If $$n$$ is even, the only possibility for $$t=(n-t)$$ is $$t=n/2$$, But as $$2t=n$$, $$n/2$$ is not prime to $$n$$. (Indeed $$n/2$$ is itself the greatest common divisor of $$n/2$$ and $$n$$.) Thus even in the case $$n$$ is even, the positive integers in $$[1,n]$$ that are prime to $$n$$ occur in distinct pairs. This forces us to conclude that $$\phi{(n)}$$ must be an even positive integer for all integers $$n>2$$.