510
例題129 1次不定方程式の応用問題
O0000
基本
|3で割ると2余り, 5で割ると3余り, 7 で割ると4余るような自然数 nで最小の
ものを求めよ。
(2) 37
基本127,128
指針> 3で割ると2余る自然数は 2, 5, 8, 11, 14, 17, 20, 23.
5で割ると3余る自然数は 3, 8,13, 18, 23,
が共通の数。
8が最小である。
よって,「3で割ると2余り, 5で割ると3余る自然数」を小さい順に書き上げると
A 8, 23, 38, 53, 68,
43と5の最小公倍数15ずつ大きくなる。
また,7で割ると4余る自然数は B 4, 11, 18, 25, 32, 39,46, 53.
の, B から,求める最小の自然数は 53 であることがわかる。
このように,書き上げによって考える方法もあるが,条件を満たす数が簡単に見つから。
い(相当多くの数の書き上げが必要な)場合は非効率的である。
そこで,問題の条件を 1次不定方程式に帰着させ, その解を求める方針で解いてみよう
解答
nはx, y, zを整数として,次のように表される。
n=3x+2, n=5y+3, n=7z+4
注意 3x+2=5y+3
36年5 かつ 5y+3=7z+4
の くち小 として解いてもよいが、係
3x+2=5y+3 から
3x-5y=1
x=2, y=1 は, ①の整数解の1つであるから
3(x-2)-5(y-1)=0 すなわち 3(x-2)=5(yー1)-x
3と5は互いに素であるから,kを整数として,x-2=5k と表
される。よって
のを3x+2=7z+4に代入して 3(5k+2) +2=7z+4 るを「43x-7z=2から
い。
x=5k+2(k は整数)
2
40 bom) ト このとき y=3k+1
S+A-%3 (ト+)-0ト- 3(x-3)-7(z-1)=0
ゆえに,1を整数として
ゆえに
72-15k=4
3
ス=-8, k=-4は, ③ の整数解の1つであるからー=¢ A+
907(z+8)-15(k+4)=0 9すなわち 7(z+8)=D15(k+4)
x=71+3
これと x=5k+2を等置し
7と15 は互いに素であるから,1を整数として,z+8=15Z と て 5k+2=7/+3
よって 5k-71=1
これより,k,1が求められ
るが,方程式を解く手間が
Ex@-
(TE bom) トー=
これをn=7z+4に代入してn=7(15/-8)+4=105/-52) 8
53 bom) 8S-
表される。よって。
2=15/-8(1は整数)
最小となる自然数nは,1=1を代入して
1つ増える。
ーンシ
文不宝武器
なるほど、よく分かりました！
ありがとうございました！