Find all the natural numbers where $ϕ(n)=110$ (Euler's totient function) Find all the natural numbers where $ϕ(n)=110$ (Euler's totient function)
What the idea behind this kind of questions?
 A: Hint. Assuming you mean Euler's totient $\phi$, if you factor $n=p_1^{e_1}\cdots p_k^{e_k}$, then
$$
\phi(n)=\phi(p_1^{e_1})\cdots\phi(p_k^{e_k})=p_1^{e_1-1}(p_1-1)\cdots p_k^{e_k-1}(p_k-1)
$$
So look for primes $p$ such that $p-1\mid 110$ and go from that.
A: Hints: if the prime decomposition of $\,n\,$ is
$$n=\prod_{i=1}^np_i^{a_i}\implies \phi(n)=n\prod_{i=1}^n\left(1-\frac{1}{p_i}\right)\implies$$
$$2\cdot5\cdot 11=110=\phi(n)=n\prod_{i=1}^n\left(1-\frac{1}{p_i}\right)\ldots$$
A: The totient of a prime $p$ is $p-1$.  The totient of a prime power $p^n$ is $(p-1)p^{n-1}$.
There can't be more different odd divisors, then the power of $2$, because each new prime brings its own 'supply' of $2$, and an odd factor in a totient comes from odd primes.  
So the solutions is a prime of the form $111$ or $11^2$.  The first is composite, the second is a power of a prime.  (In the case of $42$, which is $2 \cdot 3 \cdot 7$, both $43$ and $7^2$ work.)
Once one has addressed this issue, the next step is to consider the powers of $2$.  The euler totient of $2$ itself is 1, so if $n$ is odd, then both $n$ and $2n$ both have the same totient.  That applies here.  
