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は偶数
というものがあったのですが、これは定理として考えて良いのでしょうか？どこかに証明されているサイトか本はあるでしょうか？
みんなの回答
-
a-kuma3
満足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 は偶数です。
どれも、定理、というほどじゃないですよね。
- その他の回答を読む
この質問へのコメント
質問の情報
- 登録日時
- 2011-07-11 08:12:27
- 終了日時
- 2011-07-18 08:15:03
- 回答条件
- 1人5回まで
この質問のカテゴリ
この質問に含まれるキーワード
人気の質問
-
36歳です。卵巣腫瘍疑いで大学病院に10月1日に受診しました。エコーで充実性腫瘍があるから至急MRIと腫瘍マ…
ikkuchaan
1
-
同じような体験をしたことがある人はいますか？。 ある日、お葬式の職業に就きたいなあなんて話題にしてい…
匿名質問者
1
-
私は、【チルスポ】 という名前で、 チルスポット情報を共有するアプリを開発しています。 皆さんの知って…匿名質問者1
-
b型就労支援施設に通っている方に質問です。どういうことが通っていて辛いと感じますか？他の利用者の方と…匿名質問者
-
今行きがかり上で中小企業を相手に民事訴訟の原告と被告で2件の裁判を抱えています。しかし何も深刻さはな…
asnaro_71
1