$p$ は $10$ および $9$ と互いに素であるから， $$1111\ldots1=\sum_{k=0}^{p-2}10^k=\frac{10^{p-1}-1}{10-1}\equiv0\pmod p.$$

何通りか解法を紹介する：

• $20^{10000}\equiv7^{10000}\equiv7^{10000\bmod12}\equiv7^{4}\equiv2401\equiv9\pmod{13}$
• $20^{10000}\equiv\dfrac{40^{10000}}{2^{10000}}\equiv 2^{-10000}\equiv2^{-10000\bmod12}\equiv2^{8}\equiv256\equiv9\pmod{13}$
• $20^{10000}\equiv2^{20000}5^{10000}\equiv2^{8}5^{4}\equiv256\cdot25^2\equiv9\cdot(-1)^2\equiv9\pmod{13}$

十の位のかわりに下二桁を求める．すなわち，$11^{12^{13}}$ を $100$ で割った余りを求める．

$\lambda(100)=\operatorname{lcm}(2,20)=20$，$\lambda(20)=\operatorname{lcm}(2,4)=4$ により， $$11^{12^{13}}\equiv11^{12^{13}\bmod{20}}\equiv11^{12^{13\bmod4}}\equiv11^{12}\pmod{100}$$ までは計算できるが，ここから工夫が必要である．以下には二つの選択肢を示す：

• $11^1\equiv11,\ 11^2\equiv21,\ 11^3\equiv31,\ldots,\pmod{100}$ であるから，$11^{a}\equiv10a+1\pmod{100}$ であると予想でき，これは帰納法によって証明できる．よって，$11^{12}\equiv 121\equiv21\pmod{100}$．
• 二項定理により，$11^{12}\equiv(10+1)^{12}\equiv\cdots+{}_{12}\mathrm{C}_2\cdot10^2+12\cdot10+1\equiv21\pmod{100}$．

二乗の総和の公式を用いればよいが，少しだけ工夫する． $$1^2+2^2+\cdots+100^2\equiv (1^2+2^2+\cdots+101^2)-101^2\equiv6(1^2+2^2+\cdots+16^2)-(-1)^2\pmod{17}$$ とすれば，$1^2+2^2+\cdots+16^2\equiv\dfrac{16\cdot17\cdot33}6\equiv0\pmod{17}$ であるから，求める余りは $16$．

なお，これは$\bmod17$ の原始根 $g$ をとることで次のようにも理解できる： $$1^2+2^2+\cdots+16^2\equiv g^0+g^2+…+g^{30}\equiv\dfrac{g^{32}-1}{g^2-1}\equiv0\pmod{17}$$

$g$ を$\bmod p$ における原始根とする，$g^a\not\equiv1\pmod p$ のとき， $$\sum_{k=1}^{p-1}k^a\equiv\sum_{k=0}^{p-2}g^{ak}\equiv\dfrac{g^{a(p-1)-1}}{g^a-1}\equiv0\pmod{p}.$$ ただし，最後にフェルマーの小定理を用いた．一方で $g^a\equiv1\pmod p$ のとき， $$\sum_{k=1}^{p-1}k^a\equiv1\cdot(p-1)\equiv-1\not\equiv0\pmod{p}.$$ よって求める条件は $g^{a}\not\equiv1\pmod p$ が，これは $p-1 \not\mid a$ と言いかえられる．

なお，原始根を使わなくても解くことはできる．各自で試みよ．

$$\sum_{n=1}^{p-1}\frac1n\equiv\frac12\sum_{n=1}^{p-1}\left(\frac1n+\frac1{p-n}\right)\equiv\frac p2\sum_{n=1}^{p-1}\left(\frac1{n(p-n)}\right)\equiv-\frac p2\sum_{n=1}^{p-1}\frac1{n^2}\equiv0\pmod{p^2}$$

ただし，最後の等号は例題5から得られる． なお，最初の式変形をせずに原始根を持ち出しても$\bmod p$ の範疇から出られないため，最初の式変形は本質的である．

$p=2$ のときは明らかであるから，$p\geq3$ とする．

解法1.　$f(x\bmod p)\equiv x^{-1}\bmod p$ によって定義される写像 $f\colon\{1,2,\ldots,p-1\}\to\{1,2,\ldots,p-1\}$ は全単射であり，$x\not\equiv\pm1\pmod p$ であれば $f(x)\not\equiv x\pmod p$ であるから， $$(p-1)!\equiv1\cdot(-1)\cdot\bigl(2\cdot f(2)\bigr)\cdots\bigl(k\cdot f(k)\bigr)\equiv -1\pmod p.$$

解法2.　$g$ を$\bmod p$ における原始根とすると， $$(p-1)!\equiv\prod_{n=1}^{p-2}g^n\equiv g^{\frac{(p-2)(p-1)}2}\equiv g^{\frac{p-1}2}g^{(p-1)\frac{p-3}2}\equiv-1\pmod p.$$

解法3.　以下の両辺を $\displaystyle\prod_{n=1}^{p-2}(1+n)$ で割ればよい： $$\prod_{n=1}^{p-2}(1+n)\equiv\prod_{m=1}^{p-2}\left(1+\frac1m\right)\equiv\frac{1}{(p-2)!}\prod_{n=1}^{p-2}(1+n) \pmod{p}.$$

$g$ を$\bmod 31$ における原始根とすると， \begin{align} \prod_{n=1}^{30}(1+n^2) &\equiv 2^2\cdot\prod_{n=2}^{29}\frac{n^4-1}{n^2-1} \\ &\equiv 4\cdot\prod_{1\leq m\leq29, m\neq15}\frac{g^{4m}-1}{g^{2m}-1} \\ &\equiv 4\cdot\prod_{1\leq m\leq29, m\neq15}\frac{g^{2m}-1}{g^{2m}-1}\equiv4 \pmod{31}. \end{align} ここで，$1\leq m\leq29, m\neq15$ を動くとき，$4m\bmod30$ と $2m\bmod 30$ のとりうる値全体は多重集合として一致することを用いた．

それぞれの素数を法として考えよう．$p=q$ のときは様子が変わってしまうので，まずは $p\gt q$ のときに考える． まず $q=2$ のときは $(p-1)^{q-1}+(q-1)^{p-1}=p-1+1=p$ により $n=p$ となるが，$n$ は偶数であるから不適． 以下，$q\gt 3$ とする．いま，$p\not\mid q-1$ であるから $(p-1)^{q-1}+(q-1)^{p-1}\equiv1+1=2\pmod p$ である．

さて，$q\not\mid p-1$ ならば同様に $(p-1)^{q-1}+(q-1)^{p-1}\equiv2\pmod{q}$ となる． まとめれば $$(p-1)^{q-1}+(q-1)^{p-1}\equiv2\pmod{pq}$$ となり，これは $n=2$ のときに対応する（たとえば $(p,q)=(7,5)$ で実現できる）．

$q\mid p-1$ のときも同様に $(p-1)^{q-1}+(q-1)^{p-1}\equiv2-p\pmod{pq}$ であるから，$n=pq-p+2$ となる． あとは適当な大小評価によって絞り込めば，$n=16,28,40,46,64,76,88$ とわかる．

最後に $p=q$ のときを考える．$p=q=2$ のときは $n=2$ を得る．$p\geq 3$ のとき， $$(p-1)^{q-1}+(q-1)^{p-1}\equiv 2(p-1)^{p-1}\equiv 2\bigl(p^{p-1}-\cdots-(p-1)p+1\bigr)\equiv2(p+1)\pmod{p^2}.$$ $p\geq3$ で $2(p+1)<p^2$ であるから，このとき $n=2(p+1)$ となり， $$n=8,12,16,24,28,36,40,48,60,64,76,84,88,96.$$

$n^3-7n+9\equiv n-7n+9\equiv0\pmod3$ により $n^3-7n+9=3$ が必要であり，$n=1,2,-3$．

存在しないことを示す．そのために，$8^n+47$ が素数になったと仮定する．

まずは，$8=2^3$ や $8\pm1=7,9$ であることから$\bmod7,9$ が使えそうだが， $\bmod7$ では情報は増えない． $\bmod9$ で検討すると（$\bmod3$ でもよい），$n\equiv1\pmod2$ が必要である． これによって $2^{6m-3}+47$ の形だけ考えればよい（$n=2m-1$ としている）． これができる限り少ない値しか取らない法を探そう．

まず，とりうる値が一つしかないのは（$2^6-1=63$ により）上ですでに調べた $\bmod7,9$ などである． とりうる値が二つになるのは，$2^6+1=65$ により（←なぜか？）$\bmod5,13$ などが該当する．

$\bmod5$ では $m\equiv0\pmod2$ が必要で，$\bmod13$ では $m\equiv1\pmod2$ が必要なので，矛盾する．

式の形がすさまじいので，十中八九適切な法を選べば解けるだろう（そうでないならば，超難問になりうる）．

$\bmod{m}$ で考えるとして，$2,11$ と $\varphi(m)$ が非自明な公約数を持ってほしい． $2022!$ は約数を大量にもつので，$m$ は小さく定数として固定すれば事足りるだろう． この条件をみたす最小の $m$ は $23$ であり， 実際$\bmod23$ で考えれば $n\equiv20\pmod{23}$ のとき $x,y,z$ が存在しないことがわかる.

$m\geq8$ のとき $\bmod2^8$ を見て $n\equiv35\pmod{64}$ であり， さらに $\bmod641$ を見れば存在しないことが分かる．

あとは $m\leq 7$ を調べて $(m,n)=(7,3),(3,1),(2,0)$．

$641$ とは，$5^{64}-1$ の素因数であって，$2$ の位数も比較的小さい ($64$) ものである．

一見$\bmod5$ などを使いそうだが， $n^4+4=(n^2+2n+2)(n^2-2n+2)$ に注意することで $n=1$ のみ．

$(1)$　$\dfrac{n^p-1}{n-1}$ の $p$ でない素因数 $q$ であって， $p$ で割った余りが $1$ でもないものが存在したと仮定する． このとき，$n^p\equiv1\pmod q$ が成立する． また，これにより $n$ は $p$ で割り切れないから，フェルマーの小定理により $n^{q-1}\equiv1\pmod q$ も成立する． よって，仮定により $(q-1,p)=1$ なので，$n\equiv n^{(q-1,p)}\equiv1\pmod q$ が成立するが， $$ 0\equiv\dfrac{n^p-1}{n-1}=n^{p-1}+…+n+1\equiv1^{p-1}+…+1+1\equiv p\pmod q $$ となるので矛盾する（ここの議論にはLTEの補題を用いてもよい）．

$(2)$　$p$ で割って $1$ 余る素数が有限個であったと仮定し，それらの総積を $S$ とする． $(1)$ で $n=pS$ とすると，$\dfrac{n^p-1}{n-1}$ は $p$ で割り切れず， また $S$ の定め方から $p$ で割って $1$ 余る素因数ももたない． これは $(1)$ により $\dfrac{n^p-1}{n-1}=\pm1$ であることを意味するが，明らかに不合理である．

$d\mid n$ とすると，$\Phi_n(a,b)\mid \dfrac{a^n-b^n}{a^d-b^d}$ であるから，適当な $d$ をとればよい．

両辺ともに円分型の式なので，どちらの素因数に関する議論をしようか迷うが，左辺の素因数の制約の方が厳しい． 具体的には，$p\mid\dfrac{x^7-1}{x-1}$ とすると，$p=7$ または $p\equiv1\pmod7$ である． この情報を右辺に反映させたい． これは盲点になりがちだが，よく考えると右辺は $(y-1)(y^4+y^3+y^2+y+1)$ と因数分解できるから， 二つの因数を $7$ で割った余りはともに $0$ または $1$ である （としたいところだが，各因数が負のときは少しだけ話が違うので，$y\gt 1$ を事前に確認しておく必要があることに注意しておこう）． これらは両立しない．すなわち，解は存在しない！

$p=2$ のとき $n=2,4$ が条件をみたす． $p\geq3$ のとき，分母は偶数なので分子も偶数．すなわち $n$ は奇数である． 明らかに $n\geq3$ であり，このとき $\dfrac{n^p+1}{p^n+1}\geq1$ は $p\geq n$ を意味する．

ここで上記の手法を用いる．$n$ は奇数なので分母は $p+1$ で割り切れる．すなわち $n^p\equiv-1\pmod{p+1}$． また，オイラーの定理により $n^{\varphi(p+1)}\equiv1\pmod{p+1}$ なので $n^{\bigl(p,\varphi(p+1)\bigr)}\equiv-1\pmod{p+1}$． いま $p\geq3$ により $\varphi(p+1)\leq\dfrac{p+1}2\lt p$ であるから $\bigl(p,\varphi(p+1)\bigr)=1$． よって，$p+1\mid n+1\pmod{p+1}$ であり，特に $n+1\geq p+1$ であるから，最初に得られた $p\geq n$ とあわせて $n=p$． これは条件をみたす．

よって，求める組は（$p$ を任意の素数として）$(n,p)=(p,p),(4,2)$ である．

$p\gt n$ であることに注意しておく． 分子の素因数は，$n-1$ の素因数か，$p$ か，$p$ で割って $1$ 余るもののいずれかである． 一方で，分母の約数を $p$ で割った余りは，基本的に $1$ になることはない． これでもう解けるだろう．

$n=1$ のときはつねに条件をみたすから，$1\lt n\lt p$ とする． このとき，$p^2-n^2=(p+n)(p-n)$ の素因数を $p$ で割った余りは $0,1$ にはなりえない． 一方で，$\dfrac{n^p-1}{n-1}$ の素因数を $p$ で割った余りは $0$ か $1$ であるから，$\biggl(p^2-n^2,\dfrac{n^p-1}{n-1}\bigg)=1$． よって $\dfrac{n-1}{p^2-n^2}$ は正整数となるが，$n-1\geq p^2-n^2$ とはなりえない．

よって，求める組は（$p$ を任意の素数として）$(n,p)=(1,p)$ である．

分子は奇数であるから $n$ も奇数である． $n$ の最小の素因数を $p$ とすると，$2^{n}\equiv-1\pmod p$ であり， フェルマーの小定理により $2^{p-1}\equiv1\pmod p$ でもあるから，$2^{(n,p-1)}\equiv-1\pmod p$． ここで，$p$ が $n$ の最小の素因数であることから $(n,p-1)=1$ となるので， $3\equiv0\pmod p$，すなわち $p=3$ である．

いま，$n=3^a m$（$a$ は正整数，$m$ は $3$ で割り切れない正整数）と表すと， 分母は $3$ で $2a$ 回割り切れるが，分子はLTEの補題により（$n$ は奇数である事に注意）$3$ で $a+1$ 回しか割り切れない． よって，$a=1$ が必要である．

$m\gt 1$ として，その最小の素因数 $q\,(\geq 5)$ をとると，同様にして $2^{(3m,q-1)}\equiv -1\pmod q$． $q$ の最小性と $(-1)^3=-1$ に注意すれば，$2^3\equiv -1\pmod q$ すなわち $q\mid9$ を得るが，これはありえない． よって $m=1$となり，求める $n$ は $3$ のみである．

まず，$x^{2^n}-1$ という形をふまえれば，$2^ny+1$ の適当な素因数 $p$ をとればよさそうである． $p$ に課したい制約は，$x^{2^n}-1\equiv x^{(2^n,p-1)}-1\pmod p$ に注意すれば $p-1$ があまり $2$ で割り切れないこと， さらに $x$ に対して十分大きいことである．

一つ目の制約を考えると，できれば小さい $n$ に対する $2^ny+1$ の素因数をとりたい（$v_2(p-1)$ が小さく，抑えやすいので）． しかし，二つ目の制約をふまえてその点は譲歩してもらい， 実は $n$ が大きくても $2^ny+1$ の素因数 $p$ で $v_2(p-1)$ が小さいものがあることを示したい．

いま，$n$ の大小はさておき $2^n\pmod p$ は周期的だから， $p\mid2y+1$ かつ十分大きいある整数 $n$ に対して $p\mid 2^ny+1$，といったようにできる． ここで，$v_2\bigl(\dfrac{2^ny+1}p-1\bigr)$ は小さいので， $\dfrac{2^ny+1}p$ の素因数 $q$ であって $v_2(q-1)$ が小さいものが存在する． さらに $n$ を工夫してとれば，$q$ は大きくできる． というのも，フェルマーの小定理を使って， 小さい素数 $r$ に対して $2^ny+1\equiv 2y+1\pmod r$ となるように $n$ をとってしまえばよいからである．

$n=1+\varphi\bigl((2y+1)^2\cdot x^{2y+1}!\bigr)$ とすると，$2^ny+1\equiv0\pmod{2y+1}$ である． $2^ny+1\equiv2y+1\pmod{(2y+1)^2}$ により，$\dfrac{2^ny+1}{2y+1}$ は整数であり，かつ $2y+1$ と互いに素である． さらに，$2y+1$ を割り切らない $x^{2y+1}$ 以下の任意の素数 $q$ について $2^ny+1\equiv2y+1\not\equiv0\pmod q$ であるから， $\dfrac{2^ny+1}{2y+1}$ の素因数は $x^{2y+1}$ より大きい． また，$\dfrac{2^ny+1}{2y+1}-1\equiv-\dfrac{2y}{2y+1}\not\equiv0\pmod{2^{v_2(2y)+1}}$ であるから， $\dfrac{2^ny+1}{2y+1}$ の素因数 $p$ であって $v_2(p-1)\leq v_2(2y)$ をみたすものが存在する． 仮定により $x^{2^n}\equiv1\pmod p$ なので，$x^{2^{v_2(2y)}}-1\equiv0\pmod p$，すなわち $x^{2y}-1\equiv0\pmod p$． しかし，$p\gt x^{2y+1}$ なので，これは $x=1$ を意味する．

$p=q$ のときは明らかに不適なので，対称性により $p\gt q$ として考えれば十分． $p^p+q^q+1\equiv q^q+1\equiv0\pmod p$ だから $(p-1,q)=q$ または $q+1\equiv0\pmod p$ となり， いずれにせよ $p\gt q$ から $p=q+1$，すなわち $(p,q)=(3,2)$ になる． よって，求める解は $(p,q)=(3,2),(2,3)$．

結論から言えば存在しないのだが， この手の問題は一つうまく構成するだけというオチである可能性もあるので， 本当に構成が思いつかないかは注意深く確かめた方がよい．

さて，構成を作ろうとしてもなぜうまくいかないのかを考えてみると， それぞれの文字が $11$ で割り切れる回数などをうまく調節しようとしても，どうにもできないのである．

とにかく，$n_i^{2020}+n_{i+1}^{2019}$ が $11$ 以外の素因数をもつはずであることを示せばよいが， 一つを単独で見ても一筋縄にはいかないので，任意の $i$ で $11$ のべきだったとしてどうなるかを見ないといけない．

$n_1,n_2,\ldots,n_{2022}$ はいずれも $11$ で割り切れないとしてよい． 対称性により，$i$ を動かしたときに $n_i^{2020}+n_{i+1}^{2019}$ のうち最小のものが $n_1^{2020}+n_2^{2019}=11^k$ であったとすると， 任意の $i$ で $n_i^{2020}\equiv-n_{i+1}^{2019}\pmod{11^k}$ が成立する． いま $n_1^{2020^{2022}}\equiv-n_1^{2019^{2022}}\pmod{11^k}$ だが， $n_1$ は $11$ で割り切れないので $n_1^{2020^{2022}-2019^{2022}}\equiv-1\pmod{11^k}$．

さて，$2020^{2022}-2019^{2022}$ は $11,10$ と互いに素であることがわかるので，$n_1\equiv-1\pmod{11^k}$ である． よって $n_1\geq 11^k-1$ だが，$(11^k-1)^{2020}+1\leq n_1^{2020}+n_2^{2019}=11^k$ であるから矛盾．

偶奇を見ることで $p,r $の一方は $2$ であり，大小の制約とあわせて $p=2$ とわかる．このとき， $$2^s-s^q=3-(s^q-r^q)=3-(s-r)(s^{q-1}+\cdots+r^{q-1})\lt 3-2\cdot2\lt 0$$ から $s\lt q\log_2s$ が得られる． また，$2^s\gt 2^s-3=r^q$ から $s\gt q\log_2 r$ がわかる．

与式を $2(2^{s-1}-1)=r^q+1$ と変形する． フェルマーの小定理から左辺は $s$ で割り切れるので，$r^q\equiv-1\pmod s$. したがって，$s\mid r+1$ または $s\equiv1\pmod q$ となる． 大小の制約から前者は成立せず，$s$ が奇数であることとあわせて $s=2kq+1$ とかける． 改めて与式は $2(2^{2kq}-1)=r^q+1$ となり，特に $2(2^k-1)(2^k+1)\mid r^q+1$．

さて，以下の不等式評価により，$2(2^k-1)(2^k+1)$ の素因数 $a$ は $q$ 以下である： $$2^k-1<2^k+1\lt 2^{\frac{s}{2q}}+1\lt 2^{\frac{\log_2s}{2}}+1 =\sqrt{s}+1 \lt \dfrac{s}{\log_2s}+1\lt q+1.$$ このとき，$a\mid r^q+1$ は $a\mid r^{(q,a-1)}+1=r+1$ を意味するので，$2(2^k-1)(2^k+1)\mid r+1$ である （$v_q\bigl(2(2^k-1)(2^k+1)\bigr)\leq1$ に注意）．ここで， $$2(2^k-1)(2^k+1)=2^{\frac{s-1}q+1}-2\gt 2^{\frac sq}-2\gt r-2$$ により $2(2^k-1)(2^k+1)\geq r-1\gt \dfrac{r+1}3$ であるので，$2(2^k-1)(2^k+1)=r+1$ が成立する．

これを $s\gt q\log_2 r$ に代入すると $2kq+1\gt q\log_2(2^{2k+1}-3)$．よって， $$1\gt q\log_2\left(2-\dfrac3{2^{2k}}\right)\geq q\log_2\dfrac54.$$ これにより $q=3$ となる． このとき $s\lt q\log_2s$ から $(p,q,r,s)=(2,3,5,7)$ に絞られ，これは条件をみたす．