|
受験数学の裏技的な定理やら何やらつめ込んでいる。 入試問題の数と式絡みの倍数問題の証明などは剰余についての知識を要す。 これらの問題は、発狂系難易度の問題集、オリジナル、赤チャートや 新数演などにのっているレベルのものだと、解答をみても何をやっている のかわからない程難しいというのが現実である。 ところが、この合同式という概念を用いるといとも容易く解けてしまう問題が 多数あるのである。 定義━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ある整数a,b,mがあり、a-bがmで割り切れるならば、 mを法としaとbは合同である。という。 記号で表すと、 a≡b(mod m) これは、aをmで割った余りとbをmで割った余りが等しいと言い換えられる。 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ また、合同式は以下の規律に従う。 規律━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 反射律：a≡a(mod m) 対称律：a≡b(mod m) ならば、 b≡a(mod m) 推移律：a≡b(mod m) かつ、 b≡c(mod m) ならば a≡c(mod m) ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 合同式の基本性質として、以下が成り立つ。 定理━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 一般に、
Ⅰ： a≡b(mod m) かつ c≡d(mod m)ならば、
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━Ⅱ： a±c≡b±d(mod m) Ⅲ： ac≡bd(mod m) 特に、このときa=c,b=dとして、（nは任意の整数） Ⅳ： an≡bn(mod m) なお、これらは合同式の定義から、a=mr+q,b=ms+tなどとおけば 簡単に証明できるので、証明は省く。 １次合同方程式の解法━━━━━━━━━━━━━━━━━━━━━━━ xを未知数として、１次合同式 ax≡b(mod m) は、 (a,m)=1のとき、ただひとつの解を有し、 その一般解は、ある実数yがあって １次不定方程式 ax-my=bから求められるが、 一般には、そうはせず、合同式の性質を用い、 例えば、3x≡2(mod 7) という式が与えられていれば、 任意の整数xについて、7x≡7(mod 7)であるから、 3x≡2(mod 7)の両辺を2で掛け、 6x≡4(mod 7) このとき、7x≡0(mod 7)から、 7x-6x≡7-4(mod 7) ∴x≡3(mod 7) と、いった具合に求める。 ちなみに、(a,m)=d＞1のとき、１次合同方程式ax≡b(mod m)は、 bがdで割り切れるときに限り解をもつ。その解の個数はd個である。 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 例題.nを任意の整数とし、n9-n3は常に9で割り切れることを示せ。 [証明] n9-n3=n2(n7-n) …Ⅰ と変形できるから、任意の整数nがある整数mを用いてn=3mと表せるならば、 (※mはnによって束縛されるので「ある整数」と書いています) 明らかにn9-n3(以下、与式)は9で割り切れる。 また、n=3mと表せない全ての整数は、n=3m±1と表せる。 n=3m±1のとき、 Ⅰより、 与式=(3m±1)2{(3m±1)7-(3m±1)} ≡±(27m3±27m2+9m±1){(3m±1)6-1} ≡±{(3m±1)6-1}(mod 9) …Ⅱ このとき、n=3m+1の場合に限定すると、 Ⅱ=(3m)3(3m-2)3 =9m2・3m(3m-2)3 これは明らかに9で割り切れる。 また、n=3m-1のとき、 Ⅱ=(3m)3(3m-2)3 =9m2・3m(3m-2)3 これも9で割り切れる。 以上より、任意の整数nについて与式は成り立つ。 したがって、題意は示された。 [証明終] |