gcd（最大公約数）の性質について

(1)a,bともに偶数なら、gcd(a,b) = 2gcd(a/2, b/2)

a と b ともに偶数であれば、公約数に 2 が含まれますから、以下のようにあらわすことができます。

a = 2 D m

b = 2 D n

※ m と n は、互いに素

このとき、a と b の最大公約数は 2D です。

a/2 と b/2 は、先の数字を使うと、以下のようにあらわされます。

a/2 = D m

b/2 = D n

m と n は、互いに素なので、a/2 と b/2 の最大公約数は D です。

gcd(a, b) = 2D

gcd(a/2, b/2) = D

なので、gcd(a, b) = 2 gcd(a/2, b/2) となります。

(2)aのみ偶数で、bが奇数のとき、gcd(a,b) = gcd(a/2, b)

a のみ偶数ということなので、公約数には 2 が含まれません。a は偶数なので、

a = D (2m)

b = D n

このとき、a と b の最大公約数は D です。

a/2 を考えると、以下のようになりますが、

a/2 = D m

b = D n

2m と n は、互いに素なので、m と n も互いに素になります。

なので、a/2 と b の最大公約数は D となります。

なので、gcd(a, b) = gcd(a/2, b) となります。

(3)a,bともに奇数のとき、a-bは偶数

a, b ともに奇数なので、以下のようにあらわすことができます。

a = 2m + 1

b = 2n + 1

ここで、a - b を考えます。

a - b = (2m + 1) - (2n + 1) = 2(m - n)

となるので、a - b は偶数です。

どれも、定理、というほどじゃないですよね。

　(3)は、「『原論』９巻命題26」のようです。証明は上の方がされているのでいいと思いますが、たぶん、下記の本あたりを見ればあると思います。(^_^;

●p数学２

２６、奇数引く奇数は偶数である

http://www.geocities.jp/ja1tmc/psuugaku2.html

●ユークリッド原論　追補版 [単行本] 中村 幸四郎 (翻訳), 寺阪 英孝 (翻訳), 伊東 俊太郎 (翻訳), 池田 美恵 (翻訳)

ユークリッド原論　追補版

• 作者: 中村幸四郎,寺阪英孝,伊東俊太郎,池田美恵
• 出版社/メーカー: 共立出版
• 発売日: 2011/05/25
• メディア: 単行本
• この商品を含むブログ (1件) を見る