ガジェット通信 GetNews

見たことのないものを見に行こう
  • 『アントマン&ワスプ』エヴァンジェリン・リリーインタビュー「7歳の息子がワスプになりきっているのをこっそり見てしまったの!」
  • 『ゴースト・イン・ザ・シェル』のバトーさんを直撃! 原作愛がハンパなくて『イノセンス』制作を懇願するレベル
  • 『スーサイド・スクワッド』のダイバーシティを担う二人に直撃 「人間関係を構築するのに必要なこと教えよう」
  • 窪塚洋介が明かす未体験への挑戦と驚き 映画『沈黙-サイレンス-』でハリウッドデビューを飾る
  • コムアイ(水曜日のカンパネラ)インタビュー「お風呂に入った猫がシュッと細くなってしまうところが情けなくて愛しい」
  • 『ミッション:インポッシブル/フォール・アウト』サイモン・ペッグインタビュー「ベンジーがイーサンに唯一勝てる場所」とは?
  • 『マイティ・ソー バトルロイヤル』女戦士・ヴァルキリーを熱演! 声優・沢城みゆき「ロキ様ファンの方お友達になってください!」
  • 福士蒼汰&吉沢亮 2人の成長した部分とは?映画『BLEACH』撮り下ろしインタビュー
  • 『ジュマンジ』でタフな美女戦士を熱演! カレン・ギランの好きなゲームは「メガドライブ『ソニック・ザ・ヘッジホッグ3』」
  • 柄本佑が前田敦子を絶賛「“僕のあっちゃん、私のあっちゃん”にしたくなる魅力がある」
  • 野沢雅子×堀川りょう「ベジータがいるから悟空の存在がある」「ブルマとの馴れ初めの話が欲しい!」 映画『ドラゴンボール超 ブロリー』インタビュー
  • 『斉木楠雄のΨ難』インタビュー 佐藤二朗「橋本環奈が高校にいたら可愛すぎて男子は正気を保てないでしょ」
  • 『ハン・ソロ/スター・ウォーズ・ストーリー』で大大活躍中! チューバッカさん直撃インタビュー:動画  
  • 『パシフィック・リム:アップライジング』監督&ジョン・ボイエガに「ぼくのかんがえたさいきょうのかいじゅう」を見てもらった!
  • 『ブレードランナー 2049』“ジョイ”と“ラヴ”にインタビュー「SF映画は女子が観ちゃだめ? そんなわけないわ!」
  • 『ファンタビ』大切にしたのはティナがあの場面で「嫉妬心を出さないこと」キャサリン・ウォーターストン インタビュー

体験を伝える―『ガジェット通信』の考え方

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

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

「月を入力すると日を返す多項式」と中国剰余定理

今回は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次のページ
寄稿の記事一覧をみる

記者:

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

TwitterID: getnews_kiko

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