Let $x$ be a positive integer such that $(2^{x}-1)=pq$ , where $p$ and $q$ are prime numbers.
I want to show that either $p^{2} \bmod x \equiv 1$ or $q^{2} \bmod x \equiv 1$ (or both of course).

Is there a simple way of proving this conjecture?


Yes, there is a simple way.

First, we show $x$ has to be prime or the square of a prime. Suppose it were not, then $x=ab$ for some integers $a\neq b$ with $2\leq a\leq b$.

Then $2^a-1$ and $2^b-1$ are two different non-trivial divisors of $2^x-1$, and thus equal to $p$ and $q$.

We would have $(2^a-1)(2^b-1)=2^{ab}-1$, but as $2\leq a\leq b$, $$(2^a-1)(2^b-1)=2^{a+b}-2^a-2^b+1<2^{a+b}-1\leq2^{ab}-1,$$ a contradiction.

If $x$ is prime, then $\mbox{ord}_p(2)=x$, so $x\mid p-1$ and the conclusion follows.

Consider $x=r^2$, the square of a prime. We then have $p=2^r-1$ and $q=\frac{2^{r^2}-1}{2^r-1}$. This gives $$(2^r-1)\cdot(q-1)=2^{r^2}-2^r=2^r\cdot(2^{\varphi(r^2)}-1).$$ It follows that $r^2\mid q-1$, as desired.

(There's another way to see why $r^2\mid q-1$. Since the order of $q$ modulo $2$ can't be $1$ or $r$ (the order being $r$ would lead to $2^{r^2}-1=(2^r-1)^2$), it has to be $r^2$. Hence $r^2\mid q-1$.)

Note that this is the case in Greg Martins's examples: $3^2\mid q-1$ and $7^2\mid q-1$ in both cases. If you want $p-1$ to be divisible by $r^2$ too, $r$ has to be a so-called Wieferich prime.

  • 1
    $\begingroup$ It's not true that $x=\mathop{\rm ord}_p(2)$; it's only true that $x$ is a multiple of $\mathop{\rm ord}_p(2)$. So it doesn't follow that $x\mid(p-1)$. $\endgroup$ – Greg Martin Jan 20 '14 at 22:41
  • 1
    $\begingroup$ $x$ is prime in that sentence, so the order is either $1$ or $x$. Since $2^1-1$ is not a prime, $\mbox{ord}_p(2)$ has to be $x$. $\endgroup$ – punctured dusk Jan 21 '14 at 10:25
  • $\begingroup$ Can you explain how you got $r^2 | q-1$? I see $2^r | q-1$ immediately, but can't do better. $\endgroup$ – Calvin Lin Jan 21 '14 at 15:45
  • $\begingroup$ @CalvinLin $r^2\mid 2^{\varphi(r^2)}-1$ because of Euler's theorem. Since $2^r-1\equiv1\pmod r$ we necessarily have $r^2\mid q-1$. $\endgroup$ – punctured dusk Jan 21 '14 at 15:48

No. I doubt there's a simple way of proving it. (EDIT: I was wrong - see barto's answer.)

First of all, we have no idea how to determine whether or not there are infinitely many $x$ such that $2^x-1$ is the product of two primes, even independent of the additional condition.

Note that $2^x-1=pq$ implies $2^x\equiv1\pmod p$, so it's reasonably likely already that $x$ is a divisor of $p-1$. And if $x$ is a divisor of either $p-1$ or $q-1$, then the additional condition is certainly satisfied.

I numerically verified your conjecture up to $x\le200$; there were only two cases where $p^2\not\equiv1\pmod x$, namely $2^9-1=7\cdot73$ with $7^2\equiv4\pmod9$ and $2^{49} - 1 = 127\cdot4432676798593$ with $127^2\equiv8\pmod{49}$. But in both cases we do have $q^2\equiv1\pmod x$.

  • $\begingroup$ What about $2^{9} - 1 = 7 * 73$ with $7^2 \equiv 4 \pmod 9$? $\endgroup$ – Joseph Geipel Jan 20 '14 at 21:28
  • $\begingroup$ We still have, $73^{2} \equiv 1 \bmod 9$ $\endgroup$ – Obinna Okechukwu Jan 20 '14 at 21:31
  • $\begingroup$ Yes, but $p^2 \not\equiv 1 \pmod x$, and Greg's verification said that $x = 49$ was the only case of this below 200. $\endgroup$ – Joseph Geipel Jan 20 '14 at 21:33

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.