Question

とまと

「nは50以下の自然数とする。5n+9と2n+4が互いに素であるようなnの個数を求めよ。」の問題で、写真が回答なのですが、線を引いているところの意味がわかりません。教えてください🙏🏻

292 5 +9=(2n+4) ・2+n+1 H
2n+4=(n+1) ･2+2
よって, 5n +9 と 2n +4の最大公約数はn+1
と2の最大公約数に等しいから, n+1と2が互
いに素であるとき, 5n+9 と 2n +4は互いに素
である。
2≦n+1≦51 であり,この範囲に2の倍数は 25
個あるから, 求めるnの個数は
50-25=25(個)

Answer 1

✨ ベストアンサー ✨

aporon

5n+9=(2n+4)×2+(n+1)
つまり、5n+9を2n+4で割った余りはn+1
ユーグリッドの互除法より、
2n+4=(n+1)×2+2

よって、n+1と2の最大公約数に等しい

とまと

ユークリッドの互除法をしていって、余り2つの最大公約数が5n+9と2n+4の最大公約数って事ですか？？

aporon

余り２つのってのが違います
a=bq+r
aとbの最大公約数はbとrの最大公約数に等しい
これがユーグリッドの互除法です

とまと

理解出来ました！ありがとうございます！