\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

This question has been broken down into a series of cases.
However, the objective is to prove that $\phi(n)\leq n-\sqrt(n)$
when $n$ is a composite integer. Therefore full marks for parts
(i)-(vii) may alternatively be obtained by just giving an
alternative proof for part (vii).

\begin{description}

\item[(i)]
Give, without proof, the formula for Euler's function, $\phi(n)$,
in terms of the prime power factorisation  of $n$.

\item[(ii)]
If $p_1,p_2$ are distinct primes show that

$$\phi(p_1p_2)\leq p_1p_2-\sqrt{p_1p_2}.$$

\item[(iii)]
If $p_1,p_2$ are distinct primes and $\alpha$ is an integer such
that $\alpha\geq2$ show that

$$\phi(p_1p_2^\alpha)\leq p_1p_2^\alpha-\sqrt{p_1p_2^\alpha}.$$

\item[(iv)]
If $p_1,p_2,p_3$ are distinct primes show that

$$\phi(p_1p_2p_3)\leq p_1p_2p_3-\sqrt{p_1p_2p_3}.$$

\item[(v)]
If $p$ is a prime and $\alpha$ is a positive integer such
$\alpha\geq2$ show that

$$\phi(p^\alpha)\leq p^\alpha-\sqrt{p^\alpha}.$$

\item[(vi)]
If $n_1,n_2\geq2$ are integers show that

$$(n_1-\sqrt{n_1})(n_2-\sqrt{n_2})\leq(n_1n_2-\sqrt{n_1n_2}).$$

\item[(vii)]
If $n$ is an integer which is not prime use parts (i)-(vi) to show
that

$$\phi(n)\leq n-\sqrt{n}.$$

\item[(viii)]
Does the inequality of (vi) hold when $n$ is prime?

\end{description}



ANSWER

\begin{description}

\item[(i)]
If $n=p_1^{\alpha_1}\ldots p_r^{\alpha_r}$ with each $\alpha_i\geq
1$ and $p_1,\ldots, p_r$ distinct primes then

$$\phi(n)=p_1^{\alpha_1-1}(p_I-1)p_2^{\alpha_2-1}(p_2-1)\ldots
p_r^{\alpha_r-1}(p_r-1).$$

\item[(ii)]
If $2\leq p_1<p_2$ then $\phi(p_1p_2)p_1p_2-p_1-p_2+1$ so that the
required inequality will follow from

$$\sqrt{p_1p_2}\leq p_1+p_2-1$$

which follows in turn from

$$p_1p_2\leq p_2^3\leq(p_i+p_2-1)^2.$$

\item[(iii)]
We have

\begin{eqnarray*}
\phi(p_1p_2^\alpha)&=&(p_1-1)(p_2^\alpha-p_2^{\alpha-1})\\
&=&p_1p_2^\alpha-p_2^\alpha-p_1p_2^{\alpha_1}+p_2^{\alpha-1}\\
&\leq&p_1p_2^\alpha-p_1p_2^{\alpha-1}\\
&\leq&p_1p_2^\alpha-\sqrt{p_1p_2^\alpha}
\end{eqnarray*}

since $\sqrt{p_1}<p_1$ and $\frac{\alpha}{2}\leq\alpha-1$.

\item[(iv)]
If $2\leq p_1<p_2<p_3$ then

$$\phi(p_1p_2p_3)=p_1p_2p_3-p_1p_2-p_1p_3-p_2p_3+p_1+p_2+p_3-1$$

so that the required inequality will follow from

$$\sqrt{p_1p_2p_3}\leq p_1p_2+p_1p_3+p_2p_3-p_1-p_2-p_3+1$$

which follows in turn from

$$p_1p_2p_3\leq(p_1p_3+p_1p_2-1)^2\leq(p_1p_2+p_1p_3+p_2p_3-p_1p_2p_3+1)^2$$

which holds because $p_2p_3\geq3p_3\geq p_1+p_2+p_3.$

\item[(v)]
We have $\phi(p^\alpha)=p^\alpha-p^{\alpha-1}\leq
p^\alpha-\sqrt{p^\alpha}$ since $\alpha-1\geq\frac{\alpha}{2}$.

\item[(vi)]
We have

\begin{eqnarray*}
(n_1-\sqrt{n_1})(n_2-\sqrt{n_2})&=&
n_1n_2-\sqrt{n_1n_2}+\sqrt{n_1}(\sqrt{n_2}-n_2)+\sqrt{n_2}(\sqrt{n_1}-n_1)\\
&\leq&n_1n_2-\sqrt{n_1n_2}
\end{eqnarray*}

\item[(vii)]
Suppose that the prime factorisation of $n$ is
$n=p_1^{\alpha_1}\ldots p_r^{\alpha_r}$. Since $n$ is composite we
may write $n=n_1n_2\ldots n_s$ where $n_1,\ldots ,n_s$ are
pairwise coprime positive integers each of which is one of the
type considered in parts (ii)-(v). The result now follows from
part (vi) since

\begin{eqnarray*}
\phi(n)&=&\phi(n_1)\ldots\phi(n_s)\\
&\leq&(n_1-\sqrt{n_1})\ldots(n_s-\sqrt{n_s})\\ &\leq&n_1\ldots
n_s-\sqrt{n_1\ldots n_s}
\end{eqnarray*}

by induction on $s$.

\item[(viii)]
When $n$ is prime then $\phi(n)=n-1$ which is greater than
$n-\sqrt{n}$ because $1<\sqrt{n}$. Therefore the inequality fails
fro all primes.

\end{description}




\end{document}