Are there any composite integers $n$ such that ALL factors of $2^n-1$ $\equiv$ $1$$\pmod n$. (In other words, every prime factor dividing $2^n-1$ has the form $2kn+1$) It seems unlikely that there would be an integer $n$, not prime satisfying the case above, but I can't exactly show that's the case. A little help here? Thanks.

Can any examples can be constructed? So far, $n$ is not a multiple of $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, or $23$ as I checked. One method, unsure if practical, is to take the Mersenne Number $2^n-1$ with $n$ prime and check divisors $q_x$ of the form $2kn+1$, then check that the $\gcd$ of $k_1$, $k_2$, $k_3$......... $k_x$ is $m$ $≠$ $1$. From there check prime factors $p$ of $m$ and all divisors of $2^p-1$ and check that the divisors have the form $2knp+1$ (If this holds for all prime divisors $p$ of $m$, then all prime factors $2^m-1$ should have the form $2km+1$ or congruent to $1$ $\pmod m$ and $m$ is composite. I have no other clues on how one can be constructed besides this way.

  • 2
    $\begingroup$ $2^4-1=3\cdot5$ has a prime factor $3\not\equiv1\pmod4$. If $n$ is an odd prime, then all prime factors $p$ of $2^n-1$ are congruent to $1\pmod n$, because $2$ is then of order $n$ modulo $p$, and Lagrange's theorem kicks in. See also this question. $\endgroup$ – Jyrki Lahtonen Jun 24 '16 at 7:52
  • 1
    $\begingroup$ Such $n$ (if any) should be pseudoprime to base 2. $\endgroup$ – Ivan Neretin Jun 24 '16 at 8:33

Let $n$ be even. Then $3\mid 2^n-1$, see this MSE question. Since $3\not\equiv 1\bmod n $ for $n\ge 3$ we are done for $n$ even. For $n$ odd, and composed, I do not see an easy argument. Most of the time, $2^{2m+1}-1$ has a "small" prime divisor $p<n=2m+1$, which then is not congruent to $1$ modulo $n$. In general, however, it is not true, that $2^n-1$ in this case has always a prime factor $p$ with $p<n$, take $n=25$. Then $2^{25}-1=31\cdot 601\cdot 1801$. On the other hand we also have $31\not\equiv 1 \bmod 25$.

Edit: I also tested a few pseudoprimes to base $2$ for small prime divisors, see Ivan's remark. Some examples: $$ 23\mid 2^{341}-1,\; 7\mid 2^{561}-1,\;7\mid 2^{654}-1,\; 31\mid 2^{1105}-1. $$


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.