Number Theory: Find all solutions of $\phi(n)=16$ and $\phi(n)=24$ I have this homework problem assigned and I'm a little confused in solving it:
Find all solutions of $\phi(n)=16$ and $\phi(n)=24$ (where $\phi(n)$ is the Euler phi-function).
The hint that's provided says:
If $n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$ satisfies $\phi(n)=k$, then $n=\frac{k}{\prod (p_i-1)}\prod p_i$. Thus the integers $d_i=p_i-1$ can be determined by the conditions (1) $d_i\mid k$, (2) $d_i+1$ is prime, and (3) $\frac{k}{\prod d_i}$ contains no prime factor not in $\prod p_i$.
I'm ok with proving the statements in the hint and I know how to get them, but I'm not sure how to apply them to solve the problem.
 A: I'll make it for $k=16$.
Since $d_i$ divides $16$, it must be a power of two and $d_i+1$ is prime. Then
$$d_i\in\{1,2,4,16\}$$
that is,
$$p_i\in\{2,3,5,17\}$$
So the possible values for $n$ are $2^5$, $2^4\cdot3$, $2^3\cdot5$, $17$, $2\cdot17$ and $2^2\cdot3\cdot5$.
For $24$, start considering the divisors $d$ of $24$ such that $d+1$ is prime.
A: Case 1. $\Phi (n)=16$.If $p$ is an odd prime and $p^2|n$ then $p|\Phi (n)$ which implies $\Phi (n)\ne 16$ . If $p$ is an odd prime and $p|n$ then $(p-1)|\Phi (n)=16$. The odd primes $p$ for which $(p-1)|16$ are $3,5$ and $17$. Therefore    $ n=2^a 3^b 5^c 17^d$  with $\max (b,c,d) =1 $, and $a\leq 5$ because $2^6|n\implies 2^5|\Phi (n)$.  Clearly if $d=1$ then $n=17$ (CORRECTION :or $n=34$). If $ d=0 $ then (i)$n=2^a$ or (ii)$n=2^a. 3$ or (iii) $n-2^a .5$ or (iv) $n=2^a.3.5$....For (i) we have $a=5$. For (ii) we have $a=4$. For (iii) we have  $a=3$. For (iv) we have $a=2$. So $\Phi (n)=16 \iff n\in \{17,34,32,48,40,60\}$......Case 2. $\Phi (n)=24$. If $p$ is an odd prime and $ p^3|n$ then $p^2|\Phi (n)$ which implies $\Phi (n)\ne 24 .$ If $p$ is an odd prime then $( p^2|n \wedge \Phi (n)=24) \implies p|\Phi (n)=24\implies p=3 .$ As in Case (1) the odd primes $p$ for which $(p-1)|24$ are $3,5,7$ ,and $13$. Therefore $n=2^a 3^b 5^c 7^d 13^e$ where $b\leq 2$ and $\max (c,d,e)=1$, and $a\leq 4$ because $2^5|n\implies 2^4|\phi (n).$ This gives a small number of cases to check.
A: If $n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$, then $\phi(n)=\prod_{i=1}^r(p_i^{k_i}-p_i^{k_i-1})=\prod_{i=1}^rp_i^{k_i-1}(p_i-1)$. 
For $\phi(n)=16$, we get 
$$\prod_{i=1}^rp_i^{k_i-1}(p_i-1)=16=2^4$$


*

*If $k_i>1$ for any $i$, then $p_i$ cannot be an odd prime. In which case $p_i=2$ for all $i$. But $p_i's$ are distinct primes, therefore $p_1=2$ and $n=2^{k_1}$. In which case $\phi(n)=16$ implies $2^{k_1-1}=16$. Thus $k_1=5$ and $n=32$.

*If $k_i \leq 1$ for $i \geq 2$. Then $n=2^{k_1}3^{k_2}5^{k_3} \dotsb p_r^{k_r}$, where for $i \geq 2$, $k_i=0$ or $k_i=1$. In which case, $\phi(n)=2^{k_1-1}(3-1)^{k_2}(5-1)^{k_3}\dotsb (p_r-1)^{k_r}$. Thus we want
$$2^{k_1-1}(3-1)^{k_2}(5-1)^{k_3}\dotsb (p_r-1)^{k_r}=16=2^4.$$


Suppose $k_2=1$ and $k_i=0$ for $i \geq 3$, then we have $2^{k_1-1} \cdot 2=16$. In which case $k_1=4$. Thus $n=2^4 \cdot 3$. 
Suppose $k_2,k_3=1$ and $k_i=0$ for $i \geq 4$, then we have $2^{k_1-1} \cdot 2 \cdot 4=16$. In which case $k_1=2$. Thus $n=2^2 \cdot 3 \cdot 5$. 
Similarly you can try other cases. You should see that primes bigger than $5$ will pose a problem except when $p_i=17$.
A: One  obvious candidate is 17, as it is prime and one more than 16.
Take  $16=4\times2\times2$. Can each of these 3 terms be phi of distinct prime powers? Every power of  2 is the phi of next power of 2. The 2 can be realised as phi of 3. Next 2 is not possible. So $16=\phi(8)\times \phi(3)\times ?$, Now we are stuck.
Take another factorization $16=4\times 4=\phi(8)\times \phi(5)$, with gcd(8,5)=1. So $\phi(40)=\phi(8\times5)=16$. 
This way one can find by listing all possible factorizations: You only need to check if individual factors are phi values of prime powers; and if so do they correspond to different primes.
