Write $a=p^{q-1}+q^{p-1}$. Immediately we have
$$\begin{cases} a\equiv 0^{\,q-1}+q^{p-1} \equiv 1 \mod p \\
a\equiv p^{q-1}+0^{\,p-1} \equiv 1 \mod q.\end{cases}$$
What does CRT tell us $a$ must be $\bmod pq$?
Given ODD primes $p \neq q:$ and $$ \color{magenta}{p \equiv 3 \pmod 4} $$
Lemma: $$ (-p|q) = (q|p). $$
Lemma: If $$ a^2 + p \equiv 0 \pmod q, $$ THEN $$ (q|p) = 1. $$
Let $$ F_1 = 4 + p, $$
$$ F_2 = 4 F_1^2 + p, $$
$$ F_3 = 4 F_1^2 F_2^2 + p, $$
$$ F_4 = 4 F_1^2 F_2^2 F_3^2 + p, $$
$$ F_5 = 4 F_1^2 F_2^2 F_3^2 F_4^2 + p, $$
and so on.
These are all of the form $a^2 + p$ and are odd, so the only primes than can be factors are quadratic residues for $p.$ Next, all the $F_j$ are prime to $p$ itself. Finally, these are all coprime. So, however they factor, we get an infinite list of primes that are quadratic residues of $p.$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Given ODD primes $p \neq q:$ and $$ \color{magenta}{p \equiv 1 \pmod 4} $$
Lemma: $$ (p|q) = (q|p). $$
Lemma: If $$ a^2 - p \equiv 0 \pmod q, $$ THEN $$ (q|p) = 1. $$
FIND an even square $$ W = 4^k = \left( 2^k \right)^2 $$ such that
$$ \color{magenta}{ W > p.} $$
Let $$ F_1 = W - p, $$
$$ F_2 = W F_1^2 - p, $$
$$ F_3 = W F_1^2 F_2^2 - p, $$
$$ F_4 = W F_1^2 F_2^2 F_3^2 - p, $$
$$ F_5 = W F_1^2 F_2^2 F_3^2 F_4^2 - p, $$
and so on. As $p \equiv 1 \pmod 4$ and $W \equiv 0 \pmod 4,$ we know $W - p \equiv 3 \pmod 4 $ and so $W-p \geq 3. $ So the $F_j$ are larger than $1$ and strictly increasing.
These are all of the form $a^2 - p$ and are odd, so the only primes than can be factors are quadratic residues for $p.$ Next, all the $F_j$ are prime to $p$ itself. Finally, these are all coprime. So, however they factor, we get an infinite list of primes that are quadratic residues of $p.$
Best Answer
$$3^{18}\equiv 1 \text{ mod 19}$$ $$3^{18*55555}\equiv 1 \text{ mod 19}$$ $$3^{999990}\equiv 1\text{ mod 19}$$ $$3^{1000000}\equiv 3^{10} \text{ mod 19}$$ $$3^{1000000}\equiv 16\text{ mod 19}$$