I'm stuck at the following question: let $d$ divide $2^{2^n} +1 $. Show that $d \equiv 1 \pmod{2^{n+1}}$.

All I've managed to do so far was to notice that $2^{n+1} \mid 2^{2^n}$ for every natural $n$, so if $dl = 2^{2^n} + 1$, we have $dl \equiv 1 \pmod{2^{n+1}}$ - which merely states that $d$ is invertible, which is trivial since it is odd. This is homework, are there any hints?

  • 1
    $\begingroup$ We can actually show that $d\equiv1\pmod{2^{n+2}}$ if $n\ge2$. See here or here (and possibly elsewhere) for earlier incarnations. $\endgroup$ Jan 20, 2017 at 18:00

1 Answer 1


Suppose prime $\,p\mid d.\ $ ${\rm mod}\ p\!:\,\ 2^{\large 2^{\Large n}}\!\equiv -1\,\overset{\rm square}\Longrightarrow\, 2^{\large 2^{\Large n+1}}\!\equiv 1\ $ so by the Order Test we deduce that $\,2\,$ has order $\,2^{\large n+1}.\,$ By Fermat $\,2^{\large p-1}\!\equiv 1\,$ so $\,2^{\large n+1}\!\mid p\!-\!1,\,$ Thus since each prime $\,p_i\,$ dividing $\,d\,$ satisfies $\,\color{#c00}{p_i\equiv \bf 1}\pmod{\!2^{\large n+1}}\,$ so too their product $\,d = \prod \color{#c00}{p_i}^{\large k_i}\!\equiv\prod \color{#c00}{\bf 1}^{\large k_i}\!\equiv 1\pmod{\!2^{\large n+1}}$


You must log in to answer this question.

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