# Conjecture involving semi-prime numbers of the form $2^{x}-1$

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.

• 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)$. – Greg Martin Jan 20 '14 at 22:41
• $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$. – punctured dusk Jan 21 '14 at 10:25
• Can you explain how you got $r^2 | q-1$? I see $2^r | q-1$ immediately, but can't do better. – Calvin Lin Jan 21 '14 at 15:45
• @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$. – 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$.

• What about $2^{9} - 1 = 7 * 73$ with $7^2 \equiv 4 \pmod 9$? – Joseph Geipel Jan 20 '14 at 21:28
• We still have, $73^{2} \equiv 1 \bmod 9$ – Obinna Okechukwu Jan 20 '14 at 21:31
• 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. – Joseph Geipel Jan 20 '14 at 21:33