　条件を満たす $n$ の集合を $S$ とする．一般性を失わず $p\leq q$ とする．このとき $\gcd(p-1,q)=1$ である.

(i) $2\lt p\lt q$ かつ $\gcd(p,q-1)=1$ のとき

　$p-1,q-1$ がともに偶数であることに留意すると, Fermatの小定理から
　　$$\begin{aligned}
　　(p-1)^{q-1}+(q-1)^{p-1}\equiv(-1)^{q-1}+1\equiv2 \pmod p \\\\
　　(p-1)^{q-1}+(q-1)^{p-1}\equiv1+(-1)^{p-1}\equiv2 \pmod q \end{aligned}$$
よって中国剰余定理から $(p-1)^{q-1}+(q-1)^{p-1}\equiv2 \pmod {pq}$ が分かり, 特に $2\in S$ である.

(ii) $2\lt p\lt q$ かつ $\gcd(p,q-1)\neq1$ のとき

　$p-1,q-1$ がともに偶数であることに留意すると，Fermatの小定理から
　　$$\begin{aligned}
　　(p-1)^{q-1}+(q-1)^{p-1}\equiv(-1)^{q-1}\equiv1\equiv-q+2 \pmod p \\\\
　　(p-1)^{q-1}+(q-1)^{p-1}\equiv1+(-1)^{p-1}\equiv2 \pmod q \end{aligned}$$
よって中国剰余定理から $(p-1)^{q-1}+(q-1)^{p-1}\equiv pq-q+2 \pmod{pq}$ が分かる.

　$2\lt p\lt q$ かつ $\gcd(p,q-1)\neq1$ をみたす組 $(p,q)$ であって, $pq-q+2$ が $100$ 以下となるのは次の通りである．ここで $p\lt q$ に留意すれば $p^2-2p+2\leq 100$ より, $p=3,5,7$ のみ考えれば良いことに留意する.

- $(p,q)=(3,7)$ のとき $pq-q+2=16$
- $(p,q)=(3,13)$ のとき $pq-q+2=28$
- $(p,q)=(3,19)$ のとき $pq-q+2=40$
- $(p,q)=(3,31)$ のとき $pq-q+2=64$
- $(p,q)=(3,37)$ のとき $pq-q+2=76$
- $(p,q)=(3,43)$ のとき $pq-q+2=88$
- $(p,q)=(5,11)$ のとき $pq-q+2=46$

ゆえに $16,28,40,46,64,76,88\in S$ である．

(iii) $p=q\gt 2$ のとき

　二項定理を用いれば
　　$$2(p-1)^{p-1}\equiv2(p+1)\pmod{p^2}$$
　$3$ 以上の素数 $p$ を用いて $2(p+1)$ と表される $100$ 以下の正整数は
　　$$8,12,16,24,28,36,40,48,60,64,76,84,88,96$$
であり, これらは $S$ に属する.

(iv)　$p=2$ のとき

　以下の式が常に成立することに留意すると, $n=q$  となるほかない.
　　$$(p-1)^{q-1}+(q-1)^{p-1}\equiv q \pmod {pq}$$
このとき $n$ が偶数であることから $n=2$ が必要で, 特に $2\in S$ である.

　以上より
　　$$S=\lbrace 2,8,12,16,24,28,36,40,46,48,60,64,76,84,88,96\rbrace$$
であり, 求めるこれらの総和は $\textbf{728}$ である．
公式解説
https://onlinemathcontest.com/contests/omc014/editorial/91
　次の条件をみたす $100$ 以下の正の偶数 $n$ の総和を求めてください.

- 条件：$n\lt pq$ かつ $(p-1)^{q-1}+(q-1)^{p-1}\equiv n \pmod{pq}$ をみたす素数の組 $(p,q)$ が存在する.