0
$\begingroup$

I'm looking for an $n \in \Bbb N$ for which $\phi(n) = 40$ where $\phi$ is a Euler-Totient Function

I already found one, namely, $n=41$

How the calculate the $n's$?

$\endgroup$

marked as duplicate by Dietrich Burde, Yanior Weg, Cesareo, José Carlos Santos, Mike Earnest May 7 at 23:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Welcome to MSE. Are you claiming that prime numbers are not natural numbers? $\endgroup$ – José Carlos Santos May 5 at 9:58
  • $\begingroup$ @matemate: Do you mean : Is there any other $n$ for which $\phi(n)=40$ ? $\endgroup$ – Chinnapparaj R May 5 at 9:59
  • $\begingroup$ @ChinnapparajR yes that's what I mean! $\endgroup$ – matemate May 5 at 9:59
  • $\begingroup$ How is $41$ not a natural number? Here is a table of $\phi$ values, the next smallest with $\phi=40$ are $55$, $75$, $82$, $88$, $100$... $\endgroup$ – Conifold May 5 at 10:00
  • $\begingroup$ @Conifold is there any difference in calculating this than this approach?math.stackexchange.com/questions/2261256/… $\endgroup$ – matemate May 5 at 10:04
3
$\begingroup$

If $p$ and $q$ and two distinct primes, then $\varphi(pq)=\varphi(p)\varphi(q)=(p-1)(q-1)$.

So if you choose $p=11$ and $q=5$ you're done !


Now you can search for all solutions. Using essentially the same method as described in the links given above, it is not difficult to prove that the set of solutions for the equation $\varphi(n)=40$ is :

$$S=\{41,55,75,82,88,100,110,132,150\}$$

$\endgroup$
  • $\begingroup$ what about $75$? $\endgroup$ – J. W. Tanner May 5 at 11:27
  • 1
    $\begingroup$ Ooops ! Sorry, I missed a few more cases. Editing ... $\endgroup$ – Adren May 5 at 11:35
1
$\begingroup$

Note that $$ \phi (55)= \phi(11)\phi(5) = 10\times 4 =40$$ and

$$ \phi (100)= \phi(4)\phi(25) = 2\times 20 =40$$ as well.

That is the function is not one-to-one.

$\endgroup$
1
$\begingroup$

Hints:

Use the multiplicative property of $\phi$: if $n$ and $m$ are relatively prime then $\phi(nm)=\phi(n)\phi(m)$.

$40=2\times2\times2\times5*=2\times2\times10=4\times2\times5*=8\times5*=4\times10=20\times2.$

$*\phi(n)$ cannot be an odd number $> 1.$

If $\phi(n)=2$ then $n=3, 4, $ or $6;$ note that $6$ is not relatively prime to the others.

If $\phi(n)=4$ then $n=5, 8, 10, $ or $12.$

If $\phi(n)=10$ then $n=11$ or $22.$

If $\phi(n)=20$ then $n=25, 33, 44, 50, $ or $66.$

$3\times4\times11; 5\times11, 5\times22, 8\times11, 10\times11, 12\times11; 3\times25, 4\times25, 6\times25, 4\times33; 41, 41\times2$

$\endgroup$
1
$\begingroup$

For $1<n\in \Bbb N,$ if $n$ has exactly $m$ prime divisors then $$n=\prod_{j=1}^m(p_j)^{E(p_j)}$$ where $\{p_1,...,p_m\}$ is the set of all prime divisors of $n$, and each $E(p_j)\in \Bbb N.$ And then $$\phi(n)=\prod_{j=1}^m(p_j-1)(p_j)^{E(p_j)-1}.$$ If $\phi(n)=40$ then

(i). For each odd $p_j$ we have $(p_j-1)|40$ so the only possible values for an odd $p_j$ are $3,5,$ and $11.$

(ii). If $3|n$ then $E(3)=1$ Otherwise $3|3^{E(3)-1}|40, $ implying $3|40.$ Similarly if $11|n$ then $E(11)=1.$

(iii). If $5|n$ then $E(5)\le 2.$ Otherwise $5^2|5^{E(5)-1}|40,$ implying $5^2|40.$

(iv). If $2|n$ then $E(2)\le 4.$ Otherwise $2^4|2^{E(2)-1}|40,$ implying $2^4|40.$

(v). By (i) we have $$n=2^A3^B5^C11^D$$ where $A,B,C,D$ are non-negative integers. By (ii), (iii), and (iv) we have $A\le 4,\, B\le 1,\,C\le 2,\, D\le 1.$

(vi). If $A=4$ then $B=C=D=0.$ Otherwise $2^3|2^{A-1}$ and at least one of the (even) terms $3^{B-1}(3-1),\, 5^{C-1}(5-1),\,11^{D-1}(11-1)\,$ would also occur in the product for $\phi(n),$ implying $2^3\cdot 2=16|40.$

But if $A=4$ and $B=C=D=0$ then $n$ is a power of $2$ so $\phi(n)\ne 40.$

Therefore $A\le 3.$

(vii). If $D=0$ then $5|40=\phi(n)=\phi(2^A3^B5^C)$ which requires $C\ge 2.$ But by (ii) we have $C\le 2,$ so $D=0\implies C=2.$

If $D=1$ then $C\le 1$ otherwise $5^2|5^{C-1}(11-1)|\phi(n)=40,$ implying $5^2|40.$

(viii). This narrows it to $16$ potential cases: $A\in \{0,1,2,3\}$ and $B\in \{0,1\}$ and $(C,D)\in \{(2,0),(1,1)\}.$ Now I will leave it to you to find which of these give $n\ne 41$ and $\phi(n)=40.$

$\endgroup$

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