3で割ると2余り, 5で割ると3余り, 7で割ると4余るような自然数nで最小の
重要
どの
510
基本 例題129 1次不定方程式の応用問題
n
でき
ものを求めよ。
基本 127,128
指針>
3で割ると2余る自然数は 2, 5, 8. 11. 14, 17, 20, 23,
5 で割ると3余る自然数は 3, 8, 13, 18, 23,
指針>
が共通の数。
8が最小である。
って, 13で割ると2余り, 5で割ると3余る自然数」 を小さい順に書き上げると
43と5の最小公倍数 15ずつ大きくなる。
の 8, 23, 38, 53. 68,
また,7で割ると4余る自然数は ⑧ 4. 11, 18, 25, 32, 39, 40, 225
の, B から,求める最小の自然数は 53であることがわかる。
OS
このように, 書き上げによって考える方法もあるが, 条件を満たす数が簡単に見つからな
い(相当多くの数の書き上げが必要な) 場合は非効率的である。
m,
1]
てこで,問題の条件を 1次不定方程式に帰着させ,その解を求める方針で解いてみよう。
解答
n はx, y, zを整数として, 次のように表される。
注意 3x+2=5y+3
かつ 5y+3=7z+4
として解いてもよいが, 係
3 数が小さい方が処理しやす
n=3x+2, n=5y+3, n=7z+4
3x+2=5y+3から
3x-5y=1
x=2, y=1 は,① の整数解の1つであるから
3(x-2)-5(yー1)=0 すなわち 3(x-2)35(yー1)
3と5は互いに素であるから, kを整数として, x-2=5k と表
される。よって
2を3x+2=7z+4に代入して
の
い。
x=5k+2(kは整数)
このとき y=3k+1
ゆえに
3(5k+2)+2=7z+4
7z-15k=4
43x-7z=2 から
3(x-3)-7(z-1)=0
ゆえに,1を整数として
ス=-8,k=4は,③ の整数解の1つであるから
7(z+8)-15(k+4)=0 すなわち 7(z+8)=D15(k+4)
7と15 は互いに素であるから,1を整数として, z+8=15 と
表される。よって
これをn=7z+4に代入して n=7(15/-8)+4=105/-52
最小となる自然数 nは, 1=1 を代入して
x=71+3
これとx=5k+2 を等置し
て 5k+2=7+3
よって 5k-7131
これより、k,1が求められ
るが、方程式を解く手間が
1つ増える。
ス=15/-8(1は整数)
( bom)
53bom
エT た
不宝
ですが、この問題の場合x,y,zが負の整数の時nも負の整数となるので、おかしくなりませんか？