<s>[INST] 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?
 [/INST] 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.
</s>