Question

ひなの

これの解説お願いします🙇‍♀️

50 n は自然数とする。n°+3n+8とn+2の最大公約数として考
えられる数をすべて求めよ。

50 指針 n
2+3袋+8を
(n+2Xn+△)+(自然数)
の形に変形する。
n?+3n+8=(n+2)(2+1)-2+8
よって, n?+3n+8と n+2の最大公約数は,
2+2 と6の最大公約数に等しい。
したがって,最大公約数として考えられる数は,
6の正の約数の1,2,3, 6である。
8

ユークリッドの互除法

Answer 1

ひま

多項式の割り算を実行して、gcd(a,b)=gcd(a-kb,b)
を利用
n+2と7のgcdに帰着する

ひなの

7ってなんですか。

ひま

6だ
というか解答あったのか
どっか読んでわからないとこありますか？

ひなの

式はわかるんですけど、文章からわかりません。

ひま

a,bとa,b-kaのgcdが等しいってのは有名な性質で、証明は
a,bのgcdをgとすると、a=pg,b=qgとできてp,qは互いに素
b-ka=qg-kpg=(q-kp)g
となる
ここでpとq-kpに共通素因数tがあるとすると
p=p't,q-kp=q'tとできてp',q'は互いに素
q-kp't=q't⇔q=(kp'+q')tとなってpもqもtの倍数となるからp,q互いに素に反する
よってpとq-kpも互いに素(背理法)
だからaとb-kaのgcdもgになる
って感じ、今回はk=n-1ね
テストでは証明して使ったほうがいい気がする