3
$\begingroup$

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)

$\endgroup$
8
  • $\begingroup$ Good start. Say, $d>1$....what could you conclude? (Note: $64=2^6$, not $2^8$, but you don't seem to use that anywhere....) $\endgroup$
    – lulu
    Dec 11, 2016 at 1:23
  • $\begingroup$ @lulu Oops. Corrected ($2^6$). In that case, n would be > 100. So I guess a < 7, b < 5, c < 3, d < 2? $\endgroup$
    – Roshnal
    Dec 11, 2016 at 1:30
  • 1
    $\begingroup$ Well, I agree with you on $a,d$. But if $b$, say were $2$ then $3^2\,|\,n\implies 3\times 2\,|\,64$ which is false. Thus $b,c$ are, like $d$, either $0$ or $1$. So now you just have a few cases to check. $\endgroup$
    – lulu
    Dec 11, 2016 at 1:33
  • $\begingroup$ @lulu Ok, but what is up with $a$? I mean, if take like $a = 5$ and $b = 1$, then $\phi(96) = 32$. I know I'm missing something with the next step :/ $\endgroup$
    – Roshnal
    Dec 11, 2016 at 1:40
  • $\begingroup$ Just go case by case. If $a=6$, then $\varphi(2^6)=2^5$ so you just need to get one factor of $2$...only one place to get it! so this case just gives us $n=2^6\times 3$ (ok, that's bigger than $100$ so it doesn't even count). Now take $a=5$. $\varphi(2^5)=2^4$ so we need two factors of $2$...only one way to get it! so we get $n=2^5\times 5$ which is still too big. But keep going, it's not difficult. $\endgroup$
    – lulu
    Dec 11, 2016 at 1:42

2 Answers 2

2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Trying on WolframAlpha, I get 85 as a solution. True enough, that's $17 \cdot 5$ $\endgroup$
    – Roshnal
    Dec 11, 2016 at 2:35
  • $\begingroup$ @Roshnal Quite right, I was just correcting that. For some reason I thought $85>100$. Thanks! $\endgroup$
    – lulu
    Dec 11, 2016 at 2:36
  • $\begingroup$ @TMM Indeed. Dangers of cutting and pasting. I'll edit. Thanks. $\endgroup$
    – lulu
    Dec 11, 2016 at 2:39
  • $\begingroup$ Thanks a lot for your answer! Made it a whole lot clearer. $\endgroup$
    – Roshnal
    Dec 11, 2016 at 2:50
  • $\begingroup$ @TMM Ah, fair enough. I'll edit accordingly. $\endgroup$
    – lulu
    Dec 11, 2016 at 3:04
1
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ $\varphi(48)$ is not $64$. $\endgroup$
    – lulu
    Dec 11, 2016 at 2:20
  • $\begingroup$ @lulu: Oh yes! I messed up with the r.h.s. of the equation at the end of my computations. I think it's OK now. Thanks for pointing the error. $\endgroup$
    – Bernard
    Dec 11, 2016 at 2:30
  • $\begingroup$ I think $\phi(255)$ is $128$? But if you have $17 \cdot 5$, that appears to be a valid solution with $\phi(85) = 64$ $\endgroup$
    – Roshnal
    Dec 11, 2016 at 2:32
  • $\begingroup$ @Roshnal: You're right. Don't even know how I could get $255$, except it's getting late here. Thanks for pointing it! $\endgroup$
    – Bernard
    Dec 11, 2016 at 2:36
  • $\begingroup$ Well, I wrote $85>100$...so I'm with you on the "getting late" thing. $\endgroup$
    – lulu
    Dec 11, 2016 at 2:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .