A possible Property of Euler's totient function: $n$ such that $\varphi(n)$ and $\varphi(n+1)$ are both powers of two

There are exactly seven odd positive integers $n$ such that

$\varphi(n)$ and $\varphi(n+1)$ are both powers of two.

These are: $$ n = 1, 3, 5, 15, 255, 65535, 4294967295. $$ Written out more helpfully: \begin{align*} 5&\; \\ 1&= 2^{2^0} - 1 \\ 3&= 2^{2^1} - 1 = 3\\ 15 &= 2^{2^2} - 1 = 3 \cdot 5 \\ 255 &= 2^{2^3} - 1 = 3 \cdot 5 \cdot 17 \\ 65535 &= 2^{2^4} - 1 = 3 \cdot 5 \cdot 17 \cdot 257 \\ 4294967295 &= 2^{2^5} - 1 = 3 \cdot 5 \cdot 17 \cdot 257 \cdot 65537. \end{align*} In particular, your conjecture is true: either $n+1 = 6$, or $n+1$ is a power of two. Specifically, $n+1$ is either $6$ or equal to $2^{2^k}$ for $k \in \{0,1,2,3,4,5\}$.

You may recognize $3, 5, 17, 257, 65537$ as the known Fermat primes. The reason there are no larger $n$ is that the next Fermat number, $4294967297$, is famously composite and equal to $641 \cdot 6700417$. (Though Fermat conjectured that all Fermat numbers are prime, other than the first five no other Fermat primes are known, and some have conjectured there are no others. See e.g. this oeis entry.)

Proof

First, we show that for a positive integer $m$, $\varphi(m)$ is a power of two if and only if $m$ is a power of two times a product of zero or more Fermat primes, i.e. primes of the form $2^{2^a} + 1$. (The same is found in Mathematician 42's answer.) Assume that $\varphi(m)$ is a power of two. If $m$ is divisible by the square of any prime $p$, then $p \mid \varphi(m)$ so $p = 2$. Therefore, $m$ is a power of two times some distinct odd primes $p_1 < p_2 < \cdots < p_i$: $$ m = 2^x p_1 p_2 \cdots p_i $$ Thus, $$ \varphi(m) = 2^{x-1} (p_1 - 1) (p_2 - 1) \cdots (p_i - 1), $$ and it follows that each $p_i$ must be a power of two plus 1. And the only prime numbers of the form $2^k + 1$ are of the form $2^{2^k} + 1$ (Fermat primes); a quick proof can be found in this section of the Wikipedia page. So $p_i$ is a Fermat prime. Conversely, any $m$ of this form has $\varphi(m)$ being a power of two.

Back to the problem, then, we are looking for all odd positive integers $n$ such that $n, n+1$ are both a power of two times a product of Fermat primes. As $n$ is odd, $n$ must be a product of Fermat primes, and $n+1$ must be a power of two times such a product. To reduce down to only seven possible $n$, we will exploit the fact that a product of Fermat primes has a very, very structured binary expansion.

Let $$ n = \prod_{i=1}^l (2^{2^{a_i}} + 1), $$ where $0 \le a_1 < a_2 < \cdots < a_l$ and each term of the product is prime. Expanding out the product, we get that $$ n = \sum_{S \subseteq \{1,2,3,\ldots, l\}} 2^{\displaystyle \left( \sum_{i \in S} 2^{a_i} \right)} $$ What this scary formula is saying is that: $n$ is the sum of $2^l$ distinct powers of two, and the exponents on those powers of two are all possible sums of $2^{a_1}, 2^{a_2}, \ldots, 2^{a_l}$. Thinking in binary:

  • $n$ has $2^l$ digits which are ones;

  • $n$ is odd, so the last digit is also a $1$.

  • And, importantly, if $l \ge 1$ then $n$ consists of two identical blocks: digits $0$ through $2^{a_l} - 1$ and $2^{a_l}$ through $2^{a_l+1}$ are the same. The block may start with some $0$s. (Within each of the two blocks we then have two more identical blocks, and so on, but there may be zeroes padded on at each step. Example: $(2^{2^0} + 1)(2^{2^1}+1)(2^{2^3}+1) = 3 \cdot 5 \cdot 257$ is $111100001111$ in binary. The two identical blocks are $00001111$ and $00001111$. Then each block consists of the two identical blocks $11$ and $11$, although four $0$s are padded on in front. Then each of those consists of two identical blocks $1$ and $1$.)

By the same reasoning, $n+1$ must be a power of two times a number that looks exactly the same. We can say that for some $r,m$ and $0 \le b_1 < b_2 < \ldots < b_m$, $n+1$ equals $2^r$ times the product of $2^{2^{b_i}} + 1$, and then:

  • $n+1$ has $2^m$ digits which are ones;

  • $\frac{n+1}{2^r}$ consists of two identical blocks: digits $0$ through $2^{b_m} - 1$ and $2^{b_m}$ through $2^{b_m + 1}$ are the same. (Within each of the two blocks we then have two more identical blocks, and so on.)

To form $n+1$ from $n$, we add $1$ to the binary expansion, so the number of $1$s decreases by $(c-1)$, where $c$ is the number of $1$s at the end of the binary expansion of $n$. As $n$ has $2^l$ ones, $n+1$ has $2^l - (c-1)$ ones. Since this has to be a power of two, we must either have $c = 1$ or $c \ge 2^{l-1}+1$. In the former case, we will show that $n$ must equal $5$. In the latter, that $n$ must equal $2^{2^l} - 1$.

Case 1: $c = 1$

Since $c = 1$, $n$ has $01$ at the end of its binary expansion. So $n+1$ has the same binary expansion with $01$ replaced by $10$, and $r = 1$ (number of twos dividing $n+1$). By looking at the $1$s in $n+1$, we may extract exactly the numbers $b_i$: the $2^i$th 1 from the right, if we start counting from 0, is at position $2^{b_i} + 1$ (where positions start counting from $0$ as well, i.e. the $k$th position is the $2^k$s digit). But it is also at position $2^{a_i}$. It follows that only $a_i = 1$ is possible, and $l = 1, m = 1$, $n = 2^{2^1} + 1 = 5$, $n+1 = 6 = 2 \cdot 3$.

Case 2: $c \ge 2^{l-1} + 1$

Here, $n$ must have at least $2^{l-1} + 1$ consecutive ones at the right. But $n$ consists of two identical blocks, each containing $2^{l-1}$ ones. So there must not be any zeroes in each block: $n$ must be a string of $2^{l}$ consecutive ones. That is, exactly, $$ n = 2^{2^l} - 1. $$ Now, this factors as $$ n = (2^{2^0} + 1) (2^{2^1} + 1) (2^{2^2} + 1) \cdots (2^{2^{l-1}} + 1). $$ For $l \le 5$, all of these factors are prime and we have a genuine solution.

But for $l \ge 6$, the factor $(2^{2^{5}} + 1)$ is present, and factors into $641 \cdot 6700417$, which makes $\varphi(n)$ divisible by $640$ and thus not a power of two.


This is not an answer, but might be useful when someone smarter than me tries to prove this.

Write $n=\prod_{i}p_i^{n_i}$ and $n+1=\prod_{i}(p_i')^{m_i}$. Then $\phi(n)=\prod_{i} p_i^{n_i-1}(p_i-1)$ being a power of two implies that if $p_i\neq 2$, then $n_i=1$ and $(p_i-1)$ is a power of two. The same holds for $\phi(n+1)$.

Let $I$ be an enumeration of the prime numbers such that the prime number minus one is a power of two, i.e. $0$ corresponds to $2$, $1$ corresponds to $5$, $2$ corresponds to $17$ and so on. Then $$n=2^{n_0}\prod_{i\in I, i\geq 1}p_i^{n_i}$$ where $n_i\in \left\{0,1\right\}$ and $$n+1=2^{m_0}\prod_{i\in I,i\geq 1}p_i^{m_i}$$ where $m_i\in \left\{0,1\right\}$. Here $p_i$ denotes the $i$-th prime number such that $p_i-1$ is a power of $2$ (and we start counting from zero). From this we get that $$2^{n_0}\prod_{i\in I, i\geq 1}p_i^{n_i}+1=2^{m_0}\prod_{i\in I, i\geq 1}p_i^{m_i}.$$

From this equation, we should be able to find something, however, I do not even know whether the index set $I$ is finite or not, making further manipulations difficult.

Tags:

Number Theory

Totient Function

Related

Greatest possible cardinality of a set of numbers less than 1000 such that the sums avoid powers of 2 Examples of problems that are easier in the infinite case than in the finite case. Hartshorne Lemma II.5.3 Proof Why aren't vacuous truths just undefined? Is saying a set is nowhere dense the same as saying a set has no interior? Is there a matrix of every size with all its submatrices invertible? Show that geodesic distance on the $n$-sphere respects the triangle inequality Simplified variant of Collatz conjecture. What's meaning of the inverted Greek letter iota “ι” in Principia Mathematica I* 14? The number of all 3-digit numbers abc for which abc + ab+bc + ac+a+b+c = 29 Logical proposition for "Every positive integer can be written as the sum of 2 squares" True or false: If $f(x)$ is continuous on $[0, 2]$ and $f(0)=f(2)$, then there exists a number $c\in [0, 1]$ such that $f(c) = f(c + 1)$.

Recent Posts