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.

  • $\begingroup$ Hint for first: Make a list of the powers of $2$ whose $\varphi$ is a power of $2$ less than or equal to $2^4$. Make a list of the odd primes whose $\varphi$ is a power of $2$ less than or equal to $2^4$ (this is a short list, three primes). Then use multiplicativity. $\endgroup$ – André Nicolas Nov 1 '15 at 7:19
  • $\begingroup$ Conditions (1) and (2) mean that you can make a list of the finitely many primes that could divide $n$; from there it should be within reach of pen-and-paper calculation. $\endgroup$ – Greg Martin Nov 1 '15 at 7:21
  • $\begingroup$ Look for integers $d_i = p - 1$ for some prime $p$ such that $d_i | k$. In the case $k = 16$, the divisors are 1, 2, 4, and 8, of which $d_i$ can be 1, 2, or 4 since $8 + 1$ is not prime. $\frac{k}{\prod{d_i}}$ is 2 and $\prod{p_i}$ is 30 so $n = 60$. $\endgroup$ – affinehat Nov 1 '15 at 7:23
  • $\begingroup$ Possible duplicate of How to solve the equation $\phi(n) = k$? $\endgroup$ – Yanior Weg May 7 at 6:54

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.

  • $\begingroup$ I'm not sure how you got the possible values for $n$. How do you know for example that $2^4\cdot 3$ will work but $2^4\cdot 5$ won't? $\endgroup$ – MathQuestion Nov 1 '15 at 19:44
  • $\begingroup$ I figured it out now, thank you so much! $\endgroup$ – MathQuestion Nov 2 '15 at 5:26

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.

  • 1
    $\begingroup$ For case 1), you missed 34. ("Clearly" strikes again!) $\endgroup$ – Mark Dickinson Nov 1 '15 at 8:25
  • $\begingroup$ Right! Clearly I was hasty. $\endgroup$ – DanielWainfleet Nov 1 '15 at 15:38
  • $\begingroup$ Thank you so much, this made it a lot clearer. $\endgroup$ – MathQuestion Nov 2 '15 at 5:25

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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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