「3の100乗を19で割ったあまりは？」を４通りの方法で計算する - tsujimotterのノートブック

この記事は 日曜数学 Advent Calendar 2015 の 8日目の記事です。（7日目：京大特色入試, コインの問題を解く | kinebuchitomo） ニコニコ動画の「数学」タグを検索するのが日課の日曜数学者 tsujimotter です。 「数学」で検索すると、本当にいろいろな動画が見つかるのです。ぜひお時間あるときに試してみてください。 日曜数学 Advent Calendar ８日目の本日は、そんなニコニコ動画で見つけた動画から１つ、みなさんにご紹介したいと思います。 今回ご紹介したいのは、初音ミクが歌うボカロ曲です。タイトルは 「 を で割ったあまりは？」 です。そのタイトル通り、まさに数学の問題をテーマとした珍しい曲です。まずは、ぜひリンク先の動画をご覧ください。 tsujimotter は、心地よいメロディーが素敵な曲だと思いました。この記事を書いている最中、バッ

[tsujimotter]

↓ブコメの方、誤植の報告ありがとうございます。 9 も 19 の平方剰余です。早速訂正いたしました。

[amori]

暗算可能な訂正版(^^;; 3^100の指数を2の冪乗に分解→3^(4+32+64) 3の冪乗mod 19の自乗を繰り返すと、3^2=9,3^4=5,3^8=6,3^16=-2,3^32=4,3^64=-3 よって3^100=5×4×(-3)=1×(-3)=16 mod 19 これが自乗繰り返し法だわな

[keloinwell]

平方剰余の相互法則の話は素数夜曲で読んだ。整数論の本としてもLISPの入門書としても良い本です

[blueboy]

初等的に解く。　3^3 = 27 = 19 + 8　ゆえに 8 に落とせる。8^3 = 512 = 19 * 26 + 18 ゆえに 18 に落とせる。 3^100 = 3^99 * 3 ≡ 8^33 * 3 ≡ 18^11 * 3 ≡ (-1)^11 * 3 ≡ (-1) * 3 ≡ -3 ≡ 16　　　　　　　　Q.E.D.

[kitamati]

数学オンチのワイには“平方剰余の相互法則”がシュタゲのサブタイに見えてしまって誠に申し訳ありません。

[eieitaro]

3^100 (mod 19) =(3^2)^50 =9^50 =(19-10)^50 ≡(-10)^50 =10^50 =100^25 =(19×5+5)^25 ≡5^25 =5×5^24 =5×25^12 =5×(19+6)^12 ≡5×6^12 =5×36^6 =5×(38-2)^6 ≡5×2^6 =10×32 =10×(38-6) ≡10×(-6) =-60 =16-19×4 ≡16

[Arison]

ごめんなさい。3のときにだけ、バカになるしかわかりませんでした。

[maidcure]

フェルマーの小定理はやったけど、使わなすぎて忘れてた

[vabo-space]

Excel使ったら3^20で桁溢れした、一覧できたので周期法則には気付けたけど。マシンパワー使った力任せもいいけど、スマートな解法見つけると嬉しくなる。｜3^100に対応できる整数型があるプログラム言語ってあったっけ？

[daruyanagi]

2番目までは大学受験のときにやった感じや

[hiduki001]

4番目も理解は出来たけど、数学好きな人って説明ヘタだよな、といつも思う。大学の教科書もめっちゃわかりにくかった。回路が違うんだろつか

[okagawa]

平方剰余の相互法則

[mankozooyork]

“「掛け算した結果のあまりは、もとの数のあまり同士を掛け算した結果に合同である」ということです。これが「あまりの世界」における重要な性質です。”

[razokulover]

"つまり「掛け算した結果のあまりは、もとの数のあまり同士を掛け算した結果に合同である」ということです。これが「あまりの世界」における重要な性質です。"

[yukkie_strike]

twitterで見かけた「20の13乗を18で割った余りは？」というテスト問題を力業で解いたあと、「３だったら？」「33乗だったら」と考え、高校数学を理解していない無力さに打ちひしがれてたところにこの記事を見つけた

[kishidonguri]

なんとか理解できた。かもしれない

[georgew]

平方剰余の相互法則 > ここまで来ると素人にはかえって複雑に過ぎる。

[frsatti]

フェルマーの小定理、平方剰余の相互法則

[copymattt]

初等的に解く。　3^3 = 27 = 19 8　ゆえに 8 に落とせる。

[ytsk]

おもしろい

[napsucks]

途中で暗算ユニットがスタックオーバーフロー起こしてゲロ吐いた

[habarhaba]

“数学ガール ”

[hi-zakky]

なるほど、分からん

[kniphofia]

分からない

[oktnzm]

"つまり"の使い方がえらい前衛的やな。／ブコメみてると絶対最小剰余の便利さがわかるな。

[mag-x]

数学ミュージックの報告大会を期待したが肩透かし。なので2曲紹介。「エラトステネスの篩」（中尾ミエ）は2355で登場。みんなのうたファンなら「算数チャチャチャ」（ペギー葉山）も押さえたい。

[sakidatsumono]

数IIで習う方法が抜けている?

[honebone]

なるほど！わからん！

[toshi123]

美しいなと息を漏らし、ただただ憧れる。そんな世界

[lazex]

最初の内「へぇ～」と思いながら読んでたけど途中から何言ってるのかわからなくなった

[aya_momo]

まだ読んでないけど、暗算でも出るぞ。/平方剰余の相互法則は、今回はたまたま使えるわけで、いつも有効であるわけではないことに注意。

[shiroimai]

楽しい！　……とか言いつつ、方法4は飛ばしました。ごめんなさい。

[u_wot_m8]

9も19の平方剰余ですよね？

[dekasasaki]

“この方法を 「テトラちゃん方式」 と呼んでいます。” せやな

[mamiske]

“この方法を 「テトラちゃん方式」 と呼んでいます。”

[lp008962]

ruby -e "p 3**100%19"　←なぜかむなしい。

[timetrain]

２番目は高校の夏休みエクストラ授業でやったなあ。すっかり忘れたよ。先生ごめん