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

access_time create folderデジタル・IT 生活・趣味
「月を入力すると日を返す多項式」と中国剰余定理

今回はtsujimotterさんのブログ『tsujimotterのノートブック』からご寄稿いただきました。

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

「月を入力すると日を返す多項式」の話が、Twitterのタイムライン上で話題になりました。

「上司のおっさんに「月を入力すると日数が出るようにするにはどうすれば?」と聞かれたのでコレを教えてあげた心温まる話」『togetter』
https://togetter.com/li/1279312

どんな話題かというと、多項式 f(x) を以下のように定義したとき

多項式(1)

この f(X) に X=1,2,3,⋯,12 を代入すると、

   f(1)=31
   f(2)=28
   f(3)=31
     ⋮
   f(12)=31

となり、月を入力すると日を返す多項式になっています!すごい!

こんな多項式をいったいどうやって求めるんだろうかと、気になったかたはいるんじゃないかと思います。

これについては 中国剰余定理 が使えるということを、Iwao KIMURA ( @iwaokimura ) さんが、以下のツイートで教えてくださいました。

月を入力すると日を返す多項式.中国の剰余定理のいい例ですね.sagemathだとコマンド一発.

中国剰余定理は私の好きな定理の一つですが、このような応用があることはまったく知りませんでした。

とても興味深い話だったので、理屈を自分でも考えてみました。今日はそれを紹介したいと思います。

そもそも中国剰余定理とは

こんな問題を聞いたことはありませんか?

3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か

答えの一つをあげると 23 です。

実際、x=23 とすると

多項式2

が成り立ちますね。

実は、x≡23(mod105) であれば、x は上の3つの合同式を満たします。これが上の問題のすべての解となります。なお、105=3⋅5⋅7 です。

一般に、p1,p2,⋯,pM をそれぞれ互いに素な M 個の正整数としたとき

多項式3

を満たす整数 x は mod p1p2⋯pM の範囲で解を持ち、その解は一意に定まります。これが 中国剰余定理 です。

「中国剰余定理」という一風変わった名前がついていますが、この名前は中国の算術書「孫子算経」に由来します。この本に「3で割ると2余り、・・・」の問題とその解法が載っていたということです。

 
中国剰余定理で一意に定まる解を「具体的に」計算する関数が sagemath にあります。
「数論」『sage』
http://doc.sagemath.org/html/ja/tutorial/tour_numtheory.html

 

実際、先ほどの問題の式 (2) を元に計算する際は

CRT([2, 3, 2], [3, 5, 7])

と打ち込んでみてください。ちゃんと 23 という答えが返ってくると思います。

“CRT” は中国剰余定理の英語名 “Chinese Remainder Theorem” の頭文字をとったものですね。

多項式環の中国剰余定理

先ほどは中国剰余定理を「整数環」という特殊な状況で考えました。実は、中国剰余定理自体は、一般の環に対しても成り立つことが知られています。

多項式環で中国剰余定理を用いると、冒頭の11次の多項式を求めることができます。どういうことか、順を追って説明しましょう。

高校のときに習ったように、多項式 f(X) が f(a)=b を満たすとき

多項式4 f(X)=Q(X)(X−a)+b

が成り立ちます。ここで Q(X) は多項式です。式 (4) が成り立つことは、X=a を代入すればただちに確認できます。

1 2次のページ
access_time create folderデジタル・IT 生活・趣味

寄稿

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

TwitterID: getnews_kiko

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

スマホゲーム タラコたたき
ガジェ通制作ライブ
→ガジェ通制作生放送一覧