9
$\begingroup$

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?

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

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

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ – Henri Cohen Dec 19 '17 at 22:35
8
$\begingroup$

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

$\endgroup$
6
  • 4
    $\begingroup$ In addition to being odd, $n$ must be co-prime with $3$, right? $\endgroup$ – Seva Dec 19 '17 at 19:03
  • $\begingroup$ no, wrong. n odd is sufficient $2^2\equiv1\pmod{3}$. $\endgroup$ – Henri Cohen Dec 19 '17 at 19:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Seva Dec 19 '17 at 19:33
  • 2
    $\begingroup$ But it does imply $K^{3} \equiv 1 (\mod 3n)$. $\endgroup$ – Robert Israel Dec 19 '17 at 20:21
  • $\begingroup$ @RobertIsrael: I see, it does work this way. $\endgroup$ – Seva Dec 19 '17 at 20:50

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.