Question

まふゆ

この問題を合同式（mod）を使って計算することはできますか？

12 で割ると1余り, 7で割ると4余る3桁の自然数のうち最大の数を求めよ。
基本例題123 1次不定方程式の整数解の利用
OOOO0
基本122
CHART
SOLUTION
1次不定方程式の整数解の利用
条件から ax+6y=c の形に変形
条件を満たす自然数は, 整数x, yを用いて, 12x+1, 7y+4と2通りに表される
そこで,まず方程式 12x+1=7y+4 の整数解を求め, それから題意の自然数を
求める。
解答
求める自然数をnとすると, nはx, yを整数として, 次のよう
に表される。
aをもで割った商をg.
| 余りをrとすると
a=bq+r
n=12x+1,
n=7y+4
よって
12x+1=7y+4
『すなわち
12x-7y=3
の
x=3, y=5 は,12.x-7y=1 の整数解の1つであるから まず, ① の右辺を1とし
た方程式 12x-7y=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)
の-2から
すなわち
12 と7は互いに素であるから,3を満たす整数xは
x-9=7k すなわち x=7k+9 (kは整数)
*nを求めるためには、
x, yの一方が求まれば
よい。
と表される。
したがって
n=12x+1=12(7k+9)+1=84k+109
84k+109 が3桁で最大となるのは, 84k+109<999 を満たす
kが最大のときであり, その値は
このとき
参考 解答では, 12x-7y=1 の整数解の1つを求め,それか
ら3を導いて解いた。
しかし,例えばx=2, y=3 がOの整数解の1つであ
ることに気がつけば, これを用いて解いてもよい。
本間のように,x, yの係数が比較的小さいときは, 整数
解の1つを直接見つけて解いてしまった方が早い場合も
全84k+109 999 から
999-109
k=10
kS
84
n=84·10+109=949
=10.5………
* 12-2-7-3=3 と①から
12(x-2)-7(y-3)=0
ある。

Answer 1

✨ 最佳解答 ✨

き

一応合同式を使って解くこともできますが、連立1次合同方程式を解くことになります。計算量はかなり少ないですが、合同式のややこしい性質を使うことにもなるので合同式に相当慣れていないのであればあまりお勧めはしません。

まふゆ

わざわざありがとうございます！！🙇‍♀️
合同式もっと詳しく勉強してみようと思います。