# For which values of $k$ is it known that there are infinitely many $n$, such that $2^{n+k}\equiv 1\pmod{n}$?

I know that there are no solutions to $2^n\equiv 1\pmod{n}$ for $n>1$ and I can prove that there are infinitely many $n$ such that $2^{n+1}\equiv1\pmod{n}$.
My question is:

Do we know other fixed values $k\in \mathbb{N}$ such that $2^{n+k}\equiv 1\pmod{n}$ holds infinitely often?

• I believe any odd $k$ works, but I don't have a reference nor a proof at hand. – Henri Cohen Dec 19 '17 at 18:13
• Any $k\geq 1$ works, see my proof below. – GH from MO Dec 19 '17 at 22:13

## 2 Answers

For any $k\geq 1$, there are infinitely many solutions of the congruence $2^{n+k}\equiv 1\pmod{n}$. To see this, observe first that there is always a solution $n\geq 1$ satisfying $n+k\geq 7$. Indeed, for $k\geq 6$ this is verified by the trivial solution $n=1$, while for $1\leq k\leq 5$ it is verified by the pairs $$(k,n) \ = \ (1,15),\ \ (2,7),\ \ (3,5),\ \ (4,31),\ \ (5,3).$$ Now it suffices to show that, for any fixed $k$ and for any solution $n\geq 1$ satisfying $n+k\geq 7$, there is a bigger solution $n'>n$ for the same $k$. Indeed, let $p$ be a primitive prime divisor of $2^{n+k}-1$, which exists by Zsigmondy's theorem. Then, the order of $2$ modulo $p$ equals $n+k$, whence $n+k\mid p-1$. This implies that $pn+k=(p-1)n+(n+k)$ is divisible by $n+k$, hence $$p,n\mid 2^{n+k}-1\mid 2^{pn+k}-1.$$ However, $p>n+k>n$, so $p$ and $n$ are coprime, and the above implies that $pn\mid 2^{pn+k}-1$. That is, $n'=pn$ is a solution bigger than $n$.

• Very nice proof. My suspicion that it was true only for odd k came from experimentation: for instance for $k=6$, the first is $n=127$, then $n=3263257$, but by pushing further I found a few more. – Henri Cohen Dec 19 '17 at 22:35

Sorry, this is in fact trivial. For instance if $2^{n+1}\equiv1\pmod{n}$ then $n$ is of course odd, so $2^{3n+3}\equiv1\pmod{n}$ and mod $3$, so $2^{3n+3}\equiv1\pmod{3n}$. This probably works for all odd $k$ not only $3$.

• In addition to being odd, $n$ must be co-prime with $3$, right? – Seva Dec 19 '17 at 19:03
• no, wrong. n odd is sufficient $2^2\equiv1\pmod{3}$. – Henri Cohen Dec 19 '17 at 19:26
• I certainly agree that $2^2\equiv1\pmod 3$, but if $3\mid n$, then $K\equiv 1\pmod n$ and $K\equiv 1\pmod 3$ do not imply $K\equiv 1\pmod{3n}$ - at least in the absence of other information. – Seva Dec 19 '17 at 19:33
• But it does imply $K^{3} \equiv 1 (\mod 3n)$. – Robert Israel Dec 19 '17 at 20:21
• @RobertIsrael: I see, it does work this way. – Seva Dec 19 '17 at 20:50