(1)合同式の概念
-
合同式の基本形: 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 ) ≡ ・・・
合同式は、ある1つの「割る自然数(法という)」を決めたときに、余りが等しい数を ≡ で結んだものである。合同式で結ばれる数には、割る自然数に等しい周期の周期性があるので、回転を例にとって説明しよう。「正味何度回転させるか」ではなく「回転させた結果どうなっているのか」に注目して話を聞いてほしい。
まず反時計回りに 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) ならば、次の3つの式が成り立つ。
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°×n+60°( n は整数 ) という形で表される角度は、区別がつかないものとして考えて良いということになる。よって、これらの角度を最も簡単な 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
(3)合同式で解く累乗の余り
-
【 問 題 】
-
310 は8で割ると1余ることを示せ。
-
※ 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)
数理論 へ戻る