510
古12 次不定方程式の応用問題
た請2雪の5 で割ると 3余り, 7 で割ると4余るような自然数ヵで最
指針に 3 で割ると 2 余る自然数は 導 11. 17』20。。…
然数は 3, 舌, 13, 18, 98, ……
5 で割ると 3 余る自然数」 を小さい順に書き上げる
。 の538國6 < 3 と5 の最小公倍数 15 ずつ大きく
また, 7 で割ると4余る自然数は 1 18, 25。32。39, 46. 5
@ つから, 求める最小の自然数は 53 であることがわかる。
このように, 書き上げによって考える方法もあるが, 条件を満たす数が簡単
い (相当多くの数の書き上げが必要な) 場合は非効率的である。
そこで, 問題の条件を 1 次不定方程式に帰着させ, その解を求める方針で
き
はx。)。 るを数として 次のように表される。
カー8x寺2 ヵー5y+3. )
刺す2=5y二3から 3xー5yニ1 …… 凍いい
テー2。 ッー1 は。⑪ の整数解の 1 つであるから 沙
3ヶー2)-5(⑦-1)ニ0 すなわち 3(x-2)=5(ッー1)
3 と5 は互いに素であるから, んを整数として, *ー2ニ5 と表
される。よって ァニ5ん+2(んは整数) …… ② このとき >=3k+1
②を3z+2=7z二4 に代入して 3(5を十2)二2=7<4 3テー7<=2 から
ゆえに 。 7z一15=ニ4 …… ③ 3@ー3)一7(<-1)=0
タニー8, をニー4 は, ⑧ の整数解の 1つであるから めえに, / を整数として
7(々8) 一15(ぁ+4)ニ0 すなわち 7(々8)=15(&+4) 騙DS we
これとェー5ん2 をき
7 と 15 は互いに素であるから, を整数として, z+8=157 と | < 5二2=77+3
Eo。 よって >=15/-8 (/ は整数) よって 5z-7/ニ1
これをヵー7<十4 に代入して カー7(157一8)二41057-52 これより, ん7 が求めら
最小となる自然数んは。/=1 を代入して ss 1 方式を解く手間
1 つ増える。
人
