元気カアップ問題 101
CHECK2
難易度
CHECK I
CHECKS
17 で割ると6余り, 12 で割ると8余るような正の3桁の整数の内,最小
のものと最大のものを求めよ。
ニントリ 求める3桁の整数をnとおくと,題意より n=17.x+6=12y+8
,y:整数)となるので, これから, 1次不定方程式17x-12y=2が導ける
んだね。計算はメンドゥだけれど, 解法のパターンに従って解いていこう。
解答&解説
ココがポイント
17で割ると6余り,12で割ると8余る3桁の正の
整数をnとおくと, これは, 整数x, yを用いて
次のように表される。
n=17x + 6
n=12y + 8
-② (x, y: 整数)
1, 2よりnを消去してまとめると,
17x-12y= 2 …③ (x, y:整数)となる。
- 17x +6= 12y + 8
17.x-12y=2
17と12は互いに素より, ③の代わりにまず,
17x-12y=1 …④ の1組の整数解(x1, yi)を,
2つの係数17, 12についての右の
互除法
ユークリッドの互除法を用いて求める。
17 = 12 ×1+5⑤
の, 6, 5より,
12 = 5×2+2
|5-2.2=1 ……
2=12-5·2 ……6
5=2×2+1 ⑦
(5=17-12 … 5
のに6を代入して,
5-(12-5.2) · 2=1
2=1×2
最大公約数g=1
より,17 と 12 が
互いに素であるこ
とが分かる。
5·5-2-12=1 ………8
1