当ブログ初登場の合同式を用いる問題です。
現在のカリキュラムでは数学TA で学ぶようですね。
合同式になじみのない人は、下のほうにある解説を読んでから問題に挑戦してください。
問題25 合同式で余りを求めます [高1★★☆☆☆]
自然数 n = 2951413 を 9 で割ったときの余りを求めてください。[ヒント] 筆算で商と余りを求めるとか、なしですよ。念のため。
ちゃんと合同式を使った解答を作ってください。
合同の定義
整数 a, b に対して、a − b が m で割り切れるとき、
a ≡ b (mod m)
と書き、a と b は法 m について合同であるといいます。
a ≡ b (mod m)
と書き、a と b は法 m について合同であるといいます。
この一般的な書き方は分かりにくいので、もう少しくだけた表現で書き直すと、
整数 a, b を m で割ったときの余りが等しいとき、
a ≡ b (mod m)
と書き、a と b は法 m について合同であるといいます。
a ≡ b (mod m)
と書き、a と b は法 m について合同であるといいます。
...... やっぱり今ひとつ分かりにくいかもしれませんので、実際の数で確認してみます。
たとえば、
a = 21, b = 13
という数を選んでみましょう。それぞれ 8 で割ってみます。
a/8 = 21/8 = 2 余り 5
b/8 = 13/8 = 1 余り 5
b/8 = 13/8 = 1 余り 5
となって余りが等しいことがわかります。なので 21 と 13 は 8 を法として合同で、
21 ≡ 13 (mod 8)
と書きます。ところが a, b を 7 で割ると、
a/7 = 21/7 = 3 余り 0
b/7 = 13/7 = 1 余り 6
b/7 = 13/7 = 1 余り 6
となって、21 と 13 は 7 を法とした場合には合同ではありません。
合同式の加算・減算・乗算・べき乗
a1 ≡ a2, b1 ≡ b2 (mod m) のとき、
(1) a1 + b1 ≡ a2 + b2, a1 − b1 ≡ a2 − b2
(2) a1 b1 ≡ a2 b2 (3) a1n ≡ b1n
(1) a1 + b1 ≡ a2 + b2, a1 − b1 ≡ a2 − b2
(2) a1 b1 ≡ a2 b2 (3) a1n ≡ b1n
証明は易しいので省略します。気になる人は教科書やネットで確認しておいてください。
ここでは具体的な数を使って上の定理が成り立っているかを確認しておきます。
8 ≡ 5, 7 ≡ 4 (mod 3) を使って確かめてみましょう。
a1 = 8, a2 = 5, b1 = 7, b2 = 4 です。
(1) a1 + b1 = 15, a2 + b2 = 9 ですから、
15 ≡ 9 (mod 3)
加算について確かに成り立っています。 a1 − b1 = 1, a2 − b2 = 1 ですから、
1 ≡ 1 (mod 3)
減算についても成り立っています。
(2) a1 b1 = 56, a2 b2 = 20 です。
56 ≡ 20 (mod 3)
乗算も成り立っています。実際に割り算をしなくても、左辺 − 右辺 = 36 が 3 で割り切れることがすぐにわかります。
(3) とりあえず n = 2 だけ確認しておきましょう。 a12 = 64, a22 = 25
64 ≡ 25 (mod 3)
べき乗についても成り立っていますね(左辺 − 右辺 = 39)。
≫ [Amazon書籍] Excelでわかるハル・ホワイト・モデル
解答25(足し算で余りを求めます)
まず、10 ≡ 1 (mod 9) であることは自明ですね。同じように、102 = 99 + 1 ≡ 1, 103 = 999 + 1 ≡ 1 (mod 9)
が成り立っています。これを念頭において、
n = 2951413 = 2 × 106 + 9 × 105 + ...... + 3 × 100
と表してみます。 2 ≡ 2, 106 ≡ 1 (mod 9)ですから、乗算の定理から
2 × 106 ≡ 2 × 1 (mod 9)
が成り立ちます。他の項についても同様です。加算の定理を用いて
n ≡ 2 + 9 + 5 + 1 + 4 + 1 + 3 = 25 (mod 9)
ここまで数字が小さくなれば、 9 で割れば余りが 7 ということが明らかですけど(もちろんここで解答終わりでもいいですよ)、解答の見た目の美しさのために、ぎりぎり最後まで合同式を使って簡単にしておきましょう。先ほどの手順をもう1度繰り返すと、
n ≡ 25 ≡ 2 + 5 ≡ 7 (mod 9)
となって、すっきり 7 という数字が得られました。
足し算して余りが求められるなんて、合同式って面白いですよね。
あ、それからちなみに問題の n = 2951413 は円周率 3.141592 を逆にして作った数字です。気づいた人いましたか? 皆さんも何か適当な数字を作りたいときは円周率など無理数を使うといいですよ。ただし、パスワードには絶対に使わないでください。