-
562
基本
例題 137 1次不定方程式の応用問題
3で割ると2余り5で割ると3余り 7で割ると4余るような自然数nで最小
基本 135 136
のものを求めよ。
5で割ると3余る数のうち, 7でも3でも割り切れる数
は、7・35・4+1 の両辺を3倍して
3・7・3=3・5・4+3
指針 条件を満たす自然数を小さい順に書き上げると
[1] 3で割ると2余る自然数は
7で割ると4余る数のうち, 3でも5でも割り切れる数
は, 3・57・2+1の両辺を4倍して
1.3で割ると2余る数のうち,5でも7でも割り切
5-7-3-11+2
れる数は
下線の数を見つけるため
に、ここでは1余る数を
もとにしているが、直ち
63 としてもよい。 そ
の次の4・3・560も同様。
[2] 5で割ると3余る自然数は
3. 8. 13, 18, 23, ······
[3] 7で割ると4余る自然数は
2, 5, 8, 11, 14, 17, 20, 23,
4, 11, 18, 25, 32, 39, 46, 53.
[1] [2] に共通な数はであるから,「3で割ると2余り5で割ると3余る」 自然数
最小数は8で3と5の最小公倍数 15ず
つ大きくなる。
は
[4] 8, 23, 38, 53, 68,
求める最小の自然数nは, [3] と [4] に共通な数 (口の数) 53であることがわかる。
このように、書き上げによって考える方法もあるが、条件を満たす数が簡単に見つか
らない (相当多くの数の書き上げが必要な) 場合は非効率的である。
そこで、問題の条件を1次不定方程式に帰着させ、その解を求める方針で解いてみ
よう。
4・3・5=4・7・2+4
したがって, 5・7+3・7・3+4・3・5=35+63+60=158は,
3で割ると2余り, 5で割ると3余り, 7で割ると4余る
数である。
3, 5, 7の最小公倍数は105であるから, 求める自然数
nは
n=158-105=53
別解2.3で割ると2余り, 5で割ると3余り 7で割ると 合同式を用いた解法。
4余る自然数をnとすると n=2 (mod3) ...... ①.
n=3 (mod5) ... ②, n=4 (mod7)
563
③
①から
n=3s+2 (s は整数)
・・・... ④
④を② に代入して
3s+2=3
すなわち 3s=1
解答
nはx, y, zを整数として,次のように表される。
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
3x+2=5y+3
かつ 5y+3=7z+4と
して解いてもよいが. 係
数が小さい方が処理しや
すい。
1=6であるから
3s=6
法5と3は互いに素であるから s=2 (以上 mod 5)
ゆえに, s=5t+2 (tは整数) と表され, ④に代入すると
n=3(5t+2)+2=15t+8 ⑤
3(x-2)=5(y-1)
すなわち
3と5は互いに素であるから, kを整数として, x-2=5k
と表される。
よって
x=5k+2 ····.. ②
② を3x+2=7z+4に代入して
このとき y=3k+1
⑤を③に代入して 15t+84 すなわち 15t-4
14t=0であるから t=-4 (以上mod 7)
ゆえに,t=7k-4(kは整数) と表され, ⑤ に代入すると
n=15(7k-4)+8=105k-52
求める最小の自然数nは,k=1を代入して
n=105・1-52=53
法5と3は互いに素であ
るから, 両辺を3で割る
ことができる。
15cm45 として、法と
15は互いに素であるか
ら、両辺を15で割って
3とすることもでき
る。
3(5k+2)+2=7z+4
<3x7z=2から
ゆえに
7z-15k=4 ...... ③
7・(-2)-15・(-1)=1
3(x-3)-7(z-1)=0
ゆえに、を整数として
x=71+3
両辺に4を掛けて
検討
7・(-8)-15・(-4)=4 ...... ④
③④から
7(z+8)-15(k+4)=0
すなわち
7(z+8)=15(k+4)
7と15は互いに素であるから, lを整数として, z+8=151
と表される。
これとx=5k+2 を等置
して 5k+2=7/+3
よって 5k-77-1
これより1が求めら
れるが, 方程式を解く手
間が1つ増える。
よって
z=157-8
これをn=7z+4 に代入して
n=7(151-8)+4=1051-52
求める最小の自然数nは,l=1を代入して
n=53
<1054-52>0 とすると
52
1>
105
百五減算
ある人の年齢を3, 5, 7でそれぞれ割ったときの余りを a,b,c とし、n=70a+216+15e
とする。 このnの値から105を繰り返し引き, 105より小さい数が得られたら、その数が
その人の年齢である。 これは3, 5, 7で割った余りからもとの数を求める和算の1つで、
百五減算と呼ばれる。 なお、この計算のようすは合同式を用いると、次のように示される。
求める数をxとすると, xa (mod 3), x=b (mod5) c (mod 7) であり,
n=70a=1.4=qx (mod3)
nm15cm1c=c=x (mod 7)
=2101.60x(mod5),
よって、nxは3でも5でも7でも割り切れるから, 3, 5, 7の最小公倍数 105で割り切れ
る。ゆえに、を整数として, n-x=105kから
n105
このkが105を引く回数である。
練習 3で割ると2余り, 5で割ると1余り、 11 で割ると5余る自然数のうちで、
● ユークリッドの互法と1次不定方程式