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

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

516
0

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

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


解答を表示
100と互いに素な100以下の自然数の集合をS (=(Z/100Z)×)とする.
多項式f(x):=aS(1+xa)xnの係数が, Sの空でない部分集合で,和がnとなるものの個数を表す.
また,f(x)=n=01999anxnとする.
ζ1の原始100乗根とすると,n100の倍数のとき,k=099(ζn)k=k=0991k=100であり,
n100の倍数でないとき,ζn1でないx1001の根であるため,
(ζn)1001=(ζn1)(1+ζn+(ζn)2+...+(ζn)99)=0から,k=099(ζn)k=0となる.よって,
1100k=099f(ζk)=1100n=01999ank=099(ζn)k=a0+a100+a200+...+a1900.
したがって,求める値は1100k=099aS(1+ζka)となる.

ここで,dZ/100Zに対して,Sd:={daZ/100ZaS}とおく.
Z/100Z=d100Sd=SS2S4S5S10S20S25S50{0}
となることに注意する.さらに,kSdのとき,あるbSが存在して,k=dbと書ける.
bSより,写像SS: abaは全単射となる.よって,
aS(1+ζka)=aS(1+ζdba)=aS(1+ζda)より,
1100k=099aS(1+ζka)=1100d|100|Sd|aS(1+ζda)となる.

また,100に対する円分多項式をϕとすると,ϕ(x)=aS(xζa)と書けるため,
aS(1+ζda)=j=1daS(eπid(2j1)ζa)=j=1dϕ(eπid(2j1))となる.

ここで,x1001=(x50+1)(x501)であり,さらに
x50+1=(x10)5+1=(x10+1)(x40x30+x20x10+1)と因数分解できて,
|(Z/100Z)×|=40から,dim ϕ=40より,
ϕ(x)=x40x30+x20x10+1が分かる.よって,

ϕ(eπi)=ϕ(1)=1,

j=12ϕ(eπi2(2j1))=ϕ(i)ϕ(i)=55=25,

j=14ϕ(eπi4(2j1))=j=14(1(i2j1)+(1)i2j1+1)=1,

j=15ϕ(eπi5(2j1))=j=15(11+11+1)=1,

j=110ϕ(eπi10(2j1))=j=110(1(1)2j1+1(1)2j1+1)=510,

j=120ϕ(eπi20(2j1))=j=120(1i6j3+(1)2j1i2j1+1)=1. 
ここで,Sの半分の元が4で割って1余り,もう半分の元が4で割って3余ることから,

aS(1+ζ25a)=aS(1+ia)=((1i)(1+i))20=220.
さらに,aS(1+ζ50a)=aS(1+(1)a)=0となる.
また,aS(1+ζ100a)=aS(1+1)=240.
したがって,求める値は
1100d|100|Sd|aS(1+ζda)=1100(401+2025+201+81+4510+41+2220+240)=1100(240+221+4510+572)
=10995527880.

※今回は100の約数個々について計算をする部分がありましたが,この問題を100ではなく,一般の自然数Nにすると,ϕNNに対する円分多項式として,答えは
1Nd|N|d(Z/NZ)×|j=1dϕN(eπid(2j1))
となります.この値について明示的に計算できる方法をご存知の方がいましたら是非教えてください.
また,100の場合でも,もっと簡単に計算できる方法を思いついた方がいましたら是非教えてください.

参考文献

投稿日:202395
OptHub AI Competition

この記事を高評価した人

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

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

バッジはありません。
バッチを贈って投稿者を応援しよう

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

投稿者

Mathお
Mathお
44
6364

コメント

他の人のコメント

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