文献あり

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

516

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

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

解答を表示

100

と互いに素な

100

以下の自然数の集合を

S (= (Z / 100 Z)^{\times})

とする．
多項式

f (x) := \prod_{a \in S} (1 + x^{a})

の

x^{n}

の係数が,

S

の空でない部分集合で，和が

n

となるものの個数を表す．
また，

f (x) = \sum_{n = 0}^{1999} a_{n} x^{n}

とする．

ζ

を

1

の原始

100

乗根とすると，

n

が

100

の倍数のとき，

\sum_{k = 0}^{99} (ζ^{n})^{k} = \sum_{k = 0}^{99} 1^{k} = 100

であり，

n

が

100

の倍数でないとき，

ζ^{n}

は

1

でない

x^{100} - 1

の根であるため，

(ζ^{n})^{100} - 1 = (ζ^{n} - 1) (1 + ζ^{n} + (ζ^{n})^{2} + . . . + (ζ^{n})^{99}) = 0

から，

\sum_{k = 0}^{99} (ζ^{n})^{k} = 0

となる．よって，

\frac{1}{100} \sum_{k = 0}^{99} f (ζ^{k}) = \frac{1}{100} \sum_{n = 0}^{1999} a_{n} \sum_{k = 0}^{99} (ζ^{n})^{k} = a_{0} + a_{100} + a_{200} + . . . + a_{1900} .

したがって，求める値は

\frac{1}{100} \sum_{k = 0}^{99} \prod_{a \in S} (1 + ζ^{k a})

となる．

ここで，

d \in Z / 100 Z

に対して，

S_{d} := {d \cdot a \in Z / 100 Z ∣ a \in S}

とおく．

Z / 100 Z = \underset{d ∣ 100}{∐} S_{d} = S ⊔ S_{2} ⊔ S_{4} ⊔ S_{5} ⊔ S_{10} ⊔ S_{20} ⊔ S_{25} ⊔ S_{50} ⊔ {0}

となることに注意する．さらに，

k \in S_{d}

のとき，ある

b \in S

が存在して，

k = d \cdot b

と書ける．

b \in S

より，写像

S \to S

a \mapsto b \cdot a

は全単射となる．よって，

\prod_{a \in S} (1 + ζ^{k a}) = \prod_{a \in S} (1 + ζ^{d b a}) = \prod_{a \in S} (1 + ζ^{d a})

より，

\frac{1}{100} \sum_{k = 0}^{99} \prod_{a \in S} (1 + ζ^{k a}) = \frac{1}{100} \sum_{d | 100} | S_{d} | \prod_{a \in S} (1 + ζ^{d a})

となる．

また，

100

に対する円分多項式を

ϕ

とすると，

ϕ (x) = \prod_{a \in S} (x - ζ^{a})

と書けるため，

\prod_{a \in S} (1 + ζ^{d a}) = \prod_{j = 1}^{d} \prod_{a \in S} (e^{\frac{π i}{d} (2 j - 1)} - ζ^{a}) = \prod_{j = 1}^{d} ϕ (e^{\frac{π i}{d} (2 j - 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)

と因数分解できて，

| (Z / 100 Z)^{\times} | = 40

から，

\dim ϕ = 40

より，

ϕ (x) = x^{40} - x^{30} + x^{20} - x^{10} + 1

が分かる．よって，

ϕ (e^{π i}) = ϕ (- 1) = 1,

\prod_{j = 1}^{2} ϕ (e^{\frac{π i}{2} (2 j - 1)}) = ϕ (i) ϕ (- i) = 5 \cdot 5 = 25,

\prod_{j = 1}^{4} ϕ (e^{\frac{π i}{4} (2 j - 1)}) = \prod_{j = 1}^{4} (1 - (- i^{2 j - 1}) + (- 1) - i^{2 j - 1} + 1) = 1,

\prod_{j = 1}^{5} ϕ (e^{\frac{π i}{5} (2 j - 1)}) = \prod_{j = 1}^{5} (1 - 1 + 1 - 1 + 1) = 1,

\prod_{j = 1}^{10} ϕ (e^{\frac{π i}{10} (2 j - 1)}) = \prod_{j = 1}^{10} (1 - (- 1)^{2 j - 1} + 1 - (- 1)^{2 j - 1} + 1) = 5^{10},

\prod_{j = 1}^{20} ϕ (e^{\frac{π i}{20} (2 j - 1)}) = \prod_{j = 1}^{20} (1 - i^{6 j - 3} + (- 1)^{2 j - 1} - i^{2 j - 1} + 1) = 1.

　
ここで，

S

の半分の元が

4

で割って

1

余り，もう半分の元が

4

で割って

3

余ることから，

\prod_{a \in S} (1 + ζ^{25 a}) = \prod_{a \in S} (1 + i^{a}) = ((1 - i) (1 + i))^{20} = 2^{20} .

さらに，

\prod_{a \in S} (1 + ζ^{50 a}) = \prod_{a \in S} (1 + (- 1)^{a}) = 0

となる．
また，

\prod_{a \in S} (1 + ζ^{100 a}) = \prod_{a \in S} (1 + 1) = 2^{40} .

したがって，求める値は

\begin{aligned} \frac{1}{100} \sum_{d | 100} | S_{d} | \prod_{a \in S} (1 + ζ^{d a}) \\ = \frac{1}{100} (40 \cdot 1 + 20 \cdot 25 + 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{aligned}

= 10995527880.

※今回は

100

の約数個々について計算をする部分がありましたが，この問題を

100

ではなく，一般の自然数

N

にすると，

ϕ_{N}

を

N

に対する円分多項式として，答えは

\frac{1}{N} \sum_{d | N} | d \cdot (Z / N Z)^{\times} | \prod_{j = 1}^{d} ϕ_{N} (e^{\frac{π i}{d} (2 j - 1)})

となります．この値について明示的に計算できる方法をご存知の方がいましたら是非教えてください．
また，

100

の場合でも，もっと簡単に計算できる方法を思いついた方がいましたら是非教えてください．

参考文献

[1]

激ムズ数え上げパズルと驚きの解法, 閲覧日 2023年8月23日, https://www.youtube.com/watch?v=FR6_JK5thCY&t=1669s

投稿日：2023年9月5日

この記事を高評価した人

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

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

Mathお

6364

他の人のコメント

コメントはありません。

読み込み中

Mathお

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

参考文献