最大公約数の性質: m,nの最大公約数と3m+4n, 2m+3nの最大公約数の一致を示す方法

この問題では、2つの自然数m,nについて、最大公約数(gcd)に関連する性質を示します。具体的には、m,nの最大公約数と、3m+4n, 2m+3nの最大公約数が一致することを証明します。

1. gcdの定義と前提条件

m,nの最大公約数をgとし、mとnをそれぞれgで割った形としてm = gm’およびn = gn’と書けます。ここでm’とn’は互いに素であるとします。

つまり、mとnはgで割り切れ、gはm,nの最大公約数です。この状況で、3m+4n, 2m+3nの最大公約数がgと一致することを示します。

まず、m = gm’およびn = gn’を代入して、3m+4nと2m+3nをそれぞれ計算します。

3m + 4n = 3(gm’) + 4(gn’) = g(3m’ + 4n’)

2m + 3n = 2(gm’) + 3(gn’) = g(2m’ + 3n’)

したがって、3m+4nおよび2m+3nの最大公約数は、gと(3m’ + 4n’)および(2m’ + 3n’)の最大公約数に等しいことが分かります。

m’とn’は互いに素であるため、(3m’ + 4n’)と(2m’ + 3n’)の最大公約数は、m’とn’の間に存在する公約数に依存しません。したがって、gcd(3m+4n, 2m+3n)はgcd(m,n) = gに一致します。

このように、m,nの最大公約数がgであるとき、3m+4n, 2m+3nの最大公約数もgに等しいことが証明できました。この結果は、m’とn’が互いに素であるという性質を活用することで得られます。