0
$\begingroup$

This question already has an answer here:

For $n\ge1$, let $\phi(n)$ be the number of positive integers $\le n$, which are relatively prime to $n$

i. Find all $n$ such that $\phi(n)=\frac n2$ ii. Find all $n$ such that $\phi(n)=4$.

I know the formula for suker totient function but that is not telling me anything. Please help.

$\endgroup$

marked as duplicate by Dietrich Burde number-theory Apr 30 '18 at 10:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

For i. note $\frac{\phi(n)}{n}=\prod_{p\in\mathbb{P},\,p|n}\frac{p-1}{p}$ maintain's $n$'s largest prime factor in its denominator even when expressed in lowest form, so we obtain $\frac{1}{2}$ iff $n$ is a power of $2$. For ii. note $2^2=\prod_{p\in\mathbb{P},\,p^k|n,\,p^{k+1}\nmid n} p^{k-1}(p-1)$ requires each factor of $p^{k-1}(p-1)\ge p-1$ to be $1$, $2$ or $4$, so $p\le 5$. The case $p=5$ only allows $n=5$ or $n=10$ (the latter because $\phi(2)=1$); the case $p=3$ only allows $3|n\land 9\nmid n$, so $\phi(n/3)=2$ and $n/3=4,\,n=12$ (note $n=24$ doesn't work because $12$ is already even); and we have one more option if $2$ is the only prime factor of $n$, viz. $n=8$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.