11
$\begingroup$

$n$ is an odd positive integer such that $\varphi(n)$ and $\varphi(n+1)$ are both powers of two . Here , $\varphi(n)$ denotes Euler's totient function.

Is it true that $(n+1)$ is either $6$ or a power of $2$?

Please help me to prove or disprove this statement . (I was randomly flipping through some values attained by the $\varphi$ function when I observed this pattern) :)

$\endgroup$
  • 3
    $\begingroup$ If $n$ is a Fermat prime (of the form $2^{2^k}+1$) then certainly both $\phi(n)$ and $\phi(n-1)$ will be powers of $2$. Other than that, after checking up to about $35000$ , I can't find any other $n$. $\endgroup$ – florence Aug 9 '16 at 9:52
  • 1
    $\begingroup$ The conjecture is true, and moreover there are finitely many possible $n$. I am writing an answer now. $\endgroup$ – 6005 Aug 9 '16 at 10:27
  • $\begingroup$ @ above , can you please provide a link / reference or the answer ? $\endgroup$ – John Aug 9 '16 at 11:20
  • 1
    $\begingroup$ @florence: Your statement applies for even $n$ such that $\phi(n)$ and $\phi(n+1)$ are powers of two, but the question is about odd $n$. But the answer still involves Fermat primes. $\endgroup$ – 6005 Aug 9 '16 at 12:43
16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This answer deserves many upvotes. Brilliant answer, especially the formula for $n$ in terms of power of $2$ is very elegant. Also the OP has done a good job in finding this pattern. $\endgroup$ – Mathematician 42 Aug 9 '16 at 12:51
  • $\begingroup$ @Mathematician42 Thanks :) Yes, this simple pattern found by the OP turned out to be very cool. $\endgroup$ – 6005 Aug 9 '16 at 19:15
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is it helpful to work in binary ? $\endgroup$ – John Aug 9 '16 at 10:14
  • 1
    $\begingroup$ Not sure whether that would help. I'd like to remark that since $n$ is odd, $n_0=0$, further simplifying the equations. I'm curious to see a proof of this fact. $\endgroup$ – Mathematician 42 Aug 9 '16 at 11:16
  • 1
    $\begingroup$ +1, This answer goes in the right direction. The primes in question (indexed by $I$) are Fermat primes, $2^{2^k} + 1$ for $k = 0, 1, 2, 3, 4$: that is, $3, 5, 17, 257, 65537$, and no others are known, and it is conjectured these are the only ones. However, even without knowing whether $I$ is finite or not once you know that $n$ is a product of these special primes its binary expansion is of a very specific form and you can exploit this to get down to just 7 possible $n$. This is explained in my answer. $\endgroup$ – 6005 Aug 9 '16 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.