人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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は偶数

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

●質問者: koime_ryokutya
●カテゴリ:コンピュータ インターネット
✍キーワード:Java サイト バイナリ ユークリッド 偶数
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● a-kuma3
●34ポイント

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


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


2 ● rsc
●33ポイント

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

●p数学2

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

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

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

ユークリッド原論 追補版

ユークリッド原論 追補版

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ