Question

名無し

n+1と14の最大公約数に等しくなる理由を教えてください

と     はト       最大公約数が 7 になるような 100 以下の 自然   ーー
121    10z寺52 の最大公】                                   引然数      CE
1 1 23z 二                                                                  2

23ヵ寺121 =(10ヵ圭52)・2十3z圭17
10ヵ52=(3z十17)・3ヵ十1
3z十17 =(z填1)・3十14

よって、23ヵ121 と 10z二52 の最大公約数は, 上と 4 の最大公約数に介し

ヵ二1 と 14 の最大公約数が 7 であるとぎ, 1 は 7 の倍数であるが, 2 の他数でな

      2

1ミ<ヵミ100 より 2ミカ1ミ101 であるから
ミルミ      ミッ1ミ                     (の組仙
ヵ二1=7。 21。35、49, 63, 77,91       7ul1  29 他狼『v

=で   z三6、20, 34,。 48, 62, 76, 90         誠大約数條 中
人っ6 (3いす3。-

Answer 1

あ

整数abprを用いて証明します。

aをｂで割った時の商をp余りをrとする。
aとbの最大公約数をG
bとrの最大公約数をgとする。

a＝bp＋ｒであり、右辺はgで割り切れるからaもgで割り切れる。
よってaとbは共にgで割り切れ、最大公約数がGだからG≧g ·····①が成立する。

またa－bp＝rより右辺はGで割り切れるのでrはGで割り切れる。
よってbとrは共にGで割り切れ、最大公約数がgだからg≧G ·····②が成立する。

①、②よりG＝g

このように証明できます。

名無し

ありがとうございます！