整数論の問題

既約剰余類群の分解

中国剰余定理より、$\gcd (a,2024)=1$ である $a\mathrm{mod}2024$ と、組
$$(a\mathrm{mod}8,a\mathrm{mod}11,a\mathrm{mod}23)$$
は 1 対 1 に対応する。また $a^k\equiv 1(\mathrm{mod}2024)$ であることと、$a^k\equiv 1$ が法 $8,11,23$ のそれぞれで成り立つことは同値である。

したがって、$a$ の法 $8,11,23$ での位数をそれぞれ $d_1,d_2,d_3$ とすると
$${\mathrm{ord}}_{2024}(a)=\mathrm{lcm}(d_1,d_2,d_3)$$
となる。

各法での構造は次のとおりである。
- 法 $8$：既約剰余は $1,3,5,7$ であり、$3^2=9,5^2=25,7^2=49$ はいずれも $8$ で割ると $1$ 余る。よって各元の位数は $1$ または $2$ である（位数 $1$ が $1$ 個、位数 $2$ が $3$ 個）。
- 法 $11$：$11$ は素数なので原始根が存在し、既約剰余類群は位数 $10$ の巡回群である。$d\mid 10$ に対し、位数 $d$ の元はちょうど $\phi (d)$ 個ある。
- 法 $23$：同様に位数 $22$ の巡回群であり、$d\mid 22$ に対し、位数 $d$ の元は $\phi (d)$ 個ある。

$L$ の決定

すべての $a$ で $a^L\equiv 1$ となるのは、$L$ が $d_1,d_2,d_3$ のとりうるすべての値の倍数であるときである。$d_1$ の最大は $2$、$d_2$ の最大は $10$（原始根）、$d_3$ の最大は $22$（原始根）で、とりうる値はそれぞれ $2,10,22$ の約数なので
$$L=\mathrm{lcm}(2,10,22)=110$$
である。

$N$ の決定

$110=2\cdot 5\cdot 11$ である。$\mathrm{lcm}(d_1,d_2,d_3)=110$ となる条件を素因数ごとに調べる。

- 素因数 $5$：$5$ で割り切れうるのは $d_2$ だけである（$d_1\mid 2$、$d_3\mid 22$）。よって $d_2\in \{5,10\}$ が必要で、そのような法 $11$ の剰余の個数は
$$\phi (5)+\phi (10)=4+4=8$$
- 素因数 $11$：$11$ で割り切れうるのは $d_3$ だけである。よって $d_3\in \{11,22\}$ が必要で、その個数は
$$\phi (11)+\phi (22)=10+10=20$$
- 素因数 $2$：$d_1,d_2,d_3$ の少なくとも 1 つが偶数であればよい。

上の 2 条件（$5\mid d_2$, $11\mid d_3$）をみたす組 $(a\mathrm{mod}8,a\mathrm{mod}11,a\mathrm{mod}23)$ の総数は
$$4\times 8\times 20=640$$
である。このうち $2$ の因子がどこにも現れない、すなわち $(d_1,d_2,d_3)=(1,5,11)$ となるもの（位数 $55$）の個数は
$$1\times \phi (5)\times \phi (11)=1\times 4\times 10=40$$
である。よって
$$N=640-40=600$$

別の数え方による確認

既約剰余の総数は $\phi (2024)=4\cdot 10\cdot 22=880$ であり、すべての位数は $110$ の約数である。位数が $110$ の真の約数になるものを包除原理で除く。$a^m\equiv 1$ をみたす元の個数は、各成分で $d_i\mid m$ となる元の個数の積である。

• 位数が $55$ の約数：$1\cdot 5\cdot 11=55$ 個
• 位数が $22$ の約数：$4\cdot 2\cdot 22=176$ 個
• 位数が $10$ の約数：$4\cdot 10\cdot 2=80$ 個
• 位数が $11$ の約数：$1\cdot 1\cdot 11=11$ 個
• 位数が $5$ の約数：$1\cdot 5\cdot 1=5$ 個
• 位数が $2$ の約数：$4\cdot 2\cdot 2=16$ 個
• 位数が $1$：$1$ 個

包除原理より
$$N=880-(55+176+80)+(11+5+16)-1=880-311+32-1=600$$

2 つの方法の結果は一致する。よって $(L,N)=(110,600)$ である。

中国剰余定理より $(\mathbb{Z}/2024{)}^{\times }\cong (\mathbb{Z}/8{)}^{\times }\times (\mathbb{Z}/11{)}^{\times }\times (\mathbb{Z}/23{)}^{\times }\cong (C_2\times C_2)\times C_{10}\times C_{22}$。

指数 $L$ は各因子の指数の最小公倍数なので $L=\mathrm{lcm}(2,10,22)=110$。

位数がちょうど $110=2\cdot 5\cdot 11$ である元 $(x,y,z)$ を数える。
- 5 の因子が必要なので $y$ の位数は 5 または 10。これは $4+4=8$ 個。
- 11 の因子が必要なので $z$ の位数は 11 または 22。これは $10+10=20$ 個。
- $x$ は任意で 4 通り。

ここまでで $8\cdot 20\cdot 4=640$ 個。

ただし 2 の因子も必要である。2 の因子がない場合は $x=e$（1 通り）、$y$ の位数 5（4 通り）、$z$ の位数 11（10 通り）で $40$ 個。

よって $N=640-40=600$。

検算：位数 2 の部分が全て自明でない元の個数は、全体 $4\cdot 10\cdot 22=880$ のうち位数が 110 の約数でないものは存在しない（指数が 110 のため）。上の数え方で位数 55 の元が 40 個、位数 110 の元が 600 個となり、矛盾はない。

答え：$(L,N)=(110,600)$。