アットランダム≒ブリコラージュ

ユークリッドの互除法

1.除法
整数aを整数bで割る割り算では，a/b=q+r/b において 0?r/b<1となるので， 商qはa/bを超えない最大の整数である． 一般に実数xに対して，xを超えない最大の整数を[x]と書き表す． この記号を用いると， q=[a/b]と書き表すことができる．

整数の集合 Zでは除法の原理が土台になる． 代数的整数といわれる世界では，この除法の原理は成り立たない． そこでは新たな考え方が必要になる． 一般化された「代数的整数」に対してわれわれの整数を「有理整数」という． 有理整数でない代数的整数は後に「ガウス整数」でその端緒を紹介する． この『整数論入門』は基本的に有理整数の世界の探求である．

これからは，特に断らなければ記号 N, Z, Q, R, C はそれぞれ， 自然数，整数，有理数，実数，複素数の集合を表すものとする．

2. 最大公約数

整数a, b, c, ・・・ の最大公約数を，座標と混同する恐れのないときは(a, b,c,・・・) と書く．
整数a, b, c,・・・ の最大公約数が1であることを簡単に 「公約数をもたない」という．この場合， (a, b, c, ・・・)=1． 特に二つの整数a, b が公約数をもたないとき，つまり (a, b)=1のとき，a, b は互いに素であるという．

3. ユークリッドの互除法

ここで，最大公約数を求める一般的な方法であるユークリッドの互除法をまとめよう．

(ユークリッドの互除法)
a > b > 0 を整数とし, a を b で割った余りを r とする．このとき
(a, b) = (r, b)
が成り立つ．
数列 { r_n } を次のように定める．
r_1=a, r_2=b
n ?2 のとき
　r_n > 0 なら、r_(n+1)=r_(n-1) を r_n で割った余り
　r_n=0 なら、r_(n+1)=0

このときある番号 N で r_N ≠ 0で r_(N+1)=0となるものがあり，このとき
r_N=(a, b)

が成り立つ．

証明は、http://aozoragakuen.sakura.ne.jp/suuronN/node11.html　を参照。Orz〜

これが最大公約数を求める一般的な方法で ユークリッドの互除法 といわれる． このように「必ずできる一般的方法」をアルゴリズムという． ユークリッドの互除法はアルゴリズムの基本例である．

三つ以上の整数a, b, c, ・・・ の最大公約数もこれを応用して求めることができる．

a が a, b, c, ・・・ のなかの最小の数とする． a で他の数を割った余りを b', c', ・・・とする．すると上の定理と同様に
(a, b, c,・・・)=(a, b', c',・・・)


この操作を繰り返すと余りのなかに0が現れる．それを取り除いてさらに同様の操作を繰り返す． ついにはただひとつの数が残る．それが a, b, c, ・・・ の最大公約数である．

問題
(6188, 4709) を求めよ。

(6188, 4709)=(4709, 1479)
=(1479, 272)
=(272,119)
=(119,34)
=(34,17)
=17

問題
(629, 391, 255)=(119,136,255)=(119,17,17)=17

a < b < c のとき、
一番小さい数 c を引いた、a-m*c, b-n*c, c の中に、最大公約数はあるはずということにほかならない分けですよね。


画像：ユークリッド/エウクレイデス　Eucleidesエウクレイデス〔ユークリッド〕 (c. 330-235 B.C.)　
art-random.main.jp/ samescale/090.html　より Orz〜
「・・・一説によると、アテナイで、プラトンに数学を師事したともいわれ、のちプラトンの死後、彼が創始した哲学学校アカデメイアで数学の教師の１人だった時期があると見られている。確実なのは、彼が古代の卓越した数学者で、アレクサンドリアで数学を教えていたこと、またそこで数学の一派をなしたことである。ユークリッド幾何学の祖で、原論では、平面・立体幾何学、整数論、実数論などの当時の数学が公理的方法によって組み立てられているが、これはギリシャ数学の一つの成果として受け止められている。・・・「幾何学原論」は、ピタゴラス以来のあらゆる初期ギリシャの数学的知識を体系的に編集したものである。・・・扱われている内容は、ピタゴラスの定理をはじめとする平面幾何学、相似図形、立体幾何学などのほか、(a+b)a=aa+abのような恒等式や最大公約数、素数といった、今日私たちが代数的に扱っているものも含まれる。中世、近世を通じてユークリッド幾何学は唯一の真なる幾何学とされ、本書は幾何学の教科書として用いられた。19世紀になって、ロバチェフスキーやリーマン等が非ユークリッド幾何学の体系を作り上げたが、現在もなお中学や高校で教えられる図形問題はユークリッド幾何学である。その意味で、世界で最も長く用いられている教科書と言える」。・・・」

９０歳という長命な方だったんですねえ ^^
同じ頃のアルキメデスに関してはまたいずれ。。。v
軍人に殺されたのはアルキメデスでしたよね。。。^^;

はじめに

わたしにとって数論はこの上なくおもしろく感じる分野です。^^
算数的思考というか推論でついて行けそうな分野でもありそう。。。実際はそうじゃないようですが、、、とまれ、時間ある時に、今の自分の好きな分野を自分のペースで基礎から勉強してみようかということでこの書庫蘭を作りました。
以下のサイトを教科書として（ Orz〜）、、、どこまで進めるか自信ないけど、、、チャレンジをば始めます。^^v

http://aozoragakuen.sakura.ne.jp/suuronN/node1.html
数論初歩


画像：ガウス
http://ja.wikipedia.org/wiki/カール・フリードリヒ・ガウス　より
「ヨハン・カール・フリードリヒ・ガウス（Johann Carl Friedrich Gauss(Gau?)、1777年4月30日 - 1855年2月23日）はドイツの数学者、天文学者、物理学者である。彼の研究は広範囲におよんでおり、特に近代数学のほとんどの分野に影響を与えたと考えられている。数学や磁気学の各分野には彼の名が付いた法則、手法等が数多く存在する。子供の頃から数学の才能を発揮した。

生い立ちと幼年期
ガウスはドイツのブラウンシュヴァイクで煉瓦職人の父親と、清楚な母親の元に生まれた。子供の頃から彼は神童ぶりを発揮し、逸話として、小学校での話が残っている（彼は後年好んでこの話をしたそうだ）。ある時、1から100までの数字すべてを足すように課題を出された。それを彼は、1 + 100 = 101、99 + 2 = 101、98 + 3 = 101… となるので答えは 101×50 = 5050 だ、と即座に解答して教師を驚かせた[1]。実際、算術の教師は彼の才能を見るにつけ、このような天才に自分が教えられることは何もないと言ったそうである。また1792年頃、15歳当時の彼は、一日15分ずつの予備の時間を当てて1000個ずつの自然数にそれぞれ幾つの素数が現れるかを調べ、その次第に減っていく様子から、約100年後に証明されることになる素数定理を予想した。
ガウスは言葉が満足にしゃべれるようになる前から、誰から学ぶこともなく計算ができたといわれている。三歳になるかならないかの頃、父親が給料計算を間違えたことを指摘したという[2]。 七歳になるとガウスは地元の小学校に入った。ここでビュットナー校長によって算数を習うものの、すでにガウスは習得済みであった。このため、校長は自費でより高級な算術の教科書をハンブルグから取り寄せたが、すぐに読み終えてしまった。ここで校長は「これ以上教えられることはない」と述べたようである。そこで校長は、助手であるヨハン・バーテルスにガウスをまかせることにした。ガウスとバーテルスは共に学び、教科書を改良したり、新しい概念を生み出すようになった。・・・大学では、ハンガリー貴族であるヴォルフガング・ボヤイと友人になった。ボヤイがガウスの家を訪ねた際、ガウスの母に息子は優秀なのかとたずねられたところ、ガウスはヨーロッパ一の数学者になるでしょうと答え、母は泣き崩れたという。

思想とおもな業績
ガウスは奨学金を得て大学に進み、数々の重要な発見を行った。彼は、古代ギリシアの数学者達に起源を持つ定規とコンパスによる作図の問題に正確な必要十分条件を与え、正17角形が作図できることを発見した（1796年）。作図できる正(素数)角形は古来から知られていた正三角形と正五角形のみだと考えられていたのでこの発見は当時の数学界に衝撃を与えた。作図できる正多角形の種類が増えるのは約二千年ぶりのことであった。彼はこの結果を非常に喜び、この成果である正17角形を墓標に刻むように申し入れた（結局、これは実現されなかったが、彼の記念碑には正17角形が刻まれている）。また、この発見の日より、数学的発見を記述したガウス日記をつけはじめ、また自分の将来の進路を数学者とすることに決めたといわれる。学位論文で彼は代数学の基本定理を最初に証明した。後に彼はこの問題に対して4つの異なる証明を行い、複素数の重要性を決定付けた。
ガウスのもっとも偉大な貢献は数論の分野である。この分野だけが、その全貌ではないにしろガウスの研究が体系的にまとめられて出版された。それが1801年に発表したDisquisitiones arithmeticae（邦題『ガウス整数論』）であり、そのほとんどのページが二、三元の二次形式の研究に当てられている。この本は、数の合同の記号を導入し合同算術の明確な表現を与え、平方剰余の相互法則の初の完全な証明などが与えられている。自然数の素数による一意分解の定理が明確に言明され、証明されたのもこの本が最初であった。しかしこの本は、あまりにも時代をぬきんでた難解な著作であり、その上出版社の問題から発行部数が相当低かったこともあって、実際には当時理解できるものはほとんどいなかった。結局それがようやく理解されるようになるのは、それを詳しく解読し講義したディリクレの時代になってからである。
・・・
ガウスの言葉

数学は科学の女王であり、数論は数学の女王である。
僕は言葉を話すようになる前から計算をしていた
数値の法則は目に見えて現れるものだが、その証明は宇宙の闇に深く横たわっている（？曖昧、数値は数論ではないかと考えられるが、不明 <- (数値の意味は、近世数学史談に多く語られている)）
狭くとも深く
僕に出された多くの問題はそれを見た瞬間に答えがわかった。・・・」