今回は新課程から新しく入った分野、「整数の性質」について勉強しましょう。
整数の範囲で割り算をした時の余りに着目した、便利な定理、公式がいくつかあります。
ユークリッドの互除法を利用した、不定方程式は入試でもとてもよく出題される問題の１つですね。まず互除法について復習しましょう。
今、a > b である２つの自然数 a ，b について、a を b で割った商を q 、余りを r とすると、
a = b q ＋ r ( 0 ≤ r < b ) ・・・・・①
とおけます。
これより、 r ≠ 0 のとき、①は
r = a - b q ・・・・・② とも書けるので、
g を a と b の 最大公約数、 g ’ を b と r の最大公約数とすると、
①より g ’ は a の約数になります。よって g ’ は a と b の公約数と言えます。
そこで g ‘ ≤ g ・・・（1）
一方、②より、 g は r の約数でもあるので、g は b と r の公約数と言えます。
そこで g ≤ g’ ・・・（2）
（1） , （2） より、 g = g ’
すなわち、
『 a と b の最大公約数と b と r の最大公約数は等しい 』
( a > b、a と b は自然数、 r ≠ 0 ）‥‥‥ 互除法の原理
これを利用して、割った数と余りで割り算を繰り返し、最大公約数を求める方法が、ユークリッドの互除法です。
また、 a x + b y = c の形の不定方程式で、整数解が存在するときの１つの解を求めるときも、このユークリッドの互除法が応用されますね。
[ 例題 ]
17 x - 24 y = 1 の解の１つを求めなさい。
[ 解答、解説 ]
24 ÷ 17 = 1 余り 7 より、 7 = 24 - 17 × 1 ‥ ①
17 ÷ 7 = 2 余り 3 より、 3 = 17 - 7 × 2 ‥ ②
7 ÷ 3 = 2 余り 1 より、 １＝ 7 - 3 × 2 ‥ ③
よってこれをさかのぼる事によって、
③ より、 1 = 7 - 3 × 2
3 に②を代入、
= 7 - ( 17 - 7 × 2 ) × 2
= 7 - 17 × 2 + 7 × 4
= 7 × 5 - 17 × 2
7に①を代入、
= ( 24 - 17 ) × 5 - 17 × 2
= 24 × 5 - 17 × 7
= 17 × ( - 7 ) - 24 × （- 5）
より、 x = - 7 , y = - 5 が１つの解となります。
余りに着目した便利な式には合同式もあります。
例えば、12 を５で割った余りも、７を５で割った余りも等しく２となります。
このとき、
「12 と 7 は 5 を法として合同である」、と言い、
12 ≡ 7 ( mod 5 )
と書き、これを合同式、と言います。
合同式については、
a 、b 、c 、d 、が整数、 m が正の整数で、
a ≡ b ( mod m ) 、 c ≡ d ( mod m ) のとき、
ⅰ ) a + c ≡ b + d ( mod m )
ⅱ ) a - c ≡ b - d ( mod m )
ⅲ ) a c ≡ b d ( mod m )
が成り立ち、整数の性質の証明などに良く使われる性質です。
[ 例題 ]
50100 を 7 で割った余りを求めなさい。
[ 解答 ]
50 ≡ 1 ( mod 7 )
50100 ≡ 1100 ≡ 1 ( mod 7 ) よって求める余りは１ |
