# Reversing the CRT: Is $5$ tough?

Given odd primes $$p\ne q$$, by the CRT we can find an integer $$x$$ such that $$x\equiv 2^{p-1}\pmod q$$ and $$x\equiv 2^{q-1}\pmod p$$. Can this procedure be reversed?

For which integers $$x$$ there exist odd primes $$p\ne q$$ satisfying $$\begin{cases} 2^{p-1}\equiv x\pmod q \\ 2^{q-1}\equiv x\pmod p \end{cases}\ ?$$

If such $$p$$ and $$q$$ exist, then I call $$x$$ nice; otherwise, $$x$$ is tough. Say, $$1$$ is nice (as witnessed by the prime pair $$(11,31)$$), while $$0$$ is tough.

Computations show that in the range $$-20\le x\le 20$$, the numbers $$-19, -18, -17, -16, -13, -11, -8, -6, -5, -4, 1, 2, 3, 4, 6, 8, 9, 10, 13, 14, 16, 17, 18, 19$$ are nice, while $$-20, -15, -14, -12, -10, -9, -7, -3, -2, -1, 0, 5, 7, 11, 12, 15, 20$$ are good candidates to be tough, in the sense that there are no primes $$3\le p such that the congruences above hold true.

This suggests a number of questions.

Is there an algorithm to determine whether a given integer $$x$$ is nice or tough?

Do positive tough integers exist? If so, what is the smallest of them? (It is quite likely that $$5$$ is tough, but I couldn't prove this.)

Are there infinitely many tough integers of both signs? Are there "more" negative than positive tough integers, as computations suggest?

I do not ask whether negative tough integers exist since I know that $$x=-1$$ is tough; here is the proof.

Let $$d$$ denote the order of $$2$$ in $$(\mathbb Z/q\mathbb Z)^\times$$. If $$2^{p-1}\equiv -1\pmod q$$, then $$d\nmid p-1$$, but $$d\mid 2(p-1)$$; consequently, $$\nu_2(d)>\nu_2(p-1)$$ where $$\nu_2$$ is the $$2$$-adic valuation function. On the other hand, from $$d\mid(q-1)$$ we get $$\nu_2(d)\le \nu_2(q-1)$$. Hence, $$\nu_2(p-1)<\nu_2(q-1)$$. Switching the roles of $$p$$ and $$q$$, in the very same way we obtain $$\nu_2(q-1)<\nu_2(p-1)$$, a contradiction.

My motivation came originally from this problem (consider $$n=pq$$), but it will be fair to say that I am driven mainly by curiosity.

The system of congruences in question is equivalent to $$2^{pq}\equiv 2x\pmod{pq}$$, i.e., the question is whether there exists an odd semiprime solution $$n$$ to $$2^n\equiv c\pmod{n}$$ (where $$c=2x$$).
You can exclude many candidates by looking at 2^n mod n page at OEIS Wiki (and the corresponding sequences). For example, the sequence for $$c=10$$ contains an odd semiprime 24430928839, which disproves that 5 is tough.
• Interesting. Thus, we do not know any tough integers save for $x=0$ (trivial) and $x=1$ (addressed in my question). – W-t-P Apr 13 at 17:29
• Upon a careful checking, there is just one more candidate excluded by the data at the OEIS Wiki page that you mentioned: $-3$. – W-t-P Apr 13 at 19:11