\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

Write down the formula for the value of $\phi(n)$ in terms of the
prime factorisation of $n$ and hence find

\begin{description}

\item[(i)]
all $n$ for which $\phi(n)=\frac{4n}{11}$.

\item[(ii)]
all $n$ for which $\phi(n)=2$.

\item[(iii)]
all $n$ for which $\phi(n)=12$.

\end{description}




ANSWER

$\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)$.

\begin{description}

\item[(i)]
If $\phi(n)=\frac{4n}{11}$, then
$\prod_{p|n}\left(1-\frac{1}{p}\right)=\frac{4}{11}$, i.e.
$\prod_{p|n}\left(\frac{p-1}{p}\right)=\frac{4}{11}$.

In the expression $\prod_{p|n}\left(\frac{p-1}{p}\right)$, the
largest prime occurring in $n$ appears in the denominator, but
cannot cancel with anything in the numerator. Thus it re3mains on
the denominator in the simplified expression for
$\prod_{p|n}\left(\frac{p-1}{p}\right)$, so we may deduce that the
largest prime appearing in $n$ is 11. Then
$\prod_{p|n}\left(\frac{p-1}{p}\right)=\prod_{p|n,p<11}\left(\frac{p-1}{p}\right).\frac{10}{11}=\frac{4}{11}$.
Thus $\prod_{p|n,p<11}\left(\frac{p-1}{p}\right)=\frac{2}{5}$, and
so we can similarly deduce that the next largest prime occurring
is 5. Thus
$\prod_{p|n,p<5}\left(\frac{p-1}{p}\right).\frac{4}{5}=\frac{2}{5}$,
so $\prod_{p|n,p<5}\left(\frac{p-1}{p}\right)=\frac{1}{2}$ and we
may now deduce that the only prime occurring is 2. Thus
$\phi(n)=\frac{4n}{11}$ if and only if
$n=2^\alpha.5^\beta.11^\gamma$ for $\alpha,\ \beta,\ \gamma$ all
positive integers.

\item[(ii)]
$\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)=n\prod_{p|n}\left(\frac{p-1}{p}\right)$.
Thus if $n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}$,
then $\phi(n)=p_1^{\alpha_1-1}p_2^{\alpha_2-1}\ldots
p_k^{\alpha_k-1}(p_1-1)(p_2-1)\ldots(p_k-1)$. Now suppose
$\phi(n)=2$. If $p_i$ is a prime $>2$, then $p_i\not|\phi(n)$, so
$\alpha_i=1$. Moreover, $(p_i-1)$ divides $\phi(n)\ (=2)$, so
$p_i$ can only be 3. Thus $n$ takes one of the forms
$2^{\alpha_1}$ or $2^{\alpha_1}.3$ or 3. To see which integers of
these forms are allowed, note

$\phi(2^{\alpha_1})=2^{\alpha_1}\left(1-\frac{1}{2}\right)=2^{\alpha_1-1}=2$
only if $\alpha_1=2$

$\phi(2^{\alpha_1}.3)=\phi(2^{alpha_1})\phi(3)=2^{\alpha_1-1}.3
\left(1-\frac{1}{3}\right)=2^{\alpha_1}=2$ only if $\alpha_1=1$

$\phi(3)=3\left(1-\frac{1}{3}\right)=2$

Thus the possible cases are 2,4 and 6.

\item[(iii)]
If $\phi(n)=12$, we may argue in the same way as above, and deduce
that if $n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}$,
then $\alpha_i=1$ for all primes occurring except those which
divide 12, namely 2 and 3. Moreover, if $p_i$ occurs, then
$(p_i-1)$ divides 12, so $p_i$ can only be 13, 7, 5, 3 or 2.

Since $\prod_{p|n}(p-1)$ must divide 12, we see that the only
prime that can appear together with 13 is 2, so the possibilities
involving 13 are 13 and $2^\alpha.13$, and a quick check shows
that of these, only 13 and 26 satisfy $\phi(n)=12$.

Similarly, the only primes that can occur with 7 are 3 and 2, so
we must check 7, $3^\alpha.7, 2^\alpha.7$ and
$2^\alpha.3^\beta.7$. We note $\phi(7)=6\neq12,
\phi(3^\alpha.7)=\phi(3^\alpha).\phi(7)=3^{\alpha-1}.2.6$, so the
only possibility is $\alpha=1$, giving 21 as a possibility.
$\phi(2^\alpha.7)=\phi(2^\alpha)\phi(7)=2^{\alpha-1}.6=12$ only if
$\alpha=2$, so 28 is a possibility, and
$\phi(2^\alpha.3^\beta.7)=\phi(2^\alpha)\phi(3^\beta).\phi(7)=2^{\alpha-1}.3^{\beta-1}.2.6$,
showing that $\beta=\alpha=1$, so that 42 is a possibility. Thus
the possibilities where $7|n$ are 21,28 and 42.

The case where $5|n$ is quickly eliminated:-

If $n=5m$, where gcd$(5,m)=1$, then
$\phi(n)=\phi(5)\phi(m)=4\phi(m)$, so that $\phi(m)=3$,
contradicting cor.5.5 which tells us that $\phi(m)$ is always even
if $m>2$.

We are left with the possibilities $n=2^\alpha,\ n=3^\alpha$ or
$n=2^\alpha.3^\beta$, and again we may check the formulae to see
that the only case giving $\phi(n)=12$ is $n=2^2.3^2=36$. Thus the
full list of possibilities is 13, 21, 26, 28, 36 and 42.

\end{description}




\end{document}