ガジェット通信 GetNews

見たことのないものを見に行こう
体験を伝える―『ガジェット通信』の考え方
面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]
ガジェ通制作ライブ
→ガジェ通制作生放送一覧

「月を入力すると日を返す多項式」と中国剰余定理(tsujimotterのノートブック)

式 (4) は次のように解釈することもできます。

多項式 f(X) を (X−a) で割った余りは b である。

このようにして多項式に「あまり」という概念が導入されます。

以上のように考えると f(1)=31 という式は、「f(X) を (X−1) で割ったあまりが 31 である」と言い換えることができます。

中国剰余定理の状況に近づいてきました。

つまり、冒頭の「月を入力すると日を返す多項式」を与える問題は
  f(X) を (X−1) で割ったあまりが 31 である
  f(X) を (X−2) で割ったあまりが 28 である
  f(X) を (X−3) で割ったあまりが 31 である
     ⋮
  f(X) を (X−12) で割ったあまりが 31 である
を同時に満たす f(X) を求めよ、という問題だったというわけです。

多項式環の中国剰余定理によると、このような f(X) は存在します。

実際、sagemathを使って f(X) を計算することができます。

R. = QQ[]
f = CRT([31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31], [x-1, x-2, x-3, x-4, x-5, x-6, x-7, x-8, x-9, x-10, x-11, x-12]); f

一行目は、多項式環 R として R=Q[X] を指定しています。有理数係数の多項式環ですね。そして、多項式環の変数を x と指定しています。この辺は「へぇ、こうやって書くのか」と思っていただければ十分です。

次の行がメインです。CRT関数の1つ目の変数に

[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

のようにあまりの情報を12個並べています。

CRT関数の2つ目の変数には、対応する mod を並べます。

[x-1, x-2, x-3, x-4, x-5, x-6, x-7, x-8, x-9, x-10, x-11, x-12]

これらの変数を CRT([…], […]) に入れて、結果を変数 f に格納して f を出力しています。

 
これによって、求める多項式を計算することができます。実際に先のコマンドを打ち込むと、次の結果が返ってくるはずです。

-11/907200*x^11 + 163/181440*x^1037/1260*x^9 + 13481/24192*x^82055371/302400*x^7 + 240683/4320*x^628268521/90720*x^5 + 85774775/72576*x^4446998571/151200*x^3 + 46351537/10080*x^2221017/56*x + 1416

たしかに、冒頭の多項式 (1) になっていますね!すごい!

これがちゃんと「日を返す多項式」になっていることは以下のように確認できるでしょう。

f(1)
f(2)
f(3)
f(4)
f(5)
f(6)
f(7)
f(8)
f(9)
f(10)
f(11)
f(12)

結果は次のようになるはずです。ぜひ確かめてみてください。

31
28
31
30
31
30
31
31
30
31
30
31

私の好きな中国剰余定理がこのような形で役に立つということが面白かったです!

楽しい話題をありがとうございました!

簡単ですが、今日はこの辺で。

おまけ

中国剰余定理はベルヌーイ数を計算するのにも役に立ちます!


「非正則素数チェッカー #日曜数学会 from Junpei Tsuji」『slideshare』
https://www.slideshare.net/junpeitsuji/ss-81062660

執筆: この記事はtsujimotterさんのブログ『tsujimotterのノートブック』からご寄稿いただきました。

寄稿いただいた記事は2018年10月27日時点のものです。

前のページ 1 2
寄稿の記事一覧をみる

記者:

ガジェット通信はデジタルガジェット情報・ライフスタイル提案等を提供するウェブ媒体です。シリアスさを排除し、ジョークを交えながら肩の力を抜いて楽しんでいただけるやわらかニュースサイトを目指しています。 こちらのアカウントから記事の寄稿依頼をさせていただいております。

TwitterID: getnews_kiko

  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。
スマホゲーム タラコたたき