216
基本例題 128
1次不定方程式の整数解の利用
12で割ると余り, 7で割ると4余る3桁の自然数のうち最大の数を求めよ。
基本127
CHART & SOLUTION
1次不定方程式の整数解の利用
条件から ax+by=cの形に変形
条件を満たす自然数は, 整数 x, y を用いて, 12x+1, 7y+4と2通りに表される。 そこで、
まず方程式 12x+1=7y+4 の整数解を求め、 それから題意の自然数を求める。
答
求める自然数をnとすると, n は x,yを整数として,次のよ
うに表される。
n=12x+1, n=7y+4
よって
12x+1=7y+4
すなわち
12x-7y=3
x=3, y=5は, 12x-7y=1 の整数解の1つであるから
12・3-7.5=1
両辺に3を掛けると
12.9-7·15=3
①②から 12(x-9)-7(y-15)=0
すなわち
12(x-9)=7(y-15)
12と7は互いに素であるから, ③を満たす整数xは
x-9=7k すなわち x = 7k+9 (kは整数)
******
******
と表される。
n=12x+1=12(7k+9)+1=84k+109
したがって
84k+109が3桁で最大となるのは, 84k + 109999 を満た
すんが最大のときであり, その値は
k=10
このとき
n=84・10+109=949
RACTICE 128
11で割ると余り、5で割る
上の解答では, 12x-7y=1 の整数解の1つを求め
それから③を導いて解いた。
しかし、例えば x2, y=3 が①の整数解の1つで
あることに気がつけば、これを用いて解いてもよい。
本間のように,x,yの係数が比較的小さいときは,整
数解の1つを直接見つけて解いてしまった方が早い場
合もある。
αを6で割った商をQ,
余りをrとすると
a=bq+r
◆まず、①の右辺を1とし
た方程式 12x-7y=1
の整数解を求める。
このときy=12k+15
x,yの一方が定まれば
nも決まる。
84k + 109≦999 から
999-109
ks.
84
= 10.5......
12・27・3=3 と①から
12(x-2)-7(y-3)=0