Infinitely many primes with $2$ and $3$ generating the same set of residues

Question

Prove that there are sets $S$ and $T$ of infinitely many primes such that:

• For every $p\in S$ there exists a positive integer $n$ such that $p\mid 2^{n} - 3$.
• For every $p \in T$ the remainders mod $p$ of $\{2,2^2,2^3,\ldots\}$ and $\{3,3^2,3^3,\ldots\}$ are the same as sets. (Hint: Consider divisors of $2^{3^n} - 3$ for suitably chosen $n$.)

I was able to do the first part - assume they are finitely many, say $p_1,\ldots,p_k$, and observe that they are odd and that none of them divides $2^{(p_1-1)(p_2-1)\cdots (p_k-1)} - 3$ by Fermat's/Euler's theorem.

Any idea how to approach the (stronger) second part? Any help appreciated!

UPDATE: As Hagen von Etizen suggested, it suffices to consider $p$ such that $p\mid 2^n - 3$ and $p\mid 3^m - 2$ for some integers $m$ and $n$. It is then tempting to take all primes $p_1,p_2,\ldots$ which divide some $2^n - 3$ and suppose only $q_1,\ldots,q_k$ divide some $A = 3^n - 2$ -- then $n=(q_1-1)\cdots(q_k-1) \geq 2$ could again help, but even though $A$ must have a prime factor, this factor may not be among $p_1,p_2,\ldots$ and this is troubling! Any other ideas?

Answer 1

Unfortunately, I don't see any direct way to use the approach you stated in your update. Instead, here is a way to use the provided hint. Have there be $k$ (starting with $k = 0$) distinct, odd primes $p \in T$, with these primes being $p_i$ for $1 \le i \le k$. Then define

$$n = \prod_{i=1}^{k}\varphi(p_i - 1) \tag{1}\label{eq1A}$$

By Euler's theorem, this gives

$$3^{n} \equiv 1 \pmod{p_i - 1} \; \forall \; 1 \le i \le k \tag{2}\label{eq2A}$$

Thus, we have

$$u = 2^{3^{n}} - 3 \equiv 2 \cdot 2^{3^n-1}-3 \equiv 2 - 3 \equiv -1 \pmod{p_i} \; \forall \; 1 \le i \le k \tag{3}\label{eq3A}$$

Next, due to $u \equiv 2 \pmod{3}$, there's at least one prime which is $\equiv 2 \pmod{3}$ which divides $u$. Choose any one of these (e.g., the smallest one) and call it $q$. Since \eqref{eq3A} shows none of the $p_i$ divide $u$, then $q$ must be different from all of them.

Since $q \equiv 2 \pmod{3}$, then $\gcd(3, q - 1) = 1$. Thus, there exist multiplicative inverses for $3^{n}$ modulo $q - 1$, so pick the smallest positive one and call it $m$. This therefore gives, for some integer $s$,

$$3^{n}(m) \equiv 1 \pmod{q - 1} \; \; \to \; \; 3^{n}(m) = (q - 1)s + 1 \tag{4}\label{eq4A}$$

Next, using this gives that

$$\begin{equation}\begin{aligned} 2^{3^{n}} & \equiv 3 \pmod{q} \\ \left(2^{3^{n}}\right)^{m} & \equiv 3^{m} \pmod{q} \\ 2^{(q-1)s + 1} & \equiv 3^{m} \pmod{q} \\ \left(2^{q-1}\right)^{s}(2) & \equiv 3^{m} \pmod{q} \\ 2 & \equiv 3^{m} \pmod{q} \end{aligned}\end{equation}\tag{5}\label{eq5A}$$

As you stated in the question, this is sufficient. Nonetheless, to prove that $q \in T$, have the set of remainders mod $q$ of $\{2, 2^2, 2^3, \ldots \}$ be $U$ and of $\{3, 3^2, 3^3, \ldots \}$ be $V$. It is relatively easily to show $U \subseteq V$ and $V \subseteq U$, so $U = V$.

Thus, set $p_{k+1} = q$, increment $k$ and repeat the above steps. Doing this infinitely often shows there are an infinite number of distinct primes $p_{i} \in T$.