合同式は教育課程の中には入っていない理論である。
ところがこの合同式は整数に関する種々の問題にすっきりとした見通しを与え、かつ計算処理も比較的容易である。
合同式については数学教育の中で、もっともっと関心を持たれてもよい教材であると思われる。
今まで合同式の活用例について調べてきたが、不定方程式の解法の中で合同式がはたす役割について書き加えておきたい。
【例1】xとyは正の整数で、5x+3y=50であるという。xとyの値の組を求めよ。(明治大) |
(解法1) 5x+3y=50より、5x=50-3y
左辺は5の倍数であり、右辺も5の倍数となるには3yが5の倍数でなければならない。
3と5は互いに素なのでyは5の倍数である。 ∴y=5t…①
tx=50-3y=50-3×5t ∴x=10-3t…②
x>0,y>0より 0<t<10/3。 tは整数なので t=1,2,3
t=1のとき x=7,y=5
t=2のとき x=4,y=10 t=3のとき x=1,y=15
以上のような解法が多くの場合に紹介されているものであろう。
(解法2) 5x+3y=50…① とおく。①を満たす適当なxとyを見つける。
x=4,y=10が適するから、5×4+3×10=50…② が成り立つ。
①-②より 5(x-4)+3(y-10)=0。 従って 5(x-4)=3(10-y)。
5と3は互いに素であるから、x-4は3の倍数でなければならない。
∴ x-4=3k (kは整数) 従って、10-y=5k
∴x=4+3k, y=10-5k
x>0,y>0より k=-1,0,1
k=-1のとき x=1,y=15 k=0のとき x=4,y=10 k=1のとき x-7,y=5
この解法は(解法1)に比べて解き方の手順が決まっていて判りやすい方法であるが、②を作るために適当な整数x,yを見つけるのが少々やっかいである。
そこで、合同式を用いて解いてみよう。
(解法3) 5x+3y=50 より 5x=50-3y
よって 5x≡50-3y (mod 3)≡50 (mod 3)≡2 (mod 3)
∴ 5x=2 (mod 3)
また、5x≡2x (mod 3) より
2x≡2 (mod 3) (2,3)=1 より x≡1 (mod 3)
従って x=1+3t, y=15-5t
x>0,y>0 より t=0,1,2
t=0のとき x=1,y=15 t=1のとき x=4,y=10
t=2のとき x=7,y=5
【例2】7x+17y=450 を満たす正の整数x,yを求めよ。 |
(解) 17y=450-7x より 17y≡450 (mod 7)≡2 (mod 7)…①
17y≡3y (mod 7)より、3y≡2 (mod 7)…②
①-5×②より 2y≡2-10 (mod 7)≡6 (mod 7)…③
よって、y=3+7t, x=57-17t
x>0,y>0より t=0,1,2,3
t=0のとき x=57,y=3 t=1のとき x=40,y=10
t=2のとき x=23,y-17 t=3のとき x=6,y=24
次のようなオイラーの定理を利用すると、合同式の効用はますます大きなものとなる。
(オイラーの定理) m>1なる整数で (a,m)=1 のとき、aφ(m)≡1 (mod m) ここでaは自然数、φ(m)はmより小さい自然数の中でmと互いに素なものの個数とする。 |
【例3】38x+105y=2 を満たす整数x,yを求めよ。 |
(解) 105y=2-38x より 105y≡2 (mod 38)…①
(105,38)=1 なのでオイラーの定理より、105φ(38)≡1 (mod 38)となる。
ここで、φ(38)=18 だから、10518≡1 (mod 38)…②
②より y≡10517×2 (mod 38)…③
105≡-9 (mod 38) ∴ 10517≡(-9) 17≡-917 (mod 38)
93≡7 (mod 38) ∴ (93)3≡73≡1 (mod 38)
∴ 2・917≡2・99・98 (mod 38)
≡2・98 (mod 38)≡2・72・92 (mod 38)
≡22×5 (mod 38)≡110 (mod 38)
≡-4 (mod 38)
③に代入して y≡4 (mod 38)
よって、 y=4+38t, x=-11-105t (tは整数)
φ(m)を早く求めるためには更に次の定理を使うようにすればよい。(証明は省略させていただくことにしたい。)
(1) mが素数のとき φ(m)=m-1
(2) l,mが互いに素な素数のとき φ(m・l)=(m-1)(l-1)=φ(m)×φ(l)
(3) mが素数のとき φ(mk)= mk(1-1/m) (kはk≧1の自然数)