Number Theory: Find all solutions of $\phi(n)=16$ and $\phi(n)=24$

Question

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.

Answer 1

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.

Answer 2

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

1. 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$.
2. 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$.

Answer 3

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.

Answer 4

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.