数理論 へ戻る（１）合同式の概念
-
合同式の基本形： a を m で割ると b 余り、 c を m で割ると d 余る。
a ≡ b ( mod m ) ≡ b ＋ m ( mod m ) ≡ b + 2m ( mod m ) ≡ ・・・
c ≡ d ( mod m ) ≡ d − m ( mod m ) ≡ d − 2m ( mod m ) ≡ ・・・
c ≡ d ( mod m ) ≡ d − m ( mod m ) ≡ d − 2m ( mod m ) ≡ ・・・
合同式は、ある１つの「割る自然数（法という）」を決めたときに、余りが等しい数を ≡ で結んだものである。合同式で結ばれる数には、割る自然数に等しい周期の周期性があるので、回転を例にとって説明しよう。「正味何度回転させるか」ではなく「回転させた結果どうなっているのか」に注目して話を聞いてほしい。
まず反時計回りに 500°回転させ、続いて反時計回りに 600°回転させるということは、結果的には、まず反時計回りに 140°回転させ、続いて反時計回りに 240°回転させるということと結果的には同じであり、かつ、結果的には、反時計回りに 380°回転させることと同じであり、かつ、結果的には、反時計回りに 20°回転させることと同じである。以上を数学的に記述すると、次のようになる。
360° を法とすると、 500°＋ 600° ≡ 140°＋ 240° ≡ 380° ≡ 20°
500＝1×360＋140 → 500 ≡ 140 (mod 360)
600＝1×360＋240 → 600 ≡ 240 (mod 360)
500＋600 ＝ 140＋240 (mod 360)
140＋240 ＝ 380 ＝ 1×360＋20 → 140＋240 ≡ 20 (mod 360)
よって、 500＋600 ≡ 140＋240 ≡ 380 ≡ 20 (mod 360)
まず反時計回りに 500°回転させ、続いて時計回りに 600°回転させるということは、結果的には、まず反時計回りに 140°回転させ、続いて時計回りに 240°回転させるということと結果的には同じであり、かつ、結果的には、時計回りに 140°回転させることと同じであり、かつ、結果的には、反時計回りに 260°回転させることと同じである。以上を数学的に記述すると、次のようになる。
360° を法とすると、 500°− 600° ≡ 140°− 240° ≡ −140° ≡ 260°
合同式の演算法則：
a ≡ b (mod n) ならば、次の３つの式が成り立つ。
a＋c ≡ b＋c (mod n)
a−c ≡ b−c (mod n)
ka ≡ kb (mod n)
a＋c ≡ b＋c (mod n)
a−c ≡ b−c (mod n)
ka ≡ kb (mod n)
10 ≡ 2 (mod 8)
8 ≡ 0 (mod 8)
18 ≡ 2 (mod 8)
-
360° を法とすると、60° も 420° も 780° も すべて同じものと考えることができる。つまり、 360°×ｎ＋60°（ ｎ は整数 ） という形で表される角度は、区別がつかないものとして考えて良いということになる。よって、これらの角度を最も簡単な 60° で表すことにすればいいことになる。
7 を法とすると、（ 7 を法とする とは、最終的に 7 で割った余りを出力するということである。）
・・・ −14 −7 0 7 14 21 ・・・・ の数は区別できない数である。
→ そこでこれらの数を 0 で表すことにしよう。
・・・ −13 −6 1 8 15 22 ・・・・ の数は区別できない数である。
→ そこでこれらの数を 1 で表すことにしよう。
・・・ −12 −5 2 9 16 23 ・・・・ の数は区別できない数である。
→ そこでこれらの数を 2 で表すことにしよう。
・・・ −11 −4 3 10 17 24 ・・・・ の数は区別できない数である。
→ そこでこれらの数を 3 で表すことにしよう。
・・・ −10 −3 4 11 18 25 ・・・・ の数は区別できない数である。
→ そこでこれらの数を 4 で表すことにしよう。
・・・ −9 −2 5 12 19 26 ・・・・ の数は区別できない数である。
→ そこでこれらの数を 5 で表すことにしよう。
・・・ −8 −1 6 13 20 27 ・・・・ の数は区別できない数である。
→ そこでこれらの数を 6 で表すことにしよう。
7 を法として、 50 51 52 53 54 55 56 57 を求めてみよう。
50 ÷ 7 ＝→ 1 ÷ 7 ＝→ 0 余り 1 ⇒ 1
51 ÷ 7 ＝→ 5 ÷ 7 ＝→ 0 余り 5 ⇒ 5
52 ÷ 7 ＝→ 25 ÷ 7 ＝→ 3 余り 4 ⇒ 4
53 ÷ 7 ＝→ 125 ÷ 7 ＝→ 17 余り 6 ⇒ 6
54 ÷ 7 ＝→ 625 ÷ 7 ＝→ 89 余り 2 ⇒ 2
55 ÷ 7 ＝→ 3175 ÷ 7 ＝→ 453 余り 3 ⇒ 3
56 ÷ 7 ＝→ 15625 ÷ 7 ＝→ 2232 余り 1 ⇒ 1
57 ÷ 7 ＝→ 78125 ÷ 7 ＝→ 11160 余り 5 ⇒ 5
でも、こんなことしなくても、次のようにすれば簡単にできるのだ。ここが肝心なところ！
50 ÷ 7 ＝→ 1 ÷ 7 ＝→ 0 余り 1 ⇒ 1
51 ÷ 7 ＝→ 5 ÷ 7 ＝→ 0 余り 5 ⇒ 5
52 ÷ 7 ＝→ ( 5 × 51 ) ÷ 7 ＝→ ( 5 × 5 ) ÷ 7 ＝→ 25 ÷ 7 ＝→ 3 余り 4 ⇒ 4
53 ÷ 7 ＝→ ( 5 × 52 ) ÷ 7 ＝→ ( 5 × 4 ) ÷ 7 ＝→ 20 ÷ 7 ＝→ 2 余り 6 ⇒ 6
54 ÷ 7 ＝→ ( 5 × 53 ) ÷ 7 ＝→ ( 5 × 6 ) ÷ 7 ＝→ 30 ÷ 7 ＝→ 4 余り 2 ⇒ 2
55 ÷ 7 ＝→ ( 5 × 54 ) ÷ 7 ＝→ ( 5 × 2 ) ÷ 7 ＝→ 10 ÷ 7 ＝→ 1 余り 3 ⇒ 3
56 ÷ 7 ＝→ ( 5 × 55 ) ÷ 7 ＝→ ( 5 × 3 ) ÷ 7 ＝→ 15 ÷ 7 ＝→ 2 余り 1 ⇒ 1
57 ÷ 7 ＝→ ( 5 × 56 ) ÷ 7 ＝→ ( 5 × 1 ) ÷ 7 ＝→ 5 ÷ 7 ＝→ 0 余り 5 ⇒ 5
（３）合同式で解く累乗の余り
-
【 問 題 】
-
310 は８で割ると１余ることを示せ。
-
※ MOD (a,b) は a を b で割った余りをアウトプットする関数。
MOD (310,8) ＝ MOD (95,8)
＝ MOD ((8＋1)5,8)
＝ MOD ((0＋1)5,8)
＝ MOD (1,8)
＝ 1
以上を合同式を用いて表わすと、次のようになります。
310 ＝ 95 ＝ (8＋1)5 → 310 ≡ (8＋1)5 ≡ (0＋1)5 (mod 8)
(0＋1)5 ＝ 1 だから、 310 ≡ 1 (mod 8)