Finding all the values of n, such that $ \varphi (n) = 12 $

Question

I have not broken this down very far. I have come to the conclusion that there are infinitely many values for n where there exists 12 coprimes to n. Since there are infinitely many primes, and primes are coprimes to any number smaller than that prime, I reach that conclusion. Can anyone stop me and tell me where I'm going wrong or how to approach this.

I've used the theorem:

$ \varphi (n) = ((1-\frac{1}{p_{1}})...(1-\frac{1}{p_{k}})) $

But to compute these values would one not need to write a program to run which slots in all these primes?

Answer 1

Your conclusion is wrong. For now, forget the formula involving reciprocals.

If $p$ is prime, then $\phi(p) = p - 1$. Given $k > 1$, we have $\phi(p^k) = p^{k - 1}(p - 1)$. Also, this function is multiplicative, meaning that $\phi(pq) = \phi(p) \phi(q)$ if $\gcd(p, q) = 1$. Furthermore, there are only two exceptions to $\phi(m) > \sqrt{m}$.

So, to find all solutions for $\phi(n) = 12$ you need to figure out the finite set of ways to express $12$ as a product of numbers $1$ less than a prime and/or powers of a prime times $1$ less than that prime.

• $12$ is one less than prime, $13$.
• $12 = 2 \times 6$, and $21 = 3 \times 7$.
• $12 = 1 \times 12$. This might seem obvious and pointless, until you look at $26 = 2 \times 13$
• $28 = 2^2 \times 7$ corresponds to $12 = 2 \times 6$ because $\varphi(4) = 2$
• $36 = 2^2 \times 3^2$ also corresponds to $12 = 2 \times 6$ because $\varphi(9) = 6$
• $42 = 2 \times 3 \times 7$ also corresponds to $12 = 2 \times 6$

and you don't need to look at oh dang, I don't have time to finish up this answer anyone else do me the favor?

EDIT: Robert Soupe here. I completed the table explaining the correspondence between values of $n$ such that $\varphi(n) = 12$ and products that give 12. I really don't know where Jim is going with that stuff about $\varphi(n) > \sqrt{n}$ (though I do know the two exceptions: 2 and 6).

Answer 2

First of all, be careful, you forgot a term in your expression of $\varphi{(n)} = n \left(1-\dfrac{1}{p_{1}}\right)...\left(1-\dfrac{1}{p_{k}}\right)$ : there is a $n$.

Developping the first formula, if $n = p_1^{\alpha_1}...p_n^{\alpha_n}$, then $\varphi{(n)} = p_1^{\alpha_1-1}(p_1-1)...p_n^{\alpha_n-1}(p_n-1).$

If $\varphi{(n)} = 12 = 2*2*3$, we only have to find all the possibilities for the $p_i$ and $\alpha_i$.

If $3$ is alone, it is a $p_i^{\alpha_i-1}$ term (otherwise it would be a $(p_i-1)$ term, and $p_i$ would be $4$, which isn't prime). It goes inevitably with a $(p_i-1)$ term of $2$.

We only have a $2$ left. Hence the only possible match for him is a $(2*1)$ since a $(1*2)$ would imply another $p_i = 3$. This yields $n = 36$ and is the unique possibility with $3$ not being paired.

$3$ can be paired with a $2$ to form a $6$. This $6$ is obviously a $(p_i-1)$ term, so $p_i$ is $7$, with multiplicity $1$ because $7$ is not in our list of factors. The last $2$ can exist in the form $(2*1)$ or $(1*2)$. This yields $n = 28$ and $21$ respectively. Let's not forget the possible $(1*1)$ that can happen in the second case since $2$ isn't a factor in this case. This gives us $n=42$.

Finally, there can exist a lonely $3*2*2$ term. Once again since $12$ is not prime, it is a $(p_i-1)$ term, with $p_i$ being $13$ with multiplicity $1$. But this is not over yet. Even if we have no factors left, we can still have a $(1*1)$ term, like before. If it is there, then $n = 26$. Otherwise, $n=13$.

The final list is : $13, 21, 26, 28, 36, 42$.

Answer 3

Elaborating on James47's answer as he requested: Write $n = q_1 \cdots q_k$ for $q_i = p_i^{n_i}$ with the $p_i$ distinct. Then $$\phi(n) = \phi(q_1) \cdots \phi(q_k) = p_1^{n_i - 1} \cdots p_k^{n_k - 1}(p_1 - 1) \cdots (p_k - 1) = 12.$$ It's then just a matter of listing the $(q_1, \dots, q_k)$ satisfying the equation above. In particular, each $p_i^{n_i - 1}$ and $p_i - 1$ must divide $12$, which limits the possibilities to $q_i = 2, 2^2, 2^3, 3, 3^2, 5, 7,$ and $13$. That should be enough to brute-force the result.