1
大学数学基礎問題
文献あり

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

478
0
$$$$

数学系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$の場合でも,もっと簡単に計算できる方法を思いついた方がいましたら是非教えてください.

参考文献

投稿日:202395
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

Mathお
Mathお
42
5548

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中