黄昏より暗きもの、血の流れより赤きもの

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

3の100乗を19で割った余りを計算するための、基本事項をまとめてみた

今日は日曜数学 Advent Calendar 2015 の 8日目の以下の記事や、はてなブックマークのコメントを読み解くのに必要な基本的な知識を簡単にまとめてみました。

と言う訳で、以下基本事項の解説をします。

合同式

nを2以上の整数とし、自然数aを自然数nで割った余りbとします。この事を a≡b (mod n)のように式で表したものを合同式と言います。この事をa,bはnを法として合同と言い、こう表す事で様々な状況が捉えやすくなる事があります。次は合同式の計算をする上で必要な公式を紹介します。

公式:合同式の和、差、積

a≡s (mod n)、 b≡t (mod n)を満たす整数a,b,s,t,nがある。このとき
和:a+b ≡ s+t (mod n)
差:a-b ≡ s-t (mod n)
積:ab ≡ st (mod n)

以下公式の説明ですが、上の式をみての通り、直感的に合同式の和、差、積は通常の四則演算(+、-、×、÷)と同じように扱える事が分かります。まずは公式の使い方になれるための、以下の練習問題をご覧下さい。

練習問題

以下の(あ)、(い)、(う)に適切な語句を埋めて文章を完成させなさい。
整数nにおいて、x≡3 (mod 4)、y≡1 (mod 4)とする。このときx+2y≡(あ) (mod 4)、
2x-y≡(い) (mod 4)である。さらにx^3≡(う) (mod 4)である。

解答

x+2y≡ 3+2 ≡ 5 ≡ 1 (mod 4) (あ)、2x-y ≡ 6-2 ≡ 4 ≡ 0 (mod 4) (い) 、x^3≡3^3 ≡ 27 ≡ 3 (う)

本題:3^100を19で割った余りを求めよ

と言う訳で上記の合同式の和、差、積を使い以下の問題をやってみましょう。

今日の問題

3^100を19で割った余りを求めよ

合同式を使った解答

本問のように累乗の大きい場合の余りを求めるとき、100乗を100(乗)=3(乗)*33(個)+1(乗)というように、短い累乗に区切って整数を小さくして計算します。自分もid:amori氏やid:blueboy氏が紹介しているようなやり方で解いてみました。以下にその一例を書きます。

3^100
≡ 3 * 27^33 (mod 19)
≡ 3 * 8^33 (mod 19)
≡ 3 * 8 * 8^32 (mod 19)
≡ 3 * 8 * 64^16 (mod 19)
≡ 5 * 7^16 (mod 19)
≡ 5 * 49^8 (mod 19)
≡ 5 * 11^8 (mod 19)
≡ 5 * 121^4 (mod 19)
≡ 5 * 7^4 (mod 19)
≡ 5 * 49^2 (mod 19)
≡ 5 * 11^2 (mod 19)
≡ 5 * 7 (mod 19)
16 (mod 19)

Pythonを使った解答

元記事のはてなブックマークコメントを見ていると、id:lp008962氏やid:hfukuda58氏はPythonRubyで解いたとのことです。自分も答え合わせの為、Pythonで実践してみました。

>> pow(3,100,19)
16

2015.12.11 はてなブックマークより、正しい方法を教わったのでコードを訂正させて頂きました。

ホント、こういう時にプログラムは関数電卓の代わりになって便利です。

最後に

今日はまあストレス解消と言うか、書きたい事が無いので簡単に記事にしました。合同式は大学受験でももちろん、整数論を勉強する上でも役に立つと思います。本記事が整数論の復習になれば幸いです。