2026年10月29日の解答

答. \(m\) が奇数であるか，または \(m=2k\)（\(k\) は奇数）で \(k\) のすべての素因数が \(\pm1 \pmod 8\) に合同であるとき，かつそのときに限る。 したがって \(4\nmid m\) は必要であるが十分ではない。実際 \(m=6,10,30\) は条件をみたさず，\(m=2,14,34,98\) はみたす。

第1段：4 の倍数は不可. \(n\) が奇数ならば \(n^n\) は奇数である。\(n\) が偶数ならば \(n\ge2\) より \(4\mid n^n\) である。いずれにせよ \(n^n\not\equiv2\pmod 4\) であるから，\(4\nmid m\) でなければならない。

第2段：偶数の場合は平方剰余の条件が現れる. \(m=2k\)（\(k\) は奇数）とする。\(2\mid n^n-2\) より \(n^n\) は偶数，よって \(n\) は偶数であり，\(n^n=\bigl(n^{n/2}\bigr)^2\) は平方数となる。ゆえに \(k\) の任意の素因数 \(p\) に対して \(2\equiv n^n\) は \(p\) を法とする平方剰余であり，平方剰余の相互法則の第二補充法則より \(p\equiv\pm1\pmod 8\) を得る。ここが本問の罠である。第1段の後に \(4\nmid m\) で止めたくなるが，\(3\) を法として \(2\) は平方剰余でないので，すでに \(m=6\) が不可である。

第3段：素朴な構成が失敗する理由. 奇素数 \(p\) と \(p\) と互いに素な \(n\) に対し，\(n^n \bmod p^e\) は底としての \(n\bmod p^e\) と指数としての \(n\bmod\varphi(p^e)=p^{e-1}(p-1)\) で決まり，したがって \(n\bmod p^e\) と \(n\bmod(p-1)\) のみで決まる。\(n\) の二つの役割は一つの素数の中で結びついており（\(p^{e-1}\) を法とする剰余は底と指数の両方に関わる），さらに素数をまたいでも結びついている（\(p-1\) を法とする剰余は \(p-1\) を割るより小さい素数を法とする \(n\) の剰余を含む）。たとえば \(n\equiv2\pmod m\) と \(n\equiv1\pmod{\operatorname{ord}_m2}\) を同時に課す方法は，\(m=21\) ですでに破綻する。\(\operatorname{ord}_{21}2=6\) であり，二つの条件が \(3\) を法として矛盾するからである。対処法は，一つの素数の中では持ち上げの補題，素数をまたいでは素数を小さい順に処理することである。

第4段：持ち上げの補題. \(p\) を奇素数，\(j\ge1\) とし，\(n_0\) は \(p\nmid n_0\) かつ \(n_0^{n_0}\equiv2\pmod{p^j}\) をみたすとする。\(n_0^{n_0}\equiv2+s\,p^j\pmod{p^{j+1}}\) とおく。\(\delta=t\,p^j(p-1)\)，\(n'=n_0+\delta\) とおくと，\(n'\equiv n_0\pmod{\varphi(p^{j+1})}\) かつ \(n'\) は \(p\) と互いに素であるから \(n'^{\,n'}\equiv n'^{\,n_0}\pmod{p^{j+1}}\) である。\(p^{2j}\mid\delta^2\) に注意して二項定理を用いれば \[n'^{\,n_0}=(n_0+\delta)^{n_0}\equiv n_0^{n_0}+n_0\cdot n_0^{n_0-1}\delta=n_0^{n_0}(1+\delta)\equiv2+s\,p^j-2t\,p^j\pmod{p^{j+1}}\] を得る。ここで \(n_0^{n_0}\equiv2\pmod p\) と \(p-1\equiv-1\pmod p\) を用いた。\(p\) は奇数なので \(t\equiv s/2\pmod p\) と選べば \(n'^{\,n'}\equiv2\pmod{p^{j+1}}\) となり，しかも \(n'\equiv n_0\pmod{p(p-1)}\) である。これを繰り返せば，\(p\nmid n_0\) なる \(p\) を法とする解から，任意の \(e\) に対して \(n_p\equiv n_0\pmod{p(p-1)}\) かつ \(n_p^{n_p}\equiv2\pmod{p^e}\) なる \(n_p\) が得られる。

第5段：素数を小さい順に処理する構成. \(m\) は答の条件をみたすとし，その奇数部分を \(k=p_1^{e_1}\cdots p_r^{e_r}\)（\(p_1<\dots<p_r\)），\(L=\operatorname{lcm}(p_i-1)\) とおく。中国剰余定理により，\(n\) の剰余を素数ごとに定めていく。

まず \(k\) を割らない素数での剰余を定める。\(2^{\max(2,v_2(L))}\) を法として，\(m\) が奇数なら \(n\equiv1\)，\(m\) が偶数なら \(n\equiv2\) とする。\(L\) を割り \(k\) を割らない各奇素数 \(q\) については \(n\equiv1\pmod{q^{v_q(L)}}\) とする。

次に \(p=p_1,p_2,\dots,p_r\) を小さい順に扱う。\(p-1\) の素因数はすべて \(p\) より小さいので，\(2\) であるか，\(k\) を割らない素数であるか，すでに処理した \(p_i\) であり，いずれの場合も \(L\) におけるその素数の最高べきを法とする \(n\) の剰余はすでに定まっている。よって \(c:=n\bmod(p-1)\) はすでに決まっている。これまでに定めた奇素数での剰余はすべて単数であるから，\(m\) が奇数なら \(\gcd(c,p-1)=1\)，\(m\) が偶数なら \(\gcd(c,p-1)=2\) である（このとき \(c\) は偶数で，\(4\mid p-1\) ならば \(c\equiv2\pmod4\) である）。

\(\alpha^c\equiv2\pmod p\) を解く。\(\gcd(c,p-1)=1\) ならば \(cc'\equiv1\pmod{p-1}\) なる \(c'\) をとり \(\alpha=2^{c'}\) とすればよい。\(\gcd(c,p-1)=2\) ならば，原始根 \(g\) により \(2\equiv g^w\) と書く。\(p\equiv\pm1\pmod8\) より \(2\) は平方剰余なので \(w\) は偶数であり，\(cu\equiv w\pmod{p-1}\) は解をもち，\(\alpha=g^u\) が条件をみたす。\(n_0\equiv\alpha\pmod p\)，\(n_0\equiv c\pmod{p-1}\) とおけば \(p\nmid n_0\) かつ \(n_0^{n_0}\equiv\alpha^c\equiv2\pmod p\) である。第4段により \(n_p\equiv c\pmod{p-1}\) かつ \(n_p^{n_p}\equiv2\pmod{p^e}\) なる \(n_p\) を得る。そこで \(n\equiv n_p\pmod{p^{\max(e,v_p(L))}}\)（\(n_p\bmod p^e\) の任意の持ち上げ）と定める。\(p\) は新しい素数なので，これはそれまでの条件と両立する。新たな \(p\) を法とする剰余は単数 \(\alpha\) であるから，上で用いた互いに素という性質も保たれる。

第6段：結論. こうして得た \(n\) と各 \(p^e\,\|\,k\) について，\(n\equiv n_p\pmod{p^e}\) かつ \(n\equiv c\equiv n_p\pmod{p-1}\) であるから \(n\equiv n_p\pmod{p^e(p-1)}\) となり，\(n^n\equiv n_p^{n_p}\equiv2\pmod{p^e}\) を得る。中国剰余定理により \(k\mid n^n-2\) である。\(m\) が奇数ならこれで終わる。\(m=2k\) のときは \(n\) が偶数なので \(n^n-2\) は偶数であり，\(2k\mid n^n-2\) となる。第1段・第2段とあわせて答が示された。

検証. \(n^n\bmod m\) の一周期にわたる全数探索により，\(m\le1200\) で条件をみたす \(m\) の集合が上の記述とちょうど一致することを確かめた。また第4段・第5段の構成を実装し，\(2\cdot10^5\) までの無作為な \(m\) や \(2\cdot31^4\cdot7\)，\(3^5\cdot5^3\cdot7^2\cdot11\cdot13\) などを含む 3300 個の条件をみたす \(m\) すべてについて，正しい \(n\) が得られることを確認した。