1
$\begingroup$

Prove that $\phi (p-1) \leq (p-1)/2$, where $p\geq 3$ is a prime

My idea:

We know that $\phi (p^k) = p^{k-1} (p-1)$. Then to use the $\phi$ is multiplicative. now I have $\phi (p-1)$ in my hand, but then how to complete? could anyone help me, please?

Edit:
OP didn't check for $p=2$, the only prime where above $\phi (p-1) \leq (p-1)/2$ holds to fail.

$\endgroup$

3 Answers 3

3
$\begingroup$

Note that for every $p\geq 3$, $(p-1)$ is an even number.
Therefore, by fundamental Theorem of Arithmetic, it will have a unique factorization which contains $2^i$, $i\geq 1$.

Now, Note that $$\phi(2^i)=2^{i-1}\text{ or }\phi(2^i)=\frac{2^i}{2}$$.

Therefore, using multipicative nature of $\phi$, we have $$\phi(p-1)=\phi(2^i)\phi(\frac{p-1}{2^i}) \leq \frac{p-1}{2}$$ Case $1$ : $(p-1)$ is an exact power of $2$ i.e. $\frac{p-1}{2^i}=1$

$$\phi(p-1)=\phi(2^i)\phi(1) = \frac{p-1}{2}$$ Case $2$ : $\frac{p-1}{2^i}=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{n}^{\alpha_{n}}$, where $p_{j}\geq 3$ $ \forall j=1,2,...,n$ and $\alpha_{j}\geq 0$ $ \forall j=1,2,...,n$ and alteast one of $\alpha_{j}\geq 1$. $$\phi(\frac{p-1}{2^i})=\phi(p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{n}^{\alpha_{n}})=\phi(p_{1}^{\alpha_{1}})\phi(p_{2}^{\alpha_{2}})...\phi(p_{n}^{\alpha_{n}}) < \frac{p-1}{2^i}$$

Now, Can you complete Case $2$ and combine it with Case $1$ to get the desired answer?

Note: I have used the convention, $\phi(1)=1$.

$\endgroup$
0
3
$\begingroup$

Hint:

Two even numbers can't be coprime.

$\endgroup$
1
  • $\begingroup$ Then what is next? $\endgroup$
    – Intuition
    Jun 25, 2019 at 1:46
2
$\begingroup$

Hint: If $p$ is odd, then $p-1$ is even. If $p$ is even, then $p=2$ and $\phi(1)$ is defined to be $1$ by convention and so exceeds $1/2$.

$\endgroup$
1
  • $\begingroup$ Thank you for clarifying this case $\endgroup$
    – Intuition
    Jun 25, 2019 at 2:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .