# Why is the Euler phi function $\varphi(n)> 2$ for $n\ge 7$?

Why is the Euler phi function $\varphi(n)> 2$ for $n\ge 7$?

I am not sure how to prove this.

• There are too many different primes $<n$ for $\varphi(n)$ to be $2$. – Arthur Apr 12 '18 at 21:33
• I've considered this. There is $2,3,5$ less than $7$, but not sure how this proves it. – Al Jebr Apr 12 '18 at 21:36
• If $n > 6$, then $n$ must have a prime factor $p \geqslant 5$, or it must be divisible by one of $3^2, 2^2\cdot 3$, or $2^3$. Each of those conditions implies $\varphi(n) > 2$. – Daniel Fischer Apr 12 '18 at 21:42
• More generally, see this question. – Dietrich Burde Apr 13 '18 at 12:55

Let $n\geq7$. If $n$ is odd, then $1,2$ and $n-1$ are distinct and all coprime with $n$. If $n$ is even, then Bertrand's postulate says that there is some prime $p$ with $n/2<p<n-2$, and we therefore have $1,p$ and $n-1$ which are all distinct and coprime with $n$. We conclude that $\varphi(n)\geq 3$.

• Do we need Bertrand's postulate? Isn't $1$ and $n-1$ enough? – qwr Apr 12 '18 at 21:57
• @qwr: we are trying to show three numbers coprime to $n$. $1$ and $n-1$ are only two. – Ross Millikan Apr 12 '18 at 22:01
• @qwr I am sure there are more elementary ways to prove this, but it works. Also, $n=8$ is the first even number for which Bertrand's postulate (in this formulation) is true, so it matches the given bounds on $n$ perfectly. – Arthur Apr 12 '18 at 22:03

Consider the contrapositive:

If $\varphi(n) \le 2$, then $n < 7$.

The main tool is

If $n$ has a prime factor $p$, then $p-1$ divides $\varphi(n)$.

If $\varphi(n)=1$, then either $n$ has no prime factor and so $n=1$, or $p-1=1$ and so $n$ is a power of $2$. Only $n=2$ works.

Thus, we may assume that $\varphi(n)=2$ and $n>1$.

If $n$ has an odd prime factor $p$, then $p-1$ divides $\varphi(n)=2$, and so $p=3$. Then $n$ is a power of $3$ or twice a power of $3$. Only $n=3$ or $n=6$ work.

If $n$ has no odd prime factor, then $n$ is a power of $2$. Only $n=4$ works.

Bottom line:

If $\varphi(n) \le 2$, then $n=1,2,3,4,6$.

Let $n= \prod p_i^{k_i}$ then $\phi(n) = \prod(p_i-1)\prod p_i^{k_i - 1}$

If $\phi(n) =1$ then $\prod(p_i - 1) =1$ and $p_i^{k_i - 1} = 1$.

$p_i^{k_i-1} = 1$ means $k_i - 1 = 0$ and $k_i = 1$. $\prod(p_i -1) =$ means that either there are no prime $p_i$s or the only prime factor is $2$.

So $n =1$ or $n = 2$.

If $\phi(n) = 2$ then either A) $\prod(p_i-1) =2$ and $\prod p_i^{k_i -1} = 1$ or B) $\prod(p_i - 1) = 1$ and $\prod p_i^{k_i -1} = 2$.

If A) Then either A1) $p_1 = 3$ is the only prime factor and $k_1= 1$; or A2) $p_1 = 2;p_2=3$ are the only prime factors and $k_1=k_2 = 1$. If B) then $p_1 = 2$ is the only prime factor and $k_1 - 1 = 1$ so $k_1 = 2$.

If A1) then $n = 3^1=3$.

If A2) then $n = 2^1*3^1 = 6$.

if B) then $n = 2^2 = 4$.

So those are the only cases where $\phi(n) \le 2$.

====

Or directly.

If any prime $p \ge 5$ divides $n$ then $p-1|\phi(n)$ so $n\ge p-1 \ge 4$.

If $9$ (or any power greater than one of $3$) divides $n$ then $3|\phi(n)$ and $\phi(n) \ge 3$.

If $12|n$ then $(3-1)*2^1 = 4|\phi(n)$ and $\phi(n) \ge 4$.

If $8|n$ then $4|\phi(n)$ and $\phi(n) \ge 4$.

If $n \ge 7$ then either $n$ has a prime factor greater than $3$ or If not $n = 2^k 3^j$. If so then either $9|n$ or $n = 2^k3^j; j\le 1$. Now as $3,6 < 7$ then if $n = 2^k3$ then $2^k \ge 4$ and $12|n$. If not then $n = 2^k$ but as $n > 7$, $k \ge 3$ and $8|n$.

In any of these cases $\phi(n) \ge 3$.

Euler's phi, $\phi(n)$, counts the number of positive integers less than $n$ that are coprime to $n$.

Clearly for any $n\ge 3$, we have $1$ and $n{-}1$ coprime to $n$. $\phi(n)=2$ would imply that these are the only such coprime numbers below $n$.

However, when $n\ge 7$, we know that there are at least three primes less than $n{-}1$, and that not every prime less than $n$ will divide $n$, since for example $2\cdot 3 \cdot 5=30$ would include another $7$ primes, etc. Thus $\phi(n)>2$.