Solve for $m\in\mathbb{N}$ the equation $\phi (m)=12$

Question

Solve for $m\in\mathbb{N}$ the equation $\phi (m)=12$

I found (by trial) $m=\{13,21,26,28,36\}$, but do not know if misinterpreted the problem, but actually I suppose I have to find an equation that generates these values​​? is how? Is there a way to solve $\phi(m)=k$, with $k\in\mathbb{N}$?

Answer 1

Hints: we have that

$$12=\varphi(m)=m\prod_{p\mid m,\,p\;\text{prime}}\left(1-\frac1p\right)$$

Observe that the above seriously limits the number and kind of primes factors $\;m\;$ can have...

Answer 2

There is a formula : if $m=p^a*q^b*...$ then $\phi(m) = (p-1)*p^{a-1}*(q-1)*q^{b-1}*...$

Answer 3

A small remark. If $\phi (m) = n$ and $m$ is odd, then $\phi (2m) = n$. Hence $42$ should be in your list.

Answer 4

You have $\psi (m )=12$ and you have $$12=\psi(m)=m~\large \Pi_{p | m}\big(\frac{ p - 1}{p}\big)$$

So, each $p$ which divides $m$ should be such that $p-1$ divides $12$.(There is a gap and it would be your responsibility to verify this).

So, what are all primes $p$ such that $p-1$ divides $12$.

It would not take much time to see that only possible $p$ are ??? (Do not look at the spoiler box)

$p\in \{2,3,5,7,13\} $

We are not yet sure if all these primes divide $m$,

It would be your turn to check possible values of $m$

• Suppose $2$ is only factor of $m$ then $m=?$
• Suppose $3$ is only factor of $m$ then $m=?$
• Suppose $5$ is only factor of $m$ then $m=?$
• Suppose $7$ is only factor of $m$ then $m=?$
• Suppose $13$ is only factor of $m$ then $m=?$

you should check all other possibilities taking two at a time,taking three at a time and so on..

I am sure you would be convinced just after few steps that you can neglect some cases easily..

Answer 5

Remark 1: If $p$ is a prime $p|n$ then $p-1|12$. This shows that the only primes which could divide $n$ are $\{ 2, 3, 5, 7, 13 \}$.

Remark 2: If $p^2|n$ then $p(p-1)|12$. This shows that $5^2 \nmid n, 7^2 \nmid n$ and $13^2 \nmid n$.

Now we go systematically through all prime factors , starting from the biggest.

Case 1: $13|n$. Then $n=13m$ with $13 \nmid m$. Then

$$12=\phi(13m)=\phi(13) \phi(m)=12 \phi (m) \Rightarrow \phi(m)=1 \,.$$ There are only $2$ values $m$ can take.

Case 2: $7|n, 13 \nmid m$. Then $n=7m$ with $7 \nmid m$. Then $$12=\phi(7m)=\phi(7) \phi(m)=6 \phi (m) \Rightarrow \phi(m)=2 \,.$$ There are only $3$ values $m$ can take.

Case 3: $5|n, 7 \nmid m, 13 \nmid m$. Then $n=5m$ with $5 \nmid m$. Then $$12=\phi(5m)=\phi(5) \phi(m)=4 \phi (m) \Rightarrow \phi(m)=3 \,.$$ But this is not possible (why?)

Case 4: $5\nmid n, 7 \nmid m, 13 \nmid m$. Then $$n=2^a3^b$$

Now break the problem in three subcases, eacn being easy to solve:

Subcase 1: $a=0$. In this case $n=3^b$ and $$12= \phi(3^b)=2\cdot 3^{b-1} \,.$$ no solution.

Subcase 2: $b=0$. In this case $n=2^a$ and $$12= \phi(2^a)= 2^{a-1} \,.$$ no solution.

Subcase 3: $a\neq 0, b\neq 0$. In this case
$$12= \phi(2^a3^b)=2\cdot 2^{a-1}3^{b-1} \,.$$ There is one solution in this case..