<s>[INST] Does every integer $n > 2$ have a "reciprocating" pseudoprime $a$? Does every integer $n > 2$ have a "reciprocating" pseudoprime $a$ such that $\gcd(a, n) = 1$ and satisfies both $a^{n - 1} \equiv 1 \mod n$ and $n^{a - 1} \equiv 1 \mod a$? (And of course allowing for the idea of even pseudoprimes).
From Fermat's little theorem it follows all odd primes have such a corresponding number.
 [/INST] For any composite $n$, take $a = \dfrac{n^n - 1}{n - 1}$. It is easy to prove that $a$ is also composite and $(a, n) = 1$. Note that$$
a = \frac{n^n - 1}{n - 1} = n^{n - 1} + \cdots + n + 1 \equiv 1 \pmod{n} \Longrightarrow a^{n - 1} \equiv 1 \pmod{n}.
$$
Also,$$
n^n = (n - 1)a + 1 \equiv 1 \pmod{a} \Longrightarrow n^{a - 1} = (n^n)^{\frac{n^{n - 1} - 1}{n - 1}} \equiv 1 \pmod{a}.
$$
Thus $a = \dfrac{n^n - 1}{n - 1}$ satisfies given conditions.
</s>