All numbers less than 100 with phi(n) = 64

Question

So the question is to find all natural numbers less than 100 where $\phi(n) = 64$ (Euler totient function).

I read somewhere here on Mathematics SE, and tried something like below.

$64 = 2^6$

From

$$\prod p^{\alpha(p)-1}(p-1) = 64$$

I got {1, 2, 4, 16} as possible values for $(p-1)$, and from that: $p_i \in \{2, 3, 5, 17\}$.

From which I figured $n = 2^a\cdot3^b\cdot5^c\cdot17^d$

But from here onwards, I'm stuck. How do I go about figuring the a, b, c, and d values? And help in the right direction would be great! (please note that I'm kind of a beginner)

Answer 1

As discussed in the comments:

Simple divisibility considerations tell us that $$n=2^a3^b5^c17^d\quad 0≤a≤6\quad 0≤b,c,d≤1$$

We note that $$\varphi(3)=2\quad \varphi(5)=2^2\quad \varphi(17)=2^4$$

It follows that $\varphi(3^b5^c17^d)=2^{b+2c+4d}$

We work case by case, from values of $a$.

$a=0$ We want $b+2c+4d=6$ Easy to see the only case here is $(a,b,c,d)=(0,0,1,1)$ Thus we get $n=5\times 17=85$ Thus $\boxed {n=85}$ works

$a=1$ We want $b+2c+4d=6$ As $2\times 85>0$ we get no new cases.

$a=2$ We want $b+2c+4d=5$ Easy to see the only case here is $(a,b,c,d)=(2,1,0,1)$ Thus we get $n=2^2\times 3\times 17>100$

$a=3$ We want $b+2c+4d=4$ Easy to see the only case here is $(a,b,c,d)=(3,0,0,1)$ Thus we get $n=2^3\times 17>100$

$a=4$ We want $b+2c+4d=3$ Easy to see the only case here is $(a,b,c,d)=(4,1,1,0)$ Thus we get $n=2^4\times 3\times 5>100$

$a=5$ We want $b+2c+4d=2$ Easy to see the only case here is $(a,b,c,d)=(5,0,1,0)$ Thus we get $n=2^5\times 5>100$

$a=6$ We want $b+2c+4d=1$ Easy to see the only case here is $(a,b,c,d)=(6,1,0,0)$ Thus we get $n=2^6\times 3>100$

So, after all that work, the only solution less than $100$ is $85$.

Answer 2

You have to solve in natural numbers: $\; a+b+2c+4d=7$, with the constraints $b,c,d\le 1$ and of course, $a\le 7$.

Case 1: if $d=1$, you have to solve $a+b+2c=3$, whence $$\begin{cases}c=1,\;b=1,\;a=0&(17\cdot5\cdot3)\\ c=1,\;b=0,\;a=1&(17\cdot5\cdot2)\\ c=0,\;b=1,\;a=2\quad&(17\cdot3\cdot 2^2)\\ c=0,\;b=0,\;a=3&(17\cdot 2^3) \end{cases}$$ Case 2: if $d=0,\;c=1$, you have to solve $a+b=5$, whence $$\begin{cases} b=1,\;a=4\quad&(5\cdot3\cdot 2^4)\\ b=0,\;a=5&(5\cdot 2^5) \end{cases}$$

Case 3: if $d=0,\;c=0$, you have to solve $a+b=7$, whence $$\begin{cases} b=1,\;a=6\quad&(3\cdot 2^6)\\ b=0,\;a=7&( 2^7) \end{cases}$$ So the solutions are $$n\in\{85,128,136,160,170,192,204,240\}.$$