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<q<10^4$ 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.

  • $\begingroup$ Interesting. Thus, we do not know any tough integers save for $x=0$ (trivial) and $x=1$ (addressed in my question). $\endgroup$ – W-t-P Apr 13 at 17:29
  • $\begingroup$ Questions like this go back to Lehmer and Graham -- see problem F10 in Guy's UPINT book. $\endgroup$ – Max Alekseyev Apr 13 at 17:45
  • $\begingroup$ Upon a careful checking, there is just one more candidate excluded by the data at the OEIS Wiki page that you mentioned: $-3$. $\endgroup$ – W-t-P Apr 13 at 19:11
  • $\begingroup$ @W-t-P: Look at the linked sequences as well. E.g., 279283702428813463 excludes 7. $\endgroup$ – Max Alekseyev Apr 13 at 19:20

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.