「3の100乗を19で割ったあまりは？」を４通りの方法で計算する

この記事は日曜数学 Advent Calendar 2015 の 8日目の記事です。（7日目：京大特色入試, コインの問題を解く | kinebuchitomo）

ニコニコ動画の「数学」タグを検索するのが日課の日曜数学者 tsujimotter です。

「数学」で検索すると、本当にいろいろな動画が見つかるのです。ぜひお時間あるときに試してみてください。

日曜数学 Advent Calendar ８日目の本日は、そんなニコニコ動画で見つけた動画から１つ、みなさんにご紹介したいと思います。

今回ご紹介したいのは、初音ミクが歌うボカロ曲です。タイトルは

「 $3^{100}$ を $19$ で割ったあまりは？」

です。そのタイトル通り、まさに数学の問題をテーマとした珍しい曲です。まずは、ぜひリンク先の動画をご覧ください。

tsujimotter は、心地よいメロディーが素敵な曲だと思いました。この記事を書いている最中、バックグラウンドでずっと流しています。筆が進みます。笑

歌詞も実は面白いので、注意深く聞いて欲しいなと思います。作者の方はどうやら数学科の学生さんらしく、この問題を解くためのヒントが歌詞に込められているそうです。

数学をテーマに曲を作ってしまうなんてすごいですね。私も見習いたいです。

テーマはもちろん、タイトルにもなっている以下の整数論の問題です。

（問題）
$3^{100}$ を $19$ で割ったあまりは？

問題自体もなかなか興味深いものです。

「ザ・整数論」といえる問題で、整数論が大好きな私は、これは解かずにいられませんでした。
せっかく解いたので、その結果を Advent Calendar の記事にしてしまおう、というのが執筆の経緯です。

ザ・整数論と言った通り、初等整数論の導入として実に都合のよい問題です。というのも、この問題は「素朴な方法から高度で洗練された方法まで、多様なアプローチによって解くことができる問題」だからです。問題を通して、重要な概念をいくつも習得することができます。

今回は、数ある解法の中から４つの解法で問題にアプローチしてみたいと思います。

方法１：地道に計算する（難易度：★☆☆☆☆）
方法２：周期性を使う（難易度：★★☆☆☆）
方法３：フェルマーの小定理を使う（難易度：★★★☆☆）
方法４：平方剰余の相互法則を使う（難易度：★★★★★）

単に解法を紹介するだけでなく、問題へのアプローチを通して、tsujimotter が思う整数論の魅力も併せてお伝えできればと思っています。

書き終わった今改めて読み返してみると、書きたいことがあまりにも多すぎて、文章がとてつもなく長くなっています。このへんは反省しないといけませんね。
とはいえ、どれも伝えたいことですし、できるだけわかりやすく丁寧に書いたつもりですので、どうかついてきてもらえると嬉しく思います。

というわけで、早速第１の方法に進んでいきましょう。

・・・（自分で解いてみたい方は、ここでストップして考えてみてください。）・・・

方法１：地道に計算する（難易度：★☆☆☆☆） *

方法１は、地道に 100 回の掛け算をしよう、という素朴なアプローチです。

問題をそのまま読むと、単純に $3$ を $100$ 回かけてから $19$ で割った余りをとればよいとわかります。 $100$ 回の掛け算は大変そうですが、しょせん有限の回数なので、できないことはないはずです。

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

テトラちゃんは、数学ガールに登場する主人公の後輩の女の子です。数学はあまり得意でないものの、持ち前の根気強さ（と主人公への一途な恋心）から、一生懸命地道に問題を解こうとします。この問題のように100回計算するなんてこともやってのけます。素朴でめんどうな方法であっても粘り強く取り組んでしまう姿勢は、主人公である「僕」を驚かせることも。詳しくはぜひ数学ガールシリーズを読んでみてください。

話を元に戻しましょう。

難しいように見える問題も、地道に考えていけばいつかは答えにたどり着けます。テトラちゃんのように頑張って計算していきましょう。

$3^{1} = 3$
$3^{2} = 9$
$3^{3} = 27$
$3^{4} = 81$
$3^{5} = 243$

・・・（中略）・・・

$3^{98} = 57264168970223481226273458862846808078011946889$
$3^{99} = 171792506910670443678820376588540424234035840667$
$3^{100} = 515377520732011331036461129765621272702107522001$

できました！

べき乗の計算だけあって、とんでもない数になりましたね。笑

さて、最後に得られた

$3^{100} = 515377520732011331036461129765621272702107522001$

という数を、 $19$ で割り算してみましょう。

すると、

$3^{100} \div 19 = 27125132670105859528234796303453751194847764315$ あまり $16$

となることがわかります。あまりが $16$ であることが計算できました！

（解答）
地道に計算すると， $3^{100}$ を $19$ で割った余りは $16$ である．

あっさりかかれてますが、「地道に計算すると」の部分に凄まじい苦労が含まれています。

たしかに解は得られました。とはいえ、ちょっとこの方法はつらいですよね。

歌詞でもこう書かれています。

いつもそう僕らは
答えを出すことおそれて
3の100乗計算するみたいに
遠回りしてしまうけど

君が思うより答えは
ずっと近くにあるからさ
あせらないで一歩ずつ
前に進んでいこう

やはり 100乗の計算は遠回りなのですね。

きっともっと洗練された方法があるはず、というわけで、あせらず一歩ずつ、次の方法に移りましょう。

方法２：周期性を使う（難易度：★★☆☆☆） *

方法１では、べき乗をそのまま計算しましたが、これはなかなか大変な作業でした。特に、指数が大きくなると計算結果が巨大な数になってしまうのが問題です。

問題を解決するために、記号を２つ導入したいと思います。 $\mod{}$ （モッド）と $\equiv$ （合同）という数学記号です。

先ほどの計算結果から、

$3^{4} = 81$

でした。これを $19$ で割ったあまりを考えましょう。

$3^{4} = 81 = 4\times 19 + 5$

ですから、あまりは $5$ ですね。このことを、記号を使って表すと、

$3^{4} \equiv 5 \pmod{19}$
（読み方） $3^4$ はモッド ${19}$ において $5$ に合同である

となります。日本語では $\mod{}$ のことを「法」と呼ぶこともあります。

一方、 $\equiv$ （合同）は「左右の数が等しい、あるいは同等のもの」であることを示す記号です。結局、この式は「 $\mod{19}$ という世界で考えれば、両者は同じものとみなせる」ということを言っています。

この $\mod{}$ の世界、すなわち「あまりの世界」を用いる最大の利点は「掛け算が保存される」ということです。

具体例を挙げましょう。

$3^4$ に $3$ をかけた $3^5$ は、 $\mod{19}$ において

$3^5 = 243 = 12 \times 19 + 15$

ですから、

$3^5 \equiv 15 \pmod {19} \tag {1}$

です。

一方、 $3^4 \equiv 5 \pmod{19}$ の右辺に $3$ をかけると、

$5 \times 3 \equiv 15 \pmod {19}$

となって、結果は $(1)$ 式に一致しますね。

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

したがって、 $3$ を一回掛けてからあまりを求めて、また一回かけてあまりを求めて、・・・という手順を繰り返しても、方法１と同じ結果が得られることになります。

実際にやってみましょう。

$3 \equiv 3 \pmod{19}$ 　　　　　　（ $3^1 \pmod {19}$ に合同）
$3\times 3 \equiv 9 \pmod{19}$ 　　　　（ $3^2 \pmod {19}$ に合同）
$9\times 3 \equiv 27 \equiv 8 \pmod{19}$ 　（ $3^3 \pmod {19}$ に合同）
$8\times 3 \equiv 24 \equiv 5 \pmod{19}$ 　（ $3^4 \pmod {19}$ に合同）
$5\times 3 \equiv 15 \pmod{19}$ 　　　（ $3^5 \pmod {19}$ に合同）

・・・（以下、繰り返す）・・・

$6\times 3 \equiv 18 \pmod{19}$ 　　　（ $3^{99} \pmod {19}$ に合同）
$18\times 3 \equiv 16 \pmod{19}$ 　　（ $3^{100} \pmod {19}$ に合同）

結果は、方法１と同じ $16$ となりました！これで一安心ですね！

肝心の計算のしやすさについてですが、結果の桁が少ない分こちらの方が圧倒的に楽です。

さらに、この方法を使うと良いことがあります。実は

最後まで計算しなくても
答えがわかってしまう

のです。

いったいどういうことでしょうか。

$3$ のべき乗の $\mod{19}$ における値を、最初の３６個について書きならべてみましょう。
（12月9日追記："４０個" と書いていましたが、正しくは "３６個" でした。訂正します。）

結果をよーくみてみると、右辺の値が

$18$ 個おきに繰り返されている

ことがわかります。そう、べき乗した値を $19$ で割ったあまりには

周期性

があったのです。周期性はこのあとも続いていきます。

この周期性に気づくと、 $3^{100}$ の値が簡単に得られます。 $3^{100}$ は周期の $10$ 番目にあたりますので、

$3^{100} \equiv 3^{10} \equiv 16 \pmod{19}$

があっというまに得られました。なんということでしょう！

もちろん、結果は元の方法と一致していますね！

実は、二番のサビを注意深く聞いていると、この解法が示唆されていることがわかります。

3の10乗計算してあきらめそうになってしまうけど
君が思うより答えは
もう出ているかもなんて
夢みたいなことすら
目の前にあるからさ

なるほど、たしかに答えは $3^{10}$ を計算する時点で出ていたのですね！面白い！

しかし、この周期性は、いったいどうして現れるのでしょうか。新しい謎が生まれてしまいました。

これについては方法３で考えることにしましょう。

方法３：フェルマーの小定理を使う（難易度：★★★☆☆） *

方法２を解く過程で「べき乗の結果か周期性を持っている」という驚きの事実を発見しました。これはいったいどうしてなのでしょうか。

実はこの事実は、「フェルマーの小定理」によって説明することができます。「小定理」などと名前がついていますが、整数論において最も有用な定理の１つです。

フェルマーの小定理：
$p$ を素数とし， $a$ を $p$ と互いに素な整数とするとき，以下が成り立つ．
$a^{p-1} \equiv 1 \pmod{p}$

定理の証明はしませんが、例を見ればわかっていただけるでしょう。

今回のケースでは、 $p = 19$ ， $a = 3$ です。フェルマーの小定理に代入すると、

$3^{19-1} \equiv 1 \pmod{19}$

となります。

たしかに、先ほどの計算結果と一致していますね！

すなわち、 $(19 - 1) = 18$ のべき乗ごとに、あまりの値が $1$ に「リセットされる」ということです。その次からまた新しい周期がはじまるというわけですね。

だから、 $18$ 乗ごとに繰り返される、という結果が保証されるわけです。

フェルマーの小定理をもとにした解法を書くと、以下のようになります。

（解答）
$19$ は素数より，フェルマーの小定理から，
$3^{19 - 1} \equiv 1 \pmod{19} \tag{2}$

一方，
$3^{100} = 3^{5 \times 18 + 10} = (3^{18})^5 \cdot 3^{10}$
この式に $(2)$ を代入すると，
$(3^{18})^5 \cdot 3^{10} \equiv 1^5 \cdot 3^{10} \pmod{19}$

また，地道な計算より
$3^{10} \equiv 16 \pmod{19}$
であるから，
$3^{100} \equiv 16 \pmod{19}$
が得られる．

というわけで、ずいぶんスッキリとした計算で求めることができましたね！

めでたしめでたし。

・・・

といいたいところですが。

実は・・・この方法はさらに洗練させることができます。笑

ここまでくるともはや趣味でしかありませんが、ここまでついてきてこれた方には、ぜひとも次の解法をご紹介したい。

方法４は、初等整数論において金字塔とされる美しい定理

「平方剰余の相互法則」

を用いた鮮やかな解法です。

方法４：平方剰余の相互法則を使う（難易度：★★★★★） *

（ここから難度が少し上がります。
ついてこれなくなってしまったら・・・ごめんなさい。
記事のおわりのまとめまで飛んでください。）

方法４で着目したいのは、

$\mod{19}$ における $3^{10}$ をいかに鮮やかに計算するか

ということです。方法３においても、 $3^{10}$ の値は、ただただ地道に計算するだけでした。

そのためにまず、

$3^9 \pmod{19}$

という数に注目します。

指数である $9$ は、フェルマーの小定理の指数 $18$ の、ちょうど半分になっていますね。

すなわち、 $p = 19$ とすると、

$\displaystyle 3^{\frac{p-1}{2}} \pmod{p}$

の形になっています。

この数を２乗すると、

$\displaystyle (3^{\frac{p-1}{2}})^2 \equiv 3^{p-1} \pmod{p}$

となります。フェルマーの小定理より、

$\displaystyle 3^{\frac{p-1}{2}} \equiv \pm 1 \pmod{19}$

が得られます。

したがって $3^{\frac{p-1}{2}}$ という数は、 $\mod p$ において $1$ か $(-1)$ のいずれかと合同であるはずです。

これは高校数学で習った、

$X = \pm 1$ ならば $X^2 = 1$

と全く同じことを言っています。

ちなみに $-1$ というのは、 $\mod{19}$ においては $18$ のことを指しています。 $19 - 1 = 18$ ということですね。

さて、 $3^{\frac{p-1}{2}}$ は、 $1$ と $(-1)$ の、いったいどちらになるのでしょうか。

実は $(-1)$ になることがすぐにわかるのですが、そのためには少し準備が必要です。

まず、ルジャンドル記号を定義します。

（ルジャンドル記号）
整数 $a, p$ に対し，記号 $\displaystyle \left(\frac{a}{\;p\;}\right)$ を以下で定義する．ただし， $p$ は素数．
$x^2 \equiv a \pmod p$ をみたす $x$ が存在するとき， $\displaystyle \left(\frac{a}{\;p\;}\right) = 1$

$x^2 \equiv a \pmod p$ をみたす $x$ が存在しないとき， $\displaystyle \left(\frac{a}{\;p\;}\right) = -1$

場合わけになっていて、厄介そうにみえますね。要は $a$ が $\mod p$ における「平方数」のときに $1$ ，そうでないときに $-1$ となるような記号を $\displaystyle \left(\frac{a}{\;p\;}\right)$ と決めたわけです。

ある数を法としたときの「平方数」のことを、整数論では「平方剰余」といいます。

$\mod{19}$ において、~~0を除く19以下のすべての整数~~ $1$ 以上 $19$ 未満の整数についての平方を考えましょう。以下の式の右辺に来る数が、 $\mod{19}$ における平方数、すなわち平方剰余です。

$1^2 \equiv 1 \pmod{19}$
$2^2 \equiv 4 \pmod{19}$
$3^2 \equiv 9 \pmod{19}$
$4^2 \equiv 16 \pmod{19}$
$5^2 \equiv 6 \pmod{19}$
$6^2 \equiv 17 \pmod{19}$
$7^2 \equiv 11 \pmod{19}$
$8^2 \equiv 7 \pmod{19}$
$9^2 \equiv 5 \pmod{19}$
$10^2 \equiv 5 \pmod{19}$
$11^2 \equiv 7 \pmod{19}$
$12^2 \equiv 11 \pmod{19}$
$13^2 \equiv 17 \pmod{19}$
$14^2 \equiv 6 \pmod{19}$
$15^2 \equiv 16 \pmod{19}$
$16^2 \equiv 9 \pmod{19}$
$17^2 \equiv 4 \pmod{19}$
$18^2 \equiv 1 \pmod{19}$

計算結果より、 $1, 4, 5, 6, 7, 9, 11, 16, 17$ の９つが平方剰余であることがわかります。
（12月8日追記："８つ" と書いていましたが、正しくは "９つ" でした。訂正いたします。）

ルジャンドル記号で表すと、たとえば $5$ を使って、

$\displaystyle \left(\frac{5}{\;19\;}\right) = 1$

となります。

一方で、上の式の右辺には $3$ のような数は出てきませんから、平方剰余ではありません。この場合は、

$\displaystyle \left(\frac{3}{\;19\;}\right) = -1$

となります。

＊　＊　＊

さて、この話はいったいどこに向かっているのか、と心配になった方もいるかもしれません。もう少しがまんしてください。

実は、オイラーの基準という法則を用いると、平方剰余が最初の問題に結びつきます。

（オイラーの基準）
$p$ を素数とし， $a$ を $p$ と互いに素な整数とするとき，以下が成り立つ．
$\displaystyle a^{\frac{p-1}{2}} \equiv \left(\frac{a}{\;p\;}\right) \pmod p$

証明はおいておきましょう。結果が重要です。

ここで $a = 3$ ， $p = 19$ とすると、

$\displaystyle 3^{\frac{19-1}{2}} \equiv \left(\frac{3}{\;19\;}\right) \pmod{19}$

が得られます。

$\displaystyle \left(\frac{3}{\;19\;}\right) = -1$ より、

$3^{9} \equiv -1 \pmod{19}$

であることがわかりました。これで、 $3^9$ は一応計算できましたね。

＊　＊　＊

とはいえ、この方法ではまだ不十分です。それは、平方剰余の計算が面倒だからです。すべての数に対して平方数の計算をためして、そのリストに $3$ がないことを示さなければなりません。これでは、 $3^9$ を地道に計算した方がまだ早いかもしれません。

実は、この平方剰余を計算するための、奥の手があるのです。

おまたせしました！これこそが、まさに

「平方剰余の相互法則」

です！！

（平方剰余の相互法則）
相異なる奇素数 $p, q$ に対して，以下のいずれかが成り立つ．

ケース (A) $p, q$ のいずれかが $4$ で割ってあまり $1$ であるとき：
$\displaystyle \left(\frac{q}{\;p\;}\right) = \left(\frac{p}{\;q\;}\right)$

ケース (B) $p, q$ のどちらも $4$ で割ってあまり $3$ であるとき：
$\displaystyle \left(\frac{q}{\;p\;}\right) = -\left(\frac{p}{\;q\;}\right)$

２つの素数 $p, q$ について作られた２通りの平方剰余に対して、上に挙げたような簡単な法則が成り立つというのです。

意味を考えるには、使ってみるのが一番早いでしょう。

$p = 19, \; q = 3$ とおいてみます。すると、 $p, q$ のどちらも $4$ で割ってあまり $3$ となりますから、ケース (B) が該当します。したがって、平方剰余の相互法則より、以下が成り立ちます。

$\displaystyle \left(\frac{3}{\;19\;}\right) = -\left(\frac{19}{\;3\;}\right)$

あとは右辺を計算できれば、目的達成です。
右辺は $\mod 3$ における平方剰余を考えているわけですが、

$19 \equiv 1 \pmod 3$

ですから、

$\displaystyle \left(\frac{3}{\;19\;}\right) = -\left(\frac{1}{\;3\;}\right)$

となります。 $1$ が $\mod 3$ で平方剰余であることは、

$1^2 \equiv 1 \pmod 3$

より明らかですから、結局

$\displaystyle \left(\frac{3}{\;19\;}\right) = -1$

が得られます。これが求めていた結論でした。実に鮮やかですね。

解答もまとめておきましょう。

（解答）
$19$ は素数より，フェルマーの小定理から，
$3^{19 - 1} \equiv 1 \pmod{19} \tag{3}$

一方，
$3^{100} = 3^{5 \times 18 + 10} = (3^{18})^5 \cdot 3^{10}$
この式に $(3)$ を代入すると，
$(3^{18})^5 \cdot 3^{10} \equiv 1^5 \cdot 3^{10} \pmod{19}$

また，オイラーの基準より，
$\displaystyle 3^{9} \equiv \left(\frac{3}{\;19\;}\right) \pmod{19}$

である． $3, 19$ はともに $4$ で割って $3$ あまる素数であるから，平方剰余の相互法則 より，
$\displaystyle \left(\frac{3}{\;19\;}\right) = -\left(\frac{19}{\;3\;}\right) = -\left(\frac{1}{\;3\;}\right)$

$\displaystyle \left(\frac{1}{\;3\;}\right) = 1$ より，
$\displaystyle \left(\frac{3}{\;19\;}\right) = -1$
が得られる．

以上から，
$\displaystyle 3^{9} \equiv -1 \pmod{19}$
であることがわかった．
両辺に $3$ をかけると，
$3^{10} \equiv -3 \equiv 16 \pmod{19}$
が得られる．

したがって，
$3^{100} \equiv 16 \pmod{19}$
が示された．

$3^9$ を求める部分から地道な計算がなくなり、方法３と比べて圧倒的に楽になったことがわかるでしょう。慣れてくれば暗算で求めることもできます。

＊　＊　＊

ところで、平方剰余の相互法則の意味するところは、いったいなんなのでしょうか。

式に登場するのは、 $p$ と $q$ という２つの素数です。２つの素数で作られた２通りの平方剰余が、相互に関係しているということを表しています。

２つの平方剰余の関係は、まったく自明ではありません。証明しようとすると、いかに困難かがわかるでしょう。

相互法則をみつけたガウスは、その証明の難しさと結果の美しさに惹かれて、どうにかこれを証明しようとさまざまなアプローチを試みます。その結果、最終的に７つのも証明を残しています。ガウスの数学人生において、この相互法則の真の理解はライフワークと呼べるものでした。

数学者の中にもこの相互法則の愛好者は多いようです。数論の研究者である加藤和也先生もその一人です。
（加藤和也先生は、素数のことを愛するあまり「素数の歌」を作ってしまった数学者としてもよく知られています。）

彼の著書「数論への招待」では、平方剰余の相互法則が以下のように語られています。

全く別のことのはずなのに，その２つのことが平方剰余の相互法則によって直結してしまうのです．これは全くふしぎなことで，素数たちが互いに孤立せず強く関係しあっていることを示しています． $p$ 太君の心に映る $q$ 子さんの姿 $\left(\frac{q}{p}\right)$ と， $q$ 子さんの心に映る $p$ 太郎君の姿が $\left(\frac{p}{q}\right)$ が，関係しあっているのです．
・・・（中略）・・・
素数たちもお互いを深くわかりあっているのでしょう．

なんと素敵な表現でしょうか。

この文章を思い浮かべながら、元の曲の歌詞を振り返ってみると、登場人物の「僕」と「君」が $p$ 太君と $q$ 子さんに見えてきます。そして大サビの最後が以下のように締めくくられていることに気づくでしょう。

君と二人でいこう　僕と二人でいこう

私にはこのくだりが、 $p$ 太君と $q$ 子さんの二人の関係、すなわち、平方剰余の相互法則を示唆しているように思えてなりません。

まとめ

今回は「 $3^{100}$ を $19$ で割ったあまりは？」という問題を４通りの方法で解説してきました。この問題は、今回紹介したように多様なアプローチで挑むことができます。

方法３・４は、整数論において重要な定理である「フェルマーの小定理」や「平方剰余の相互法則」をつかったエレガントな方法でした。一方で、方法１・２のような、地道で素朴な方法によっても、この問題は解を得ることができます。

まったくの初心者でも手を出すことができて、なおかつ整数論に詳しい人はよりエレガントな方法を追求できる、という非常にバランスのよい問題だったということですね。

実は、他にも紹介したかった方法が１つあったのですが、時間の都合からカットしています。「繰り返し自乗法」と呼ばれる方法ですが、tsujimotterの旧ブログの以下の記事で説明していますので、興味を持った方はみてみてください。暗号の計算にも用いられる実用的な計算方法です。

繰り返し自乗法

常々思うことなのですが、整数論の問題は日曜数学者にとってぴったりだと思うのです。

一般に整数論の問題には、登場する数は整数だけですから、数を代入して試すことができます。整数の四則演算は、昔からみなさん親しんできていますので、そのハードルはあまり高くないはずですよね。

具体的な手計算は、問題についてのイメージを捉えることにもつながり、イメージが湧けばそれだけ問題の理解に近づきます。整数論の問題は、たとえ難しい定理を知っていなくても、こうした行為によって気軽に親しむことができるのです（専門家でなくても！）。

あなたがもしプログラマであれば、プログラムを使ってたくさんの例を計算することもできます。実をいうと、方法１・方法２の計算には Ruby のプログラムを使っています。私は手計算がとても苦手で、いつも間違えるのでプログラムを使うことが多いです。それぞれが自分の得意な方法でアプローチしていけば良いと思います。

今回の話で、整数論の魅力のひとかけらを感じてもらえると嬉しいです。ぜひ、一緒に整数で遊びましょう！