Return to Answer

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).$$ Hence 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$.

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$.

For any $k\geq 1$, there are infinitely many solutions of the congruence $2^{n+k}\equiv 1\pmod{n}$. To see this, we observe first that there is always a solution $n$ such that $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).$$ Hence it suffices to show that, for any fixed $k$ and for any solution $n$ 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$.

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).$$ Hence 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$.

Here is a proof that any $k\geq 6$ works. Fix any $k\geq 6$, and consider the solutions of $2^{n+k}\equiv 1\pmod{n}$, including the trivial solution $n=1$. We claim that for any solution $n$ there is a bigger solution. Indeed, let $n\geq 1$ be any solution, and 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, $pn$ is a solution (bigger than $n$).

The remaining cases $1\leq k\leq 5$ probably follow along similar lines, by exhibiting first a solution $n$ such that $n+k\geq 7$. For example, for $n=15$ is such a solution for $k=1$, confirming the OP's claim that $k=1$ works.

For any $k\geq 1$, there are infinitely many solutions of the congruence $2^{n+k}\equiv 1\pmod{n}$. To see this, we observe first that there is always a solution $n$ such that $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).$$ Hence it suffices to show that, for any fixed $k$ and for any solution $n$ 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$.