整数論の問題

中国剰余定理により
$$(\mathbb{Z}/1001\mathbb{Z}{)}^{\times }\cong (\mathbb{Z}/7\mathbb{Z}{)}^{\times }\times (\mathbb{Z}/11\mathbb{Z}{)}^{\times }\times (\mathbb{Z}/13\mathbb{Z}{)}^{\times }$$
であり、素数 $p$ を法とする既約剰余類群は原始根の存在により位数 $p-1$ の巡回群なので、右辺は $C_6\times C_{10}\times C_{12}$ と同型である。$a$ に対応する成分を $(\alpha ,\beta ,\gamma )$ とすると、$a$ の位数は $\mathrm{lcm}(\mathrm{ord}\alpha ,\mathrm{ord}\beta ,\mathrm{ord}\gamma )$ である。

位数 $d$ の元は巡回群 $C_n$（$d\mid n$）にちょうど $\phi (d)$ 個ある。lcm が $12=2^2\cdot 3$ になる条件を考える。
- $\mathrm{ord}\beta \mid 10$ で、lcm に $5$ が入ってはいけないので $\mathrm{ord}\beta \in \{1,2\}$：$\phi (1)+\phi (2)=2$ 通り。
- $4$ で割り切れる位数をもてるのは $C_{12}$ の成分だけなので $\mathrm{ord}\gamma \in \{4,12\}$。
- $\mathrm{ord}\alpha \mid 6$ は常に $12$ を割る。

(i) $\mathrm{ord}\gamma =12$（$\phi (12)=4$ 個）のとき、$\alpha$ は任意で $6$ 個。$4\cdot 6\cdot 2=48$ 個。
(ii) $\mathrm{ord}\gamma =4$（$\phi (4)=2$ 個）のとき、因数 $3$ は $\alpha$ から来る必要があり $\mathrm{ord}\alpha \in \{3,6\}$：$\phi (3)+\phi (6)=4$ 個。$2\cdot 4\cdot 2=16$ 個。

合計 $48+16=64$ 個。

$1\le a\le 1000$ で $\gcd (a,1001)=1$ の $a$ は、$(\mathbb{Z}/1001\mathbb{Z}{)}^{\times }$ の元をちょうど 1 回ずつ表す。中国剰余定理より
$(\mathbb{Z}/1001{)}^{\times }\cong (\mathbb{Z}/7{)}^{\times }\times (\mathbb{Z}/11{)}^{\times }\times (\mathbb{Z}/13{)}^{\times }\cong C_6\times C_{10}\times C_{12}$（巡回群）。

巡回群 $C_n$ のうち $x^m=1$ を満たす元の個数は $\gcd (m,n)$。

・位数が 12 の約数: $\gcd (12,6)\gcd (12,10)\gcd (12,12)=6\cdot 2\cdot 12=144$。
・位数が 6 の約数: $\gcd (6,6)\gcd (6,10)\gcd (6,12)=6\cdot 2\cdot 6=72$。
・位数が 4 の約数: $\gcd (4,6)\gcd (4,10)\gcd (4,12)=2\cdot 2\cdot 4=16$。
・位数が 2 の約数: $\gcd (2,6)\gcd (2,10)\gcd (2,12)=2\cdot 2\cdot 2=8$。

位数がちょうど 12 の元は、位数が 12 の約数であり、かつ 6 の約数でも 4 の約数でもないもの（12 の真の約数 $1,2,3,4,6$ は 6 か 4 の約数）。位数が 6 の約数または 4 の約数である元の個数は包除原理で $72+16-8=80$。

よって $144-80=64$。

確かめ: 位数 12 になるのは、各成分の位数の最小公倍数が 12 のとき。$C_6$ の位数は $1,2,3,6$、$C_{10}$ は $1,2,5,10$ ですが 5 は 12 を割らないので位数 $1,2$ のみ（元は 1 と 1 個ずつ）、$C_{12}$ は $1,2,3,4,6,12$。位数 12 には 4 の約数でない因子 3 と 4 が必要で、これは $C_{12}$ で位数 4 か 12 の元、かつ 3 を含む成分が必要という条件の数え上げと整合し 64 を得る。