3
$\begingroup$

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.

$\endgroup$
3
  • 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$ Commented Jun 24, 2016 at 7:52
  • 2
    $\begingroup$ Such $n$ (if any) should be pseudoprime to base 2. $\endgroup$ Commented Jun 24, 2016 at 8:33
  • $\begingroup$ How did @IvanNeretin proved this? $\endgroup$
    – user1115547
    Commented Jan 19, 2023 at 14:33

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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