# find all the $n$ such that $\phi(n) , \phi(n+1) , \phi(n+2)$ are powers of 2

Find all the natural numbers such that, the regular $n , n+1 , n+2$ gons are constructible.

Well this problem can be restated in the following way. Since the construction of the regular n-gon is equivalent to the construction of the primitive root $e^{\frac{2\pi i}{n}}$ , and we know that the degree of this extension over $\Bbb Q$ is $\phi(n)$ , and also knowing that a number is constructible iff it's degree over $\Bbb Q$ is $2^k$ we want all the natural numbers $n$ such that $\phi(n) , \phi(n+1) , \phi(n+2)$ are powers of 2. I have no idea how can I do this :S, I only know properties of $\phi(n)$ involving products of coprimes. But here ...

-
Solved - see my updated answer. Nice problem! – Alon Amit Nov 24 '12 at 6:15

We have $\varphi(a)$ is a power of $2$ iff $a$ is a power of $2$ times a product of distinct Fermat primes. Since the only currently known Fermat primes are $3$, $5$, $17$, $257$, and $65537$, there is only a short list of current possibilities to examine. The largest obvious triple is $(65535,65536,65537)$.

It is likely that one can show that there are no additional triples, without trying to settle any open problem about the number of Fermat primes.

We definitely cannot have any more examples of shape $2^{2^n}-1,2^{2^n}, 2^{2^n}+1$ beside the obvious ones. The fact that $F_5$ is not prime settles the case $n=5$. And if $n \gt 5$, then among the factors of $2^{2^n}-1$ we find the Fermat number $F_5$, which is not prime. There also cannot be examples of shape $2^{2^n},2^{2^n}+1, 2^{2^n}+2$ beside $n=0$ and $n=1$. For elementary considerations of size show that $2^{2^n-1}+1$ cannot be a product of distinct Fermat primes if $n \gt 1$.

-
Well yes , we don't know if it exist more of such numbers , but in this case is something particular, finding 3 consecutives, so maybe this case can be proved :C – Daniel Nov 21 '12 at 6:58

Let us call a number $N$ constructible if a regular $N$-gon can be constructed with straightedge and compass. As you know, this is equivalent to $\varphi(N)$ being a power of $2$, and equivalently $N$ is of the form $N=2^kF_{m_1}F_{m_2}\cdots F_{m_r}$ where $F_m=2^{2^m}+1$ is a Fermat number, the $m_i$ are all distinct and moreover each $F_{m_i}$ is prime. We interpret the product of the $F_{m_i}$'s as $1$ if $r=0$.

Let $b(N)$ be the number of $1$'s in the binary representation of $N$. Thus $b(15)=4$, $b(16)=1$. First of all, show:

1) $b(F_{m_1}\cdots F_{m_r}) = 2^r$.

This is so because when you expand the product $(2^{2^{m_1}}+1)(2^{2^{m_2}}+1)\cdots(2^{2^{m_r}}+1)$, the powers of $2$ don't "mix": Numbers of the form $2^{m_{i_1}}+2^{m_{i_2}}+\cdots+2^{m_{i_p}}$ are all distinct, so each term in the expanded product contributes precisely one $1$ to the binary representation of the result.

Now conclude:

2) If $N$ is even and both $N$ and $N+1$ are constructible, then $N=2^{2^m}$ for some $m$ and $N+1$ is a Fermat prime.

Proof: Since $N$ is even, $b(N+1)=b(N)+1$. By part 1) above we have $b(N)=2^r$ for some $r$ and $b(N+1)=2^s$ for some $s$. But the only way for $2^s=2^r+1$ to happen is if $r=0$ and $s=1$. Thus $N$ is a power of $2$ and $N+1$ is a constructible number of the form $F_m$, which necessitates that it's a Fermat prime and $N=2^{2^m}$.

We don't know how many $N$'s there are with this property, since we don't know how many Fermat primes exist. However, adding the requirement that $N-1$ is also constructible restricts the options enough for the problem to be solvable.

3) If $N$ is even and both $N-1$ and $N+1$ are constructible, then $N=2^{2^m}$ with $0 \leq m \leq 4$.

Proof: We already know that $N=2^{2^m}$ for some $m$. But now

$N-1 = 2^{2^m}-1 = F_0F_1\cdots F_{m-1}$ (proof: induction, or expand the product)

and for that to be constructible, each $F_k$ must be prime for $0 \leq k \leq m-1$. This works fine for $0 \leq m \leq 5$ but ceases to work afterwards since $F_5$ isn't prime, and for the same reason $m=5$ fails to ensure that $N+1$ is constructible. Thus the only possible values of $m$ are $0 \leq m \leq 4$.

Finally, we need to check triplets $(N-1,N,N+1)$ where $N$ is odd. This means that $N-1,N$ are now a power of 2 and a Fermat prime, respectively, with the additional requirement that $N+1$ is also constructible. I'll leave this as an exercise :-) The only possible cases are $N=3$ and $N=5$.

So finally, the list of constructible triplets is:

$(1,2,3)$, $(2,3,4)$, $(3,4,5)$, $(4,5,6)$, $(15,16,17)$, $(255,256,257)$, $(65535,65536,65537)$.

-