Question

ぷりん🍮

整数の性質
どうしてm+1と14の最大公約数に分けるのですか？

類 approach p.26 問題49
52 (最大公約数)
5m +194m +18 の最大公約数が7となるような100以下の自然数mは何個あるか。 [岡山商科大]

52 (最大公約数)
ポイント
ユークリッドの互除法を用いて最大公約数を考える
ユークリッドの互除法を用いて, 5m +19 と 4m +18 の最大公約数
をっ
+1と14の最大公約数にする。
14 との最大公約数が7となる条件は、7の倍数であり2の倍数
でないこと。
5m +19と4m +18にユークリッドの互除法を適用すると
5m +19=(4m+18)·1+m+1
4m+18= (m+ 1) ･ 4 + 14
よって, 5m +19 と 4m +18 の最大公約数は,m+1と14の
最大公約数に等しい。
14=2.7 であるから m+1と14の最大公約数が7となると
き, m+1は7の倍数であるが, 2の倍数ではない。
これと2≤m + 1 ≤101 から
m+1=7,21,35,49, 63,77,91
よって
m=6,20,34,48,62, 76,90
ゆえに、条件を満たす m は 7個

Answer 1

✨ ベストアンサー ✨

まさ

これについてはユークリットの互除法の定理を覚えるしかないかと思います。

補足をしておくと
解説には 4m+18=(m+1)*4+14 で止まっていますが、これを進めて行くと適当な定数a、bとした時

4m+18=(m+1)*4+14
(m+1)=14a+b
14=7*2+0

となり、今回の最大公約数が7という条件の 7 が出てきます。

これが(m+1),14の最大公約数であり、4m+18,(m+1)、5m+19,4m+18の最大公約数になります。

ポイントの所で2の倍数を除外しているのは
(m+1)=14a+b　(a≠0、b=0)
(m+1)=14a+0 となってしまい、最大公約数が14になるからです。

ぷりん🍮

すごく分かりやすいです！
知りたかったこと＋知らなかったことを知れたので本当に助かりました！！

まさ

頑張ってくださいbb