Find all the natural numbers where $ϕ(n)=110$ (Euler's totient function)

Question

Find all the natural numbers where $ϕ(n)=110$ (Euler's totient function)

What the idea behind this kind of questions?

Answer 1

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.

Answer 2

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$$

Answer 3

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.