2
$\begingroup$

In 1999, Ford proved that for every $k\ge2$, there exists $m$ such that $\phi(n) = m$ has exactly $k$ solutions. Here, $\phi$ is the Euler totient function which counts the number of integers relatively prime to $n$. However, it remained an open question that does there exist $m$ for which $k=1$. Carl Pomerance, Kevin Ford, Victor Klee and many others have worked on providing the upper and lower bounds for the failure of conjecture and the conditions under which the conjecture cannot be true. In the following script on the stack, while doing some hand work, I've found the following conclusion based on observations from numerical computations. I am not able to prove the conclusion and any help on the same would be of worth to me.

Observation : If $m = 2^{j},$ $\phi(n) = m$ has exactly $j+2$ solutions.

Validating the observation : The observation is validated using the following data from oeis, (https://oeis.org/A014197/b014197.txt). For example if $m = 2^{2}$, number of solutions to $\phi(n) = 2^2$ are $2+2 = 4$. Another example is if $m = 2^{12}$, number of solutions to $\phi(n) = 2^{12}$ are $12+2 = 14$.

At present, I don't have much idea on proving this observation. I would be thankful stack community provides some insight on the same.

$\endgroup$
18
  • 2
    $\begingroup$ Your first sentence ... shouldn't it be something like, for every $k\ge2$ there exists $m$ such that $\phi(n)=m$ has exactly $k$ solutions? $\endgroup$ Oct 2, 2021 at 7:49
  • 2
    $\begingroup$ Note that if $\phi(m)$ is a power of two, then $m$ must be a power of two times a product of distinct Fermat primes. There are only five known Fermat primes – there may only be five Fermat primes – so it shouldn't be hard to get an exact answer for the number of preimages of any given power of two. $\endgroup$ Oct 2, 2021 at 7:53
  • 1
    $\begingroup$ I think such solutions $n$ are integers for which the regular $n$-gon is constructible with ruler and straightedge. Maybe your pattern fails when you come to a composite Fermat number, namely $F_5=2^{32}+1$ is composite and not a solution to $\phi(n)=2^{32}$. $\endgroup$ Oct 2, 2021 at 7:55
  • 2
    $\begingroup$ Theorem The number of solutions to $\phi(n)=2^j$ is equal to $j+2$ for $j\le 31$, and equal to $32$ for $j\ge 32$. $\endgroup$ Oct 2, 2021 at 8:12
  • 2
    $\begingroup$ Wait, we cannot prove the theorem if we cannot prove that all Fermat numbers $F_m=2^{2^m}+1$ with $m\ge 5$ are composite. $\endgroup$ Oct 2, 2021 at 8:16

2 Answers 2

3
$\begingroup$

From the formula for $\phi$, it is clear enough that if $\phi(n)$ is to be a power of two, then all primes that divide $n$ must be one greater than a power of two. The special prime $2$ can occur in any multiplicity $2^k$ in the factorization of $n$, while the odd primes must be Fermat primes, and each can only occur once (to the first power).

(Note that Gauss discovered that for such $n$ it is possible to construct the regular $n$-gon with compass and straightedge. He knew that for $n$ not of this type, it was impossible, and this part was proved by Wantzel.)

The only known odd primes that are one greater than a power of two, are $3,5,17,257,65537$. Therefore, the only known odd numbers whose totient is a power of two, are the thirty-two positive divisors of $3\cdot 5\cdot 17\cdot 257\cdot 65537$. Each such number can be multiplied by two raised to any power to get even numbers whose totient is a power of two.

It is left as an exercise to count how many of all these numbers $n$ are mapped by $\phi$ to each value $2^j$. Note that if $n$ is the odd part, then both $n$ and $2n$ share the same totient, while the subsequent doublings $2^2n,2^3n,2^4n,\ldots$ correspond to doublings of the totient values.

The result of the exercise, is that the number of solutions to the equation $\phi(n)=2^j$ for $j=0,1,2,\ldots$ is:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 32, 32, 32, 32, 32, ...

We can denote the $j$th term of this sequence $a(j)$. Then under the hypothesis that no more Fermat primes exist we have: $$a(j)=\begin{cases}j+2 & \text{for }0\le j<32 \\ 32 & \text{for }j\ge 32\end{cases}$$ The first Fermat number whose primality is still unknown, is $F_{33}=2^{8589934592}+1$. Consequently, the first $a(j)$ which is unknown is $a(8589934592)$. We have $a(8589934592)=32$ if $F_{33}$ is composite, or $a(8589934592)=34$ in the unlikely case $F_{33}$ is prime.

I think I should submit $a(j)$ to OEIS. Edit: The sequence was already in OEIS but I had trouble locating it because its data was temporarily incorrect. That is now fixed; see A058321.

$\endgroup$
4
  • $\begingroup$ Sure, you may submit $a(j)$ to OEIS, but would be thankful if you cite the question posted here. $\endgroup$
    – Aziz
    Oct 2, 2021 at 20:53
  • $\begingroup$ How come 33?, it is probably typo error. $\endgroup$
    – Aziz
    Oct 2, 2021 at 20:58
  • $\begingroup$ Argh, I could not find it in OEIS because someone else had also thought 33 was a typo. It is no typo. $a(31)=33$ and the 33 solutions are: 4294967295, 4294967296, 4295032832, 4311744512, 4311810304, 4563402752, 4563472384, 4581228544, 4581298448, 5368709120, 5368791040, 5389680640, 5389762880, 5704253440, 5704340480, 5726535680, 5726623060, 6442450944, 6442549248, 6467616768, 6467715456, 6845104128, 6845208576, 6871842816, 6871947672, 8053063680, 8053186560, 8084520960, 8084644320, 8556380160, 8556510720, 8589803520, 8589934590 The first one is odd, and the last one is twice the first one. $\endgroup$ Oct 2, 2021 at 21:09
  • $\begingroup$ Sorry Jeppe, my bad. You are correct. $\endgroup$
    – Aziz
    Oct 3, 2021 at 4:06
0
$\begingroup$

I must try to end this discussion with a proper base, by citing the following article in which the complete account of image of Euler totient function is provided.

The discussions done through comments and answers on the stack community are found to be exact and up to the mark.

The complete formulation for the discussion done through comments is given in the article attached with this answer.

I am thankful to people who have spent their valuable time in answering and discussing on the question posed on this platform.

Article:-https://arxiv.org/abs/0910.2223

$\endgroup$

You must log in to answer this question.

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