Phi-Pi-Po-Pum

First, any power of 2 is infinitely Euler since $\phi(2^{k+1}) = 2^k$ . Next, if $j, k > 0$ , then $m = 2^j 3^k$ is infinitely Euler since $\phi(2^j 3^{k+1}) = m$ .

We wish to prove that these are the only infinitely Euler numbers.

Let $\nu(m)$ denote the largest $k$ for which $2^k$ divides $m$ (e.g. $\nu(200) = 3$ ). Note that $\nu(mm') = \nu(m) + \nu(m')$ . The following result is critical.

$-$

Claim : For any positive integer $m$ which is not a power of 2, we have $\nu(\phi(m)) \ge \nu(m)$ ; equality holds if and only if $m = 2^k p^j$ for some prime $p \equiv 3\pmod 4$ and $j,k>0$ .

Proof : Write $m = 2^k n$ where $n>1$ is odd, so that $\phi(m) = \phi(2^k)\phi(n)$ and thus:

$\nu(\phi(m)) - \nu(m) = [\nu(\phi(2^k)) - \nu(2^k)] + [\nu(\phi(n)) - \nu(n)]$

Now the first summand on RHS is either 0 or -1 (it's -1 if and only if $k>0$ ). The second summand equals $\nu(\phi(n) )$ which is always positive since $n > 1$ . This proves the first statement. If equality holds, then the first summand must be -1, so $k>0$ , and the second summand satisfy $\nu(\phi(n)) = 1$ .

Recall that if $n = \prod_i p_i^{a_i}$ is the prime factorisation of $n$ , then $\phi(n) = \prod_i (p_i-1)p_i^{a_i-1}$ . Hence, $\nu(\phi(n)) = 1$ if and only if there's only one prime factor $p_i$ and $p_i -1$ only contributes a single factor of 2 to the product, i.e. $n = p^j$ where $p \equiv 3 \pmod 4$ . (QED)

$-$

Now suppose $m$ is infinitely Euler, where $m$ is not a power of 2, and $m_1, m_2, m_3,\ldots$ are such that:

• $m_1 = m, \ m_i = \phi(m_{i+1})$ for all $i \ge 1$ .

Since $m_1$ is not a power of 2, neither is any $m_i$ . Hence, by the above claim, $\nu(m_i)$ is a (non-strictly) decreasing sequence so it must be eventually constant:

$\nu(m_N) = \nu(m_{N+1}) = \nu(m_{N+2}) = \ldots = k$

for some $N$ . By the claim, it follows that $m_{N+1}, m_{N+2}, \ldots$ are all of the form $2^k p^j$ , for some odd prime $p\equiv 3 \pmod 4$ . But

$\phi(2^k p^j) = 2^k \frac{p-1} 2 p^{j-1}$

so if $p > 3$ then $\frac {p-1} 2$ is an odd number > 1. This means $\phi(2^k p^j)$ cannot be of the form $2^k p^j$ except when $j=1$ . Thus, $m_{N+2}, m_{N+3}, \ldots$ are all of the form $2^k p$ where $p\equiv 3\pmod 4$ . Writing $m_i = 2^k p_i$ , we must have $p_{i+1} = 2p_i + 1$ . However, clearly $p_i$ cannot be all prime since:

• $p_i \equiv 1 \pmod 3\implies 3|p_{i+1}$ and $p_{i+1}>3$ , and
• $p_i \equiv 2 \pmod 3\implies 3|p_{i+2}$ and $p_{i+2}>3$ .

$-$

Conclusion

Hence, the infinitely Euler numbers less than 1000 are:

• $2^0, 2^1, \ldots, 2^9$ : 10 numbers;
• $3\times 2, 3\times 2^2, \ldots, 3\times 2^8$ : 8 numbers;
• $3^2\times 2, \ldots, 3^2\times 2^6$ : 6 numbers;
• $3^3\times 2, \ldots, 3^3\times 2^5$ : 5 numbers;
• $3^4\times 2, \ldots, 3^4\times 2^3$ : 3 numbers;
• $3^5\times 2, 3^5\times 2^2$ : 2 numbers.

And the answer is $\fbox{34}$ .

Since $\varphi(2^a) \,=\, 2^{a-1}$ for any integer $a \ge 1$ , we deduce that $2^a$ is infinitely Euler for any integer $a \ge 0$ , since we can set $m_j \; = \; 2^{a+j-1} \qquad \qquad j \ge 1 \;.$ Since $\varphi(2^a3^b) \,=\, 2^a3^{b-1}$ for any integers $a,b \ge 1$ , we deduce that $2^a3^b$ is infinitely Euler for all integers $a,b \ge 1$ , since we can set $m_j \; = \; 2^a 3^{b+j-1} \qquad \qquad j \ge 1 \;.$ I claim that all infinitely Euler numbers are of one of these two forms. Suppose instead that $m$ is infinitely Euler, but that $m$ is not of one of these two types. We can find integers $m_j$ for all $j\ge 1$ such that $m_1=m$ and $m_j \,=\, \varphi(m_{j+1})$ for all $j\ge 1$ . If any of the integers $m_j$ (which must themselves be infinitely Euler) were of either of the two types, then so would $m$ be, so we deduce that none of the integers $m_j$ are of either of the two types. Note that $m_j$ is even for all $j \ge1$ . Let $a_j \ge 1$ be the index of $2$ in $m_j$ , so that $m_j \,=\, 2^{a_j}\mu_j$ for all $j \ge 1$ , where $a_j \ge 1$ and $\mu_j \ge 3$ is odd, but not equal to a power of $3$ . Then we deduce that $2^{a_j}\mu_j \; = \; m_j \; = \; \varphi(m_{j+1}) \; = \; 2^{a_{j+1}-1}\varphi(\mu_{j+1})$ Since $\varphi(\mu_{j+1})$ is even, we deduce that $a_j \ge a_{j+1}$ for all $j \ge 1$ .

Thus $\big(a_j\big)_j$ is a decreasing sequence of positive integers, and hence there must exist some $J \ge 1$ such that $a_j \,=\, a_J$ for all $j \ge J$ . This implies that $\varphi(\mu_{j+1}) \,=\, 2\mu_j$ for all $j \ge J$ . For any $j \ge J+1$ , $\varphi(\mu_j)$ has just one factor of $2$ , and so $\mu_j$ must be a power $p_j^{x_j}$ of a single odd prime $p_j$ , where $p_j \equiv 3$ modulo $4$ . Since $\mu_j$ is not a power of $3$ , we deduce that $p_j > 3$ , and hence $p_j \ge 7$ . Now $2p_j^{x_j} \; = \; 2\mu_j \; = \; \varphi(\mu_{j+1}) \; = \; p_{j+1}^{x_{j+1}-1}(p_{j+1}-1) \qquad j \ge J+1$ Now $\tfrac12(p_{j+1}-1)$ is odd and at least $3$ , and so has a prime factor which must be distinct from $p_{j+1}$ . Since $2p_j^{x_j}$ has exactly one odd prime factor, we deduce that $x_{j+1} = 1$ for all $j \ge J+1$ , and that $p_{j+1} \,=\, 1 + 2p_j^{x_j}$ for all $j \ge J+1$ . Hence we deduce that $p_{j+1} \,=\,1 + 2p_j$ for all $j \ge J+2$ . Thus we deduce that $p_{J+2+k} = 2^k(p_{J+2} + 1) - 1$ for all $k \ge 0$ . But if $k \ge 1$ is such that $2^k \equiv 1$ modulo $p_{J+2}$ , we deduce that $p_{J+2}$ divides $p_{J+k+2}$ . But $p_{J+k+2}$ is clearly bigger than $p_{J+2}$ . We have reached a contradiction, and hence there are no infinitely Euler numbers except those of the two types given above.

There are $34$ numbers of these two forms between $1$ and $1000$ , namely $\begin{array}{cccccccccc} 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 \\ 6 & 12 & 24 & 48 & 96 & 192 & 384 & 768 & 18 & 36 \\ 72 & 144 & 288 & 576 & 54 & 108 & 216 & 432 & 864 & 162 \\ 324 & 648 & 486 & 972 \end{array}$

The rules for the totient function are: $\begin{aligned}\phi(mn) &= \phi(m) \phi(n) \mbox{ for m,n coprime} \\ \phi(p^a) &= p^{a-1}(p-1) \mbox{ for p prime, }a \gt 0 \end{aligned}$

From this we get: $\phi(2^a) = 2^{a-1}, \mbox{ for }a \ge 0$ therefore $2^a$ is infinitely Euler. Also,

$\phi(2^a3^b) = 2^a3^{b-1}, \mbox{ for }a \ge 0, b \ge 1$ therefore $2^a3^b$ is infinitely Euler.

Other numbers must include a power of a higher prime. For example consider $m_1 = 2^a5$ In order for $\phi(x)$ to contain a factor of $5$ , we see from the rules given above that $x$ must contain a factor of $5^2$ . However, if $m_2 = 2^a5^bn$ for some $n$ coprime to $2,5$ , then $\phi(m_2) = 2^{a+1}5^{b-1} \phi(n)$ So $m_1$ has more factors of $2$ than $m_2$ . By induction then, $m_1$ cannot be infinitely Euler as eventually we must run out of factors of $2$ , but $2 \vert \phi(n)$ for all $n > 1$ .

Similarly, if $m_1$ contains a factor of $7^b$ then $m_2$ must contain a factor of $7^{b+1}$ . But $\phi(7^{b+1}) = 2\cdot3\cdot 7^b$ . By similar reasoning to the previous case, $m_1$ must have a greater number of factors of $2$ and $3$ combined than $m_2$ does, so it cannot be infinitely Euler.

All odd primes greater than $3$ must have $p-1$ being a product of at least two smaller primes, so the same reasoning as the above cases applies. The multiplicative rule lets us break down more complicated cases into supersets of the above cases. So there are actually no more infinitely Euler numbers.

Enumerating the cases given above: $1\\ 2, 6, 18, 54, 162, 486 \\ 4, 12, 36, 108, 324, 972 \\ 8, 24, 72, 216, 648 \\ 16, 48, 144, 432 \\ 32, 96, 288, 864 \\ 64, 192, 576 \\ 128, 384 \\ 256, 768 \\ 512$ for a total of $\boxed{34}$ .

For an integer $n = p_1^{a_1} p_2^{a_2}...p_x^{a_x}$ , we define $\phi^{-1} (n) = \frac{n}{(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_x})}$

$= \frac{p_1^{a_1+1} p_2^{a_2+1}...p_x^{a_x+1}}{(p_1-1)(p_2-1)...(p_x-1)}$

For this to be an integer, the denominator must divide numerator. Also note that primes contained in denominator are also contained in the numerator, since all of them are $p_i<p_x$ .

So we may write : $\phi^{-1} (n) =p_1^{a_1-r_1+1} p_2^{a_2-r_2+1}...p_x^{a_x-r_x+1}$ for some $r_i \geq 0$ . Following 3 conclusions are important:

• No prime powers (except those of 2) are infinitely Euler. Obvious since $\phi^{-1}(p^{\alpha}) = \frac{p^{\alpha+1}}{p-1}$ but $p$ & $(p-1)$ are coprime.

• $p_1 = 2$ . (Consider not, then the numerator is odd, & denominator even, contradiction.)

• $r_1 \leq 1$ . Suppose $r_1 > 1$ , then power of 2 decreases at each step of using $\phi^{-1}$ & at some stage it would become 0,then no more $m_{i+1}$ can be obtained, contradicting the infinite sequence condition. In more rigorous words, if $r_1 > 1$ , then $a_1$ of ${m_i} < a_1$ of $m_{i+1}$ but this sequence is non-negative & cannot decrease indefinitely.

Now $r_1 = 0 \Rightarrow n$ is a power of $2$ , yielding cases: $m = 2^0,2^1,...,2^9$ ie 10 cases.

Again $r_1 = 1 \Rightarrow$ there is/are another prime/s $p_k$ whose $(p-1)$ contains $2^1$ . There can be atmost 1 such more prime since if there are 2 primes,their $(p_k-1)$ contains more than just $2^1$ . Also the other prime must be $3$ , as only $(3-1)$ contains $2^1$ . So these $m$ are of form $2^i 3^j$ [ $i,j \geq 1$ ] which are 24 in number $<1000$ .

Thus there are total 34 infinitely Euler numbers. (Exotic problem!)