17
$\begingroup$

Let $\phi(n) $ is the numbers of number that are relatively prime to n.
Then, how could we solve the equation $\phi(n) = k, k > 0?$

For example:

$\phi(n) = 8 $

I can use computer program to check all numbers that are relatively prime to $n$, but I think there must be an easier way to approach this problem.

Base on this formula: $$\prod_{i=0}^{k} p_{i}a^{a_i} $$
The only thing I can see is n must not have a prime factor > 9, otherwise $\phi(n) > 8 $. I really don't know where to start :( ? A hint would be greatly appreciated.

$\endgroup$
3
  • $\begingroup$ You might take a look into this: - jstor.org/stable/2308462 $\endgroup$
    – anonymous
    Feb 27, 2011 at 3:32
  • 2
    $\begingroup$ Solving for $n$ involves splitting the problem into cases and arguing out which divides what. However, $\phi(n) = k$ has only finitely many solution for every $k$ since $\phi(n) \geq \sqrt{n}$ for $n>6$. (For odd $k>1$, no solution exists) $\endgroup$
    – user17762
    Feb 27, 2011 at 3:38
  • $\begingroup$ @ Sivaram Ambikasaran: Thank you for the information. Can you give me one example of dividing into cases. Let take $\phi(n) = 8$. Thank you. $\endgroup$
    – roxrook
    Feb 27, 2011 at 5:42

4 Answers 4

16
$\begingroup$

This is too long to be comment and hence the post.

$\phi(n) = 8$. Note that $\sqrt{n} \leq \phi(n) \leq n-1$.

This implies $n$ is at most $64$. So you could write a brute force computer and compute $\phi(n)$ when $n \in [9,64]$.

A better way would be as follows.

Let $n=\displaystyle \prod_{i=1}^k p_i^{\alpha_i} \Rightarrow \phi(n) = \displaystyle \prod_{i=1}^k p_i^{\alpha_i-1} (p_i-1)$.

First note that $n$ can be of the form $\displaystyle 2^\alpha \left( \prod_{i=1}^k p_i \right)$ i.e. the exponent of the odd primes in the prime factorization of $n$ is $1$. This is so, because if not these primes will then divide $\phi(n) = 8$ which is not possible.

If $k=0$, then we have $n=2^{\alpha}$, $\displaystyle 2^{\alpha-1} = \phi(n) = 2^3 \Rightarrow \alpha=4$. Hence, $k=1 \Rightarrow n=16$.

Let $k=1$. Then we have $n=2^{\alpha} p_1$.

If $\alpha = 0,1$, then $\displaystyle (p_1-1) = \phi(n) = 2^3 \Rightarrow p_1 = 9 \Rightarrow \text{ Not possible}$.

If $\alpha = 2$, then $\displaystyle 2 (p_1 - 1) = \phi(n) = 2^3 \Rightarrow p_1=5$. Hence, $n=20$.

If $\alpha = 3$, then $\displaystyle 2^2 (p_1 - 1) = \phi(n) = 2^3 \Rightarrow p_1=3$. Hence, $n=24$.

Now let $k=2$. Then we have $n=2^{\alpha} p_1 p_2$.

If $\alpha = 0,1$, then $\displaystyle (p_1-1)(p_2-1) = \phi(n) = 2^3 \Rightarrow p_1 = 3, p_2 = 5$. Hence, $n=15$ when $\alpha = 0$ and $n=30$ when $\alpha = 1$

If $\alpha = 2$, then $\displaystyle 2(p_1-1)(p_2-1) = \phi(n) = 2^3 \Rightarrow (p_1-1)(p_2-1) = 4 \Rightarrow \text{ Not Possible}$.

$k=3$ is not possible since $(3-1) \times (5-1) \times (7-1) > 8$.

Hence, the only solutions (hope I have not missed any case) are:

$$n=15,16,20,24,30$$

Similar idea extends to other problems where we want to find the inverse of the totient function.

$\endgroup$
1
  • $\begingroup$ Ambikasaran: Amazing ;) Many thanks. I really appreciated it. $\endgroup$
    – roxrook
    Feb 27, 2011 at 8:02
2
$\begingroup$

See these:

$\endgroup$
0
1
$\begingroup$

I needed this recently and sketched the following algorithmic approach, so I might as well put it here. It's not terribly efficient but it works.

Input: Integer $k>0$

Output: All solutions $x$ of $\varphi(x)=k$.

Pseudocode:

  • Let $Q = \{d+1; d \mid k \text{ and } d+1 \text{ is prime}\}$
  • For all $R \subseteq Q$:
    • Set $l = \prod_{r \in R} (r-1)$
    • If $l \mid k$ and all prime factors of $\frac{k}{l}$ lie in $R$:
      • Report $x=\frac{k}{l}\cdot \prod_{r\in R} r$

It is based on the fact that if prime $q\mid x$, then $q-1 \mid \varphi(x)=k$, so all prime factors of $x$ must come from a suitable divisor $d \mid k$ for which $d+1$ is a prime. There are only finitely many of these so we store them in a set $Q$. Then for each combination of these primes, there is at most one $x$ which has exactly these prime factors. It also immediately implies there is at most $2^{\tau(k)}$ solutions (where $\tau(k)$ is number of positive divisors of $k$).

For example if $\varphi(n) = 8$, then $k=8$ and divisors $d$ of $k$ are $1,2,4,8$. So primes $d+1$ form $Q=\{2,3,5\}$. Then for each $R \subseteq Q$ we compute: \begin{array}{c|c|c|c|l} R&l= \prod_{r \in R} (r-1)&\frac{k}{l}&x=\frac{k}{l}\cdot \prod_{r\in R} r\\ \hline \emptyset&1&2^3&\text{None}\, ( \{2\} \not\subseteq \emptyset ) &\\ \{2\}&1&2^3&16& \\ \{3\}&2&2^2&\text{None}\, (\{2\} \not\subseteq \{3\})& \\ \{5\}&4&2^1&\text{None}\, (\{2\} \not\subseteq \{5\})& \\ \{2,3\}&2&2^2&24& \\ \{2,5\}&4&2^1&20& \\ \{3,5\}&8&1&15& \\ \{2,3,5\}&8&1&30& \\ \end{array} Hence $x \in \{15,16,20,24,30\}$.

This can be futher optimized when programmed, for example instead of iterating over all subsets $R \subseteq Q$ we can backtrack whenever $\prod_{r \in R} (r-1) \mid k$ cannot be satisfied, and so on...

$\endgroup$
0
$\begingroup$

For smaller values of $k$ it might be feasible to match the prime decomposition of $k$ to the product formula for $\phi(n)$, and then go through the different possible cases. For example with $k = 12$ (Ex. 1(c) of Chapter 2 of "Introduction to Analytic Number Theory" by Tom M. Apostol) :

$n = 13$ is an obvious solution as $\phi(p) = p - 1$ for any prime $p$, and clearly any solution $n$ is $\geq 13$.

Consider $n = p_1^{a_1} \cdots p_k^{a_k}$, where $p_i$ are distinct primes with $p_1 < p_2 < \ldots < p_k$, and $a_i \geq 1$.

From the product formula for $\phi(n)$ : $$ \phi(n) = ( p_1^{a_1-1} \cdots p_k^{a_k-1} ) \cdot (\: (p_1-1) \cdots (p_k-1) \:) = m \cdot l \mbox{, say} $$

where every factor $(p_i - 1)$ is even, except possibly the first which is $1$ when $p_1 = 2$.

If $2 \nmid l$ then $k = 1$ and $p_1 = 2 \therefore n = 2^{a_1}$, therefore from the product formula for the totient function, $\phi(n) = n/2$. In the present case this implies $n = 24$, but $\phi(24) = 8$, so below we can assume $2 \mid l$.

Since we require $m \cdot l = 12 = 2^2 \cdot 3$ and $2 \mid l$, from the prime decompositions we must have one of the following possibilities :

  1. $m = 2 \cdot 3$, $l = 2$
  2. $m = 3$, $l = 2^2$
  3. $m = 2$, $l = 2 \cdot 3$
  4. $m = 1$, $l = 2^2 \cdot 3$

Case (i) $n$ even.

Then $p_1 = 2$. If $k = 1$ then $n$ is a power of $2$ but this cannot give $\phi(n) = 12$ as seen above. Thus assume $k \geq 2$.

Then, in the product $l$, the factor $(p_1 - 1) = 1$ and the distinct factors $(p_2 - 1), \cdots, (p_k - 1)$ are all divisible by $2$.

Case (1) $\Rightarrow k = 2$ and $p_2 = 3$, to achieve $l = 2$. Thus the primes of $n$ are $2$, $3$. Since $m = 2 \cdot 3$ we must have $a_1 = a_2 = 2$. Thus $n = 2^2 \cdot 3^2 = \mathbf{36}$.

Case (2) $\Rightarrow k \leq 3$, otherwise there would be too many $2$'s in $l$. But $k = 2 \Rightarrow p_2 = 5 \Rightarrow$ primes of $n$ are $2, 5$, but $m = 3 \Rightarrow$ $3$ a prime of $n \therefore$ contradiction. And $k = 3 \Rightarrow p_2 - 1 = p_3 - 1 = 2 \Rightarrow p_2 = p_3 \Rightarrow$ contradiction. Thus case (2) is not possible.

Case (3) $\Rightarrow$ there is only one $2$ in $l$ $\Rightarrow$ $k = 2$. Then to achieve $l = 2 \cdot 3$, $p_2 = 7 \therefore$ primes of $n$ are $2, 7$, and $m = 2 \Rightarrow a_1 = 2, a_2 = 1$. Thus $n = 2^2 \cdot 7 = \mathbf{28}$.

Case (4) $\Rightarrow k \leq 3$. $k = 2 \Rightarrow p_2 - 1 = l = 12 \therefore$ primes of $n$ are $2, 13$ and $m = 1 \Rightarrow a_1 = a_2 = 1 \therefore$ $n = 2 \cdot 13 = \mathbf{26}$. $k = 3 \Rightarrow (p_2 - 1)(p_3 - 1) = 2^2 \cdot 3$ with $2 \mid (p_2 - 1)$ and $2 \mid (p_3 - 1) \Rightarrow p_2 - 1 = 2 \cdot 3$ and $p_3 - 1 = 2$ (or vice-versa) $\Rightarrow$ since $p_2 < p_3$, $p_2 = 3$ and $p_3 = 7$. Thus the primes of $n$ are $2, 3, 7$ and $m = 1 \Rightarrow a_1 = a_2 = a_3 = 1 \therefore n = 2 \cdot 3 \cdot 7 = \mathbf{42}$.

Case (ii) $n$ odd.

Here all $p_i$'s are odd, $k \geq 1$, and every factor $(p_i - 1)$ is even.

Case (1) $\Rightarrow k = 1$ and $p_1 = 3$. But $m = 2 \cdot 3 \Rightarrow p_1^{a_1-1} = 2 \cdot 3$ which is even - a contradiction as $p_1$ odd. Thus case (1) is not possible.

Case (2) $\Rightarrow k \leq 2$. $k = 1 \Rightarrow p_1 = 5$. But $m = 3 \Rightarrow p_1^{a_1-1} = 3 \Rightarrow$ contradiction as $p_1 = 5$. $k = 2 \Rightarrow p_1 - 1 = p_2 - 1 = 2 \Rightarrow p_1 = p_2 \Rightarrow$ contradiction. Thus case (2) is not possible.

Case (3) $\Rightarrow k = 1$ and then $p_1 = 7$. But $m = 2 \Rightarrow p_1^{a_1-1} = 2 \Rightarrow$ contradiction as $p_1 = 7$. Thus case (3) is not possible.

Case (4) $\Rightarrow k \leq 2$. $k = 1 \Rightarrow p_1 = 13$. Then $m = 1 \Rightarrow a_1 = 1 \therefore n = \mathbf{13}$. $k = 2 \Rightarrow$ since $2 \mid (p_1 - 1)$ and $2 \mid (p_2 - 1)$, so $(p_1 - 1) = 2 \cdot 3$ and $(p_2 - 1) = 2$ (or vice-versa). But $p_1 < p_2 \therefore$ $p_1 = 3, p_2 = 7$, and $3, 7$ are the prime factors of $n$. Since $m = 1$, $a_1 = a_2 = 1 \therefore n = 3 \cdot 7 = \mathbf{21}$.

Thus the solution is $\{13, 21, 26, 28, 36, 42\}$.

$\endgroup$

You must log in to answer this question.

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