2
$\begingroup$

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

I am not sure how to prove this.

$\endgroup$
  • 2
    $\begingroup$ There are too many different primes $<n$ for $\varphi(n)$ to be $2$. $\endgroup$ – Arthur Apr 12 '18 at 21:33
  • $\begingroup$ I've considered this. There is $2,3,5$ less than $7$, but not sure how this proves it. $\endgroup$ – Al Jebr Apr 12 '18 at 21:36
  • 1
    $\begingroup$ 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$. $\endgroup$ – Daniel Fischer Apr 12 '18 at 21:42
  • $\begingroup$ More generally, see this question. $\endgroup$ – Dietrich Burde Apr 13 '18 at 12:55
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Do we need Bertrand's postulate? Isn't $1$ and $n-1$ enough? $\endgroup$ – qwr Apr 12 '18 at 21:57
  • 1
    $\begingroup$ @qwr: we are trying to show three numbers coprime to $n$. $1$ and $n-1$ are only two. $\endgroup$ – Ross Millikan Apr 12 '18 at 22:01
  • $\begingroup$ @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. $\endgroup$ – Arthur Apr 12 '18 at 22:03
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.