n を正の整数とする.ユークリッドの互除法を用いて 2n + 13 と n + 7 の最大公約数を求

n を正の整数とする.ユークリッドの互除法を用いて 2n + 13 と n + 7 の最大公約数を求めなさい。

この問題を教えてください！

No.1 ベストアンサー 回答者： masterkoto 回答日時： 2020/06/24 15:01

割られる数と割る数の最大公約数と割る数とあまりの最大公約数は一致する　というのがユークリッドの互除法の意味です

ということで割り算して余りを出して、　割る数と余りで割り算して というようなことを繰り返し実行です
ただし、(2n+13)÷(n+7)=2あまり-1　みたいにあまりが負の数になるとややこしいので
基本公式：(割られる数)＝(割る数)x(商)＋(あまり)　を利用して
今回は
2n+13を割られる数　n+7は割る数とみなし、余りがマイナスにならないように商を調節します

基本公式より
2n+13=(n+7)x1+(n+6)だから
2n+13をn+7で割ると余りはn+6
ユークリッドの互除法で、2n + 13 と n + 7 の最大公約数はn+7とn+6の最大公約数に等しい！
再び基本公式利用で
(n+7)=(n+6)x1+1より
n + 7とn+6 の最大公約数はn+6と1の最大公約数に等しい
n+6と１の最大公約数は１なので求めるべき公約数も１

このような流れになります