2
$\begingroup$

To show $n\in\mathbb{N}\setminus \{6\}\Rightarrow 2^{\varphi(n)}\ge n$

I can't follow the proof from http://mathematicalspectacles.blogspot.de/2012/05/interesting-study-of-zsigmondy-primes.html

Lemma 2. There is a part with

If $k=1$ in other word $2^{\varphi(n)}=n+1$. The $\varphi(n)$ numbers $2^i$ for $0\le i \le \varphi(n)-1$ are coprime with $n=2^{\varphi(n)}−1$ and are between 1 and n.

This is clear.

WHY IS : $1\le 2^{\varphi(n)}−2\le n $ The $\le n$ is clear. But why $1\le 2^{\varphi(n)}$?

"and $\gcd(2^{\varphi(n)}−2,n)=1$, we have $2^{\varphi(n)}−2=2^i$ for some $0\le i\le \varphi(n)−1$." This is also clear.

"Hence $2^{\varphi(n)-1}−1=2^{i−1}$, so $2^{\varphi(n)-1}−1=1$ [and] $n=3$."

MY QUESTIONS IS WHY: "It follows that $2^{\varphi(n)}>3n$ holds for odd $n>3$."

It would be great If someone can explain me the 2 points which I can't follow.

2 Answers 2

2

Your first question was presumably intended to ask why $2^{\varphi(n)}-2\ge 1$, not why $2^{\varphi(n)}\ge 1$. One of the hypotheses of Lemma 2 is that $n>1$. Since we have $2^{\varphi(n)}=n+1$ in this case of the proof, we also have $2^{\varphi(n)}-2=(n+1)-2=n-1\ge 1$.

For your second question, recall that the first paragraph of the proof established that if $n$ is odd, then $2^{\varphi(n)}=kn+1$ for some $k\ge 1$. The second paragraph shows that if $k=1$, then $n=3$. Thus, if $n$ is odd and greater than $3$, $k$ must be greater than $1$. But $k$ cannot be $2$, since $2n+1$ is odd, and $2^{\varphi(n)}$ is even (since $n\ge 3$), so $k$ must be at least $3$. Thus, if $n>3$ is odd, we have $2^{\varphi(n)}=kn+1\ge 3n+1>3n$.

2

$1\leq 2^{\phi(n)}$ since $\phi(n)\geq 1$ by definition.

For the second part, the proof makes the observation that since $2^{\phi(n)}=1(\mod n)$, then $2^{\phi(n)}=kn+1$ for some $k\geq 1$ (where $k$ depends on $n$). It then assumes that $k=1$ and shows that $n$ must be 3. In other words if $n$ is NOT 3, then $k>1$. In particular, if $n$ is odd, then $k$ MUST be odd as well, again since $2^{\phi(n)}=kn+1$ and even $\times$ odd+1=odd. In other words, $k\geq 3$ from which the desired result follows.