gcd(最大公約数)の性質について

『Javaで作って学ぶ暗号技術』という本を読んでいるのですが、その中の「バイナリー・ユークリッド互除法」で利用されているgcdの性質で

(1)a,bともに偶数なら、gcd(a,b) = 2gcd(a/2, b/2)
(2)aのみ偶数で、bが奇数のとき、gcd(a,b) = gcd(a/2, b)
(3)a,bともに奇数のとき、a-bは偶数

というものがあったのですが、これは定理として考えて良いのでしょうか?どこかに証明されているサイトか本はあるでしょうか?

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2011/07/11 08:12:27
  • 終了:2011/07/18 08:15:03

回答(2件)

id:a-kuma3 No.1

a-kuma3回答回数4442ベストアンサー獲得回数18252011/07/11 12:32:10

ポイント34pt

(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 は偶数です。


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

id:rsc96074 No.2

rsc回答回数4387ベストアンサー獲得回数4012011/07/11 14:03:07

ポイント33pt

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

●p数学2

26、奇数引く奇数は偶数である

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

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

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません