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

Question

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?

Answer 1

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.

Answer 2

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