文献あり

100と互いに素な相異なる100以下の自然数組の和が100の倍数になる場合の数

257

数学系Youtubeチャンネルである3Blue1Brownのこちらの動画 (和訳版)を見て，以下の発展問題を作成しました．

それぞれが$100$と互いに素で，相異なる$100$以下の自然数からなる組で，和が$100$の倍数となるものは何通りか．

解答を表示

$100$と互いに素な$100$以下の自然数の集合を$S ~(= (\mathbb{Z}/100\mathbb{Z})^{\times})$とする．
多項式$\displaystyle f(x) := \prod_{a \in S }(1+x^a)$の$x^n$の係数が, $S$の空でない部分集合で，和が$n$となるものの個数を表す．
また，$\displaystyle f(x) = \sum_{n=0}^{1999} a_n x^n$とする．
$\zeta$を$1$の原始$100$乗根とすると，$n$が$100$の倍数のとき，$\displaystyle \sum_{k=0}^{99} (\zeta^n)^k = \sum_{k=0}^{99} 1^k = 100$であり，
$n$が$100$の倍数でないとき，$\zeta^n$は$1$でない$x^{100} - 1$の根であるため，
$(\zeta^n)^{100} - 1 = (\zeta^n - 1) \big(1 + \zeta^n + (\zeta^n)^2 + ... +(\zeta^n)^{99} \big) = 0$から，$\displaystyle \sum_{k=0}^{99} (\zeta^n)^k = 0$となる．よって，
$\displaystyle \frac{1}{100} \sum_{k=0}^{99} f(\zeta^k) = \frac{1}{100} \sum_{n=0}^{1999} a_n \sum_{k=0}^{99} (\zeta^n)^k = a_0 + a_{100} + a_{200} + ... + a_{1900}.$
したがって，求める値は$\displaystyle \frac{1}{100} \sum_{k=0}^{99} \prod_{a \in S} (1 + \zeta^{k a})$となる．

ここで，$d \in \mathbb{Z}/100\mathbb{Z}$に対して，$S_d := \{d \cdot a \in \mathbb{Z}/100\mathbb{Z} \mid a \in S \}$とおく．
$\displaystyle \mathbb{Z}/100\mathbb{Z} = \coprod_{d \mid 100} S_d = S \sqcup S_2 \sqcup S_4 \sqcup S_5 \sqcup S_{10} \sqcup S_{20} \sqcup S_{25} \sqcup S_{50} \sqcup \{0\}$
となることに注意する．さらに，$k \in S_d$のとき，ある$b \in S$が存在して，$k = d\cdot b$と書ける．
$b \in S$より，写像$S \to S$: $a \mapsto b\cdot a$は全単射となる．よって，
$\displaystyle \prod_{a \in S} (1 + \zeta^{k a}) = \prod_{a \in S} (1 + \zeta^{d b a}) = \prod_{a \in S} (1 + \zeta^{d a})$より，
$\displaystyle \frac{1}{100} \sum_{k=0}^{99} \prod_{a \in S} (1 + \zeta^{k a}) = \frac{1}{100} \sum_{d | 100} |S_d| \prod_{a \in S} (1 + \zeta^{d a})$となる．

また，$100$に対する円分多項式を$\phi$とすると，$\displaystyle \phi(x) = \prod_{a \in S} (x - \zeta^a)$と書けるため，
$\displaystyle \prod_{a \in S} (1 + \zeta^{d a}) = \prod_{j=1}^{d} \prod_{a \in S}(e^{\frac{\pi i }{d}(2j-1) } - \zeta^a) = \prod_{j=1}^{d}\phi(e^{\frac{\pi i }{d}(2j-1) })$となる．

ここで，$x^{100} - 1 = (x^{50} + 1)(x^{50}-1)$であり，さらに
$x^{50}+1 = (x^{10})^5 + 1 = (x^{10} + 1)(x^{40} - x^{30} + x^{20} -x^{10} + 1)$と因数分解できて，
$|(\mathbb{Z}/100\mathbb{Z})^{\times}| = 40$から，$\mathrm{dim}~\phi = 40$より，
$\phi(x) = x^{40} - x^{30} + x^{20} -x^{10} + 1$が分かる．よって，

$\displaystyle \phi(e^{\pi i }) = \phi(-1) = 1,$

$\displaystyle \prod_{j=1}^2 \phi(e^{\frac{\pi i }{2} (2j-1)}) = \phi(i) \phi(-i) = 5 \cdot 5 = 25,$

$\displaystyle \prod_{j=1}^4 \phi(e^{\frac{\pi i }{4} (2j-1)}) = \prod_{j=1}^4 \big(1 -(-i^{2j-1}) + (-1) - i^{2j-1} + 1 \big) = 1,$

$\displaystyle \prod_{j=1}^5 \phi(e^{\frac{\pi i }{5} (2j-1)}) = \prod_{j=1}^5 \big(1 - 1 + 1 - 1 + 1 \big) = 1,$

$\displaystyle \prod_{j=1}^{10} \phi(e^{\frac{\pi i }{10}(2j-1)}) = \prod_{j=1}^{10} \big(1 -(-1)^{2j-1} + 1 - (-1)^{2j-1} + 1 \big) = 5^{10},$

$\displaystyle \prod_{j=1}^{20} \phi(e^{\frac{\pi i }{20}(2j-1)}) = \prod_{j=1}^{20} \big(1 -i^{6j-3} + (-1)^{2j-1} - i^{2j-1} + 1 \big) = 1.$　
ここで，$S$の半分の元が$4$で割って$1$余り，もう半分の元が$4$で割って$3$余ることから，

$\displaystyle \prod_{a \in S} (1 + \zeta^{25 a}) =\prod_{a \in S} (1 + i^a) = \big((1-i)(1+i)\big)^{20} = 2^{20}.$
さらに，$\displaystyle \prod_{a \in S} (1 + \zeta^{50 a}) = \prod_{a \in S} \big(1 + (-1)^{a} \big) = 0$となる．
また，$\displaystyle \prod_{a \in S} (1 + \zeta^{100 a}) = \prod_{a \in S} (1+1) = 2^{40}.$
したがって，求める値は
\begin{align*} &\frac{1}{100} \sum_{d | 100} |S_d| \prod_{a \in S} (1 + \zeta^{d a})\\ &= \frac{1}{100} (40\cdot 1 + 20\cdot25 + 20\cdot 1 + 8\cdot 1 + 4\cdot 5^{10} + 4\cdot 1 + 2\cdot 2^{20} + 2^{40})\\ &=\frac{1}{100}(2^{40} + 2^{21} + 4\cdot 5^{10} + 572) \end{align*}
$=10995527880.$

※今回は$100$の約数個々について計算をする部分がありましたが，この問題を$100$ではなく，一般の自然数$N$にすると，$\phi_N$を$N$に対する円分多項式として，答えは
$\displaystyle \frac{1}{N} \sum_{d | N} |d \cdot (\mathbb{Z}/N\mathbb{Z})^{\times}|\prod_{j=1}^{d}\phi_N(e^{\frac{\pi i }{d}(2j-1) })$
となります．この値について明示的に計算できる方法をご存知の方がいましたら是非教えてください．
また，$100$の場合でも，もっと簡単に計算できる方法を思いついた方がいましたら是非教えてください．