Obviously $3$, $p$ and $q$ have to be pairwise distinct. In fact, assuming the contrary and letting $p = q$ (for example), it would be $\alpha^{3p^2} \equiv \alpha \bmod p^2$, for any $\alpha \in \mathbb{Z}$. Anyway this is trivially checked to be false for $\alpha = p$. So suppose $p < q$ by simmetry. Then $p \neq 2$ and $3 < p < q$. In fact, letting $p = 2$ and $\gcd(\alpha, 3) = 1$, you'd find out $\alpha \equiv \alpha^{3pq} \equiv 1 \bmod 3$, which fails to be true for $\alpha \equiv 2 \bmod 3$. Now let $\alpha_1$ and $\alpha_2$ be primitive roots $\bmod\;\! p$ and $\bmod\;\! q$, respectively, and argue $(q-1) \mid (3p - 1)$ and $(p-1) \mid (3q - 1)$, by properties of generators and multiplicative orders. Then let i) $3p - 1 = (q-1)u$ and ii) $3q - 1 = (p-1)v$, for suitable $u, v \in \mathbb{Z}^+$. Because $q \geq 7$, you need $1 \leq u \leq 3$, since otherwise $(q-1)u \geq 3q - 1 > 3p - 1$. But $u = 1$ and $u = 3$ are actually impossible values (that's trivial!), so necessarily $u = 2$ and $q = \frac{3p+1}{2}$. Subsequently, it follows $p = \frac{2v+1}{2v-9}$ from ii). You need $p \geq 5$ as well as $v \geq 5$. Moreover you know the function $p(\cdot): [5, +\infty[ \; \mapsto \mathbb{R}: v \mapsto \frac{2v+1}{2v-9}$ is strictly decreasing for $v \geq 5$. You check $p(5) = 11$ and $p(4) < 5$ by hand, concluding that $v = 5$ only fits. Hence you get $p = 11$ and $q = 17$ (or viceversa, by symmetrization) and everything works.

hitlEULER wrote: Obviously $ 3$, $ p$ and $ q$ have to be pairwise distinct. In fact, assuming the contrary and letting $ p = q$ (for example), it would be $ \alpha^{3p^2} \equiv \alpha \bmod p^2$, for any $ \alpha \in \mathbb{Z}$. Anyway this is trivially checked to be false for $ \alpha = p$. So suppose $ p < q$ by simmetry. Then $ p \neq 2$ and $ 3 < p < q$. In fact, letting $ p = 2$ and $ \gcd(\alpha, 3) = 1$, you'd find out $ \alpha \equiv \alpha^{3pq} \equiv 1 \bmod 3$, which fails to be true for $ \alpha \equiv 2 \bmod 3$. Now let $ \alpha_1$ and $ \alpha_2$ be primitive roots $ \bmod\;\! p$ and $ \bmod\;\! q$, respectively, and argue $ (q - 1) \mid (3p - 1)$ and $ (p - 1) \mid (3q - 1)$, by properties of generators and multiplicative orders. Then let i) $ 3p - 1 = (q - 1)u$ and ii) $ 3q - 1 = (p - 1)v$, for suitable $ u, v \in \mathbb{Z}^ +$. Because $ q \geq 7$, you need $ 1 \leq u \leq 3$, since otherwise $ (q - 1)u \geq 3q - 1 > 3p - 1$. But $ u = 1$ and $ u = 3$ are actually impossible values (that's trivial!), so necessarily $ u = 2$ and $ q = \frac {3p + 1}{2}$. Subsequently, it follows $ p = \frac {2v + 1}{2v - 9}$ from ii). You need $ p \geq 5$ as well as $ v \geq 5$. Moreover you know the function $ p(\cdot): [5, + \infty[ \; \mapsto \mathbb{R}: v \mapsto \frac {2v + 1}{2v - 9}$ is strictly decreasing for $ v \geq 5$. You check $ p(5) = 11$ and $ p(4) < 5$ by hand, concluding that $ v = 5$ only fits. Hence you get $ p = 11$ and $ q = 17$ (or viceversa, by symmetrization) and everything works. Could somebody help me with the prove of (p - 1) / (3q - 1)?

let alpha be a primitive root mod q. then you do see why $ q-1|3pq-1$ right? (and then $ 3pq-1\equiv 3p-1 (\mod q-1)$)

WLOG $p\ge q,$ and note that if $q=2,$ then $3\nmid 2^{3\cdot 2\cdot p}-2.$ If $q=3,$ then $n^{9p}\equiv n\pmod{9}$ and setting $n=2$ yields $(-1)^p\equiv 2\pmod{9},$ which is absurd. Similarly, $p>3.$ We know $n^{3q}\equiv n^{3pq}\equiv n\pmod{p}$ so $g^{3q-1}\equiv 1\pmod{3}$ where $g$ is a primitive root modulo $p.$ Hence, $p-1\mid 3q-1$ since $\operatorname{ord}_p(g)=p-1.$ Similarly, we see $q-1\mid 3p-1$ so let $(p-1)\ell=3q-1$ and $(q-1)m=3p-1.$ Then, we have \[p\ell -\ell=3q-1\le 3p-1\implies \ell\le 3+\frac{2}{p-1}.\]Therefore, $\ell=1,$ $2,$ $3.$ If $\ell=1,$ then $p=3q,$ which is absurd. If $\ell=3,$ then we have a contradiction modulo $3$ so we need $\ell=2.$ Solving for $p$ in and substituting into the other equation, we have \[(q-1)m=3\cdot\frac{3q+1}{2}-1\implies q=\frac{2m+1}{2m-9}.\]In order for $2m+1\mid 2m-9,$ we need $2m-9\mid 10$ so $m=5,$ $7.$ Therefore, $q=3,$ $11$ and $p=5,$ $17,$ respectively. Since $p,q>3,$ our only solutions are $\boxed{(p,q)=(11,17),(17,11)}.$

Put $n=2$ in $3\mid n^{3pq}-n$ to get $p$, $q$ are both odd. Now if anyone of them $=3$ , say $p$, then $9\mid n^{9q}-n$, and choose a primitive root $g$ to get $g^{9q-1}\equiv 1\pmod{9}\implies 6\mid 9q-1$, contradiction. So, $p,q\not=2,3$. Now for a primitive root $g\pmod p$, we have $g^{3pq}\equiv g\pmod p\implies g^{3q-1}\equiv 1\pmod p\implies p-1\mid 3q-1$. Similarly choose a primitive root $\pmod q$ to get $q-1\mid 3p-1$. So now we have $p-1\mid 3q-1$ and $q-1\mid 3p-1$. WLOG $p\le q$. Now $\dfrac{3p-1}{q-1}\ge 5$ fails due to size reasons. Now we use bounding from which we get for $\dfrac{3p-1}{q-1}=4$ that $q=3$, contradiction. $\dfrac{3p-1}{q-1}=3$ fails $\pmod 3$. $\dfrac{3p-1}{q-1}=1$ fails due to $q=3p$. So we must have $\dfrac{3p-1}{q-1}=2\implies q=\dfrac{3p+1}{2}$. Put this in $p-1\mid 3q-1$ to get $p=11$ from which $q=17$. So our solutions for $(p,q)$ are $(11,17)$ and $(17,11)$.

The answer is $(11, 17)$ and $(17, 11)$ only, which work. Pick some $n$ that is a primitive root modulo $p$ and $q$ which exists by CRT. Let $p, q$ be odd primes for now. Then, $pq \mid n^{3pq - 1} - 1$, thus $$p-1 \mid 3pq - 1 \iff p - 1 \mid 3q-1$$and similarly $q-1 \mid 3p-1$. WLOG $p \leq q$, so we have $3q - 1 \geq 3p-1$; thus, we must have $3p-1 = 2q - 2$ is the only valid case. Plugging this back in, we have $$p-1 \mid \frac 92 p + \frac 12 \implies \frac 92 p + \frac 12 = 5p - 5 \iff p = 11.$$ On the other hand, if $2 \in \{p, q\}$, we have $6q \mid n^{6q} - 1$, so $q-1 \mid 6q-1$, and $q=2$. But this case fails too.

Solved with dolphinday. It was pretty nice for such an old problem. The answer is $(11,17)$ and $(17,11)$ only. (The confirmation of these solutions is at the bottom of the solution). We first show the following key claim. Claim : The divisibilities $p-1 \mid 3q-1$ and $q-1 \mid 3p-1$ must hold. Proof: SImply note that by considering a primitive root $\pmod{p}$ for $n$ (which is known to exist), we have \[n^{3pq-1}\equiv 1 \pmod{p} \implies \text{ord}_p(n) \mid 3pq-1 \]combining this with the fact that $\text{ord}_p(n)=p-1$ we have that, \[p-1 \mid 3q-1\]as desired. Similarly, we obtain that (by considering a primitive root $\pmod{q}$ to be $n$) $q-1 \mid 3p-1$. Now, we resort to size. WLOG, assume $p\geq q$.If $p=q$ then we have that $q-1 \mid 3q-1$ which implies that $p=q=2$ or $p=q=3$. These can be clearly seen to be impossible by considering $n=3$ and $n=2$ respectively. Note that from $p-1\mid 3q-1$ we have that $3q-1=k(p-1)$. For all $k\geq3$, this implies that \[k(p-1)\geq 3(p-1)=3p-3 > 3q-1\]for all primes $p,q$ (since $p,q$ are distinct $p-q\geq 2$.) Thus, $k=1$ or $k=2$. One can check that $k=1$ is impossible as it implies $p=3q$ which is clearly non-prime. Thus, we have that \[p=\frac{3q+1}{2}\]Now, plugging this into the other divisibility we obtain that \begin{align*} q-1 & \mid 3\left(\frac{3q+1}{2}\right)-1\\ q-1 & \mid \frac{9q+1}{2}\\ 2q-2 & \mid 9p+1\\ 2q-2 &\mid q+9 \end{align*}which can then be seen to imply that $q\leq 11$ with some size bounding. Then, checking the values of $p$ for $q=2,3,5,7,11$ we see that the only possibilities are $(3,5),(7,11)$ and $(11,17)$. Of these, $(3,5)$ clearly fails when $n=3$. For, $(7,11)$ we have that, \[3\times 7 \times 11 \mid n(n^{230}-1)\]which clearly fails for $n\equiv 2 \pmod{7}$. For, $(11,17)$ note that the original equation turns into \[3\times 11 \times 17 \mid n(n^{560}-1)\]which clearly holds for all $n$. (if $3,7,11\mid n$ it divides the first factor, if not it divides the second factor since $2,10,16\mid 560$). Thus, the only answer is the claimed one which has been checked to work.

I claim that the only solutions are $\boxed{(p, q) \in \{(11, 17), (17, 11)\}}$. First observe that all of $3, p, q$ must be distinct and all odd. If say, $p$ were even, then $n^{6q} \equiv n \pmod 6$, so if $n = 5$ we would have $1 \equiv 5 \pmod 6$ which is a contradiction. Also note that $3, p, q$ must be distinct as if $p = q$, then $n^{3p^2 - 1} \equiv 1 \pmod{p^2}$, and so if $n = p$, we would derive a contradiction as $p$ is odd, and similar reasoning follows if either $p$ or $q$ are $3$. Therefore assume without loss of generality that $p > q > 3$. We now then make the following claim: Claim: We have that $p - 1 \mid 3q - 1$ and $q - 1 \mid 3p - 1$. Proof: Let $g$ be a primitive root modulo $p$. Then \[g^{3pq} \equiv g \pmod p \implies g^{3q - 1} \equiv 1 \pmod p \implies p - 1 \mid 3q - 1.\]Similarly it follows that $q - 1 \mid 3p - 1$. $\square$ Hence we may write $3q - 1 = a(p - 1)$ and $3p - 1 = b(q - 1)$, and also observe $1 \leq a \leq 3$, as if $a > 3$, we must have $3q - 1 = a(p - 1) > 3p - 3 \geq 3q - 1$, as $p - q \geq 2$, which is a contradiction. Now $a = 1, 3$ gives us that $p \equiv 0 \pmod 3$ and $3q - 1 \equiv 0 \pmod 3$ respectively, both of which are impossible. Hence $a = 2$, and this gives us \[p = \frac{3q + 1}{2} \implies b = \frac{9q + 1}{2(q - 1)} \implies q - 1 \mid 10 \implies q = 2, 3, 6, 11.\]Of these only $\boxed{q = 11}$ works, which in turn provides $\boxed{p = 17}$, and vice versa. Therefore all of the solutions are $\boxed{(11, 17), (17, 11),}$ as was claimed. $\blacksquare$

By FLT, $0 \equiv n^{3pq}-n \equiv n^{3q}-n \pmod p.$ If we let $n$ be a primitive root mod $p,$ then we have that $p-1 | 3q-1.$ Similarly, $q-1 | 3p-1, 2 | pq-1.$ Therefore, $p, q \geq 3.$ We can also easily verify that $p, q \neq 3 \implies p, q > 3.$ Now, let $3p-1=a(q-1).$ WLOG, assume that $p \leq q,$ then we have that $$a(q-1)=3p-1 \leq 3q-1 \implies a \leq 3+\frac{2}{q-1} \implies a=1, 2, 3.$$If $a=1, q=3p,$ impossible. If $a=3,$ taking mod $3$ on $a(q-1)=3p-1$ yields a contradiction. Thus $a=2 \implies 2q=3p+1,$ meaning that $$p-1 | \frac{9p+1}{2} \implies p-1 | 9p+1 \implies p-1 | 10 \implies p=11.$$Hence, $q=17.$ Therefore, the only solutions are $(11, 17), (17, 11),$ and it is easy to show that both of these work.

Me when Carmichael numbers are a thing