数論初歩
青空学園数学科 2009 年5月31日
はじめに
数は人間にとって大変身近なものです．数はまず自然数であり，そして整数です．整数の性質を 調べる整数論は高校数学のなかでも大切な分野です．しかし，現在の高校の教科書ではまったく軽 視されています．高校生向けの参考書にいちおうは載っているのですが，どうしても入試問題に引 きずられて記述されるため，行きあたりばったりで体系的でない切れ切れの知識が積みあげられ，
小手先の方法論が先行し，かえってわかりにくくなっているのが現状です．
これはたいへん残念なことです．整数論は初等的な段階から数学のおもしろさ，美しさを実感す ることができる分野です．また，体系立てて学ぶことで，少ない原理を生かして自由に応用すると いう，数学の大切な精神を身につけることができます．さらにその結果，入試問題も見通しよく解 くことができます．
青空学園の『数論初歩』は，高校生から大学初年級の諸君が体系的に数論の基本を学ぶ教科書で す．あつかう範囲は，おおよそ『初等整数論講義』(高木貞治,共立出版)の第1章，第2章に対応 し，現代的な抽象代数学の方法を用いない有理整数の古典理論です．平方剰余の相互法則を，いく つかの初等的な方法で証明することが主眼です．
演習問題を，その内容を理解するのに適した「練習問題」と，関連する「入試問題」で構成しま した．入試問題では，大学入試問題のなかで整数を取りあげいてる意味のある問題を紹介し，関連 して学べるようにします．ここで用いた大学入試問題の一覧表も作りました．ほぼ意味ある整数問 題のすべてが集められています．いくつかの基本的な内容の入試問題は出典をあげずに練習問題と していることを断っておきます．練習問題の解答は定理やその他の結論を用いるようにし，逆に入 試問題の解答はできるだけそのなかで完結する方法で解くようにしています．
「定理」は一般的な結果です．「補題」は定理の証明に必要な準備的命題です．これらは通し番号 になっています．
「例」は対話をすすめる材料となる具体的な例や，試しに解いてみる問題です．「注意」は意味通 りです．これらは節毎に【節番号-番号】の形で番号をつけています．
□ は証明など論述文の終わりを意味しています．
高校生の皆さんがとおして勉強するのは大変です．次のようにするとよいでしょう．●のところ を勉強してください．次にできれば○を，前半だけでも読む．そして各節末の「演習問題」，とく に最近の入試問題を集めたものに取り組む．●や○以外のところの演習問題もやってみてくださ い．残したところは大学生になってからぜひ読んでほしいです．
1. 整数の除法●
2. 最大公約数と最小公倍数●
3. 一次不定方程式●
5. 合同式●
6. オイラーの関数 ○ 7. １のn乗根○
8. フェルマの小定理●
9. 原始根と指数○
10. 平方剰余の相互法則
11. ガウス整数
12. ペル方程式の解の構造と存在●
13. 二次行列と実数の連分数展開 14. 数の幾何○
15. 二次無理数の連分数展開とペル方程式の解の構成
入試問題一覧
1章
［96大阪教育大］【1】／式の除法 2章
［98お茶の水大］【2】／ユークリッドの互除法の原理
［91阪大理系後期］【3】／ユークリッドの互除法の長さの評価 3章
［89京大理系後期］【4】／格子点と三角形の面積
［91東大理系前期］【5】／直線と格子点の距離
［93早稲田］【6】／連分数による一次不定方程式の解
［立命館大改題］【7】／一次不定方程式の一般解
［00京大理系後期］【8】／一次不定方程式の一般解，格子点
［00阪大理系前期］【9】／一次式で数を表す
［00大阪女子大］【10】／一次不定方程式の解の存在
［90京大理系後期］【11】／三角関数の値の集合
［02金沢大理系後期］【12】／領域内格子点の対応 4章
［88群馬大］【13】／n!における素因数2の個数
［97京大文系前期］【14】／約数の論証
［98上智大］【15】／約数の個数とその和
［98京大文系後期］【16】／約数の論証
［99京大文系後期］【17】／ピタゴラス数の論証
［02九大理系前期］【18】／約数の和に関する論証 5章
［82名古屋市大］【19】／倍数の証明
［東工大］【20】／倍数の証明
［82九大］【21】／n次方程式と整数
［01京大文系前期］【22】／倍数の証明 7章
［70東大理系］【23】／1のn乗根，原始n乗根
［01京大理系］【24】／1のn乗根
［01京都府立医大］【25】／1のn乗根からなる集合 8章
［98奈良女子大改題(3)追加］【26】／フェルマの小定理の数学的帰納法による証明 9章
［95京大文系後期］【27】／フェルマの小定理と応用 10章
［98横国大文系後期］【28】／3個の平方数の和にならないための条件
11章
［01京大理系前期］【29】／ガウス整数の素数べき
［02慶応医］【30】／素数の平方数の和への分解の初等的証明 12章
［95大阪府大］【12.1】／ある数列はペル方程式を満たす
［95明治大］【12.2】／ペル方程式の解はある数列で得られる
［85東工大］【12.2】／ペル方程式の解の構造
［98お茶の水女子大］【31】／ブラーマグプタの恒等式
［01滋賀医大］【32】／双曲線上の格子点 13章
［04名古屋大理系後期］【33】／√
2の近似有理数
［00上智大後期理工］【34】／無理数の近似有理数 14章
［66京大］【35】／格子点と正方形領域
［新潟大過去問］【36】／格子点と平行四辺形領域
［92東大］【37】／線分上の格子点
［お茶の水女子大改題］【38】／格子点を頂点とする正多角形
［03お茶の水女子大理系後期］【39】／格子点を頂点とする正三角形
目 次
1 整数の除法 9
1.1 整数の除法 . . . . 9
1.2 整式の除法 . . . . 11
1.3 演習問題. . . . 12
1.3.1 関連入試問題 . . . . 12
2 最大公約数と最小公倍数 14 2.1 最大公約数と最小公倍数 . . . . 14
2.2 ユークリッドの互除法 . . . . 16
2.3 演習問題. . . . 18
2.3.1 関連入試問題 . . . . 18
3 一次不定方程式 20 3.1 一次不定方程式の解の存在 . . . . 20
3.2 一次不定方程式の一般解と解の構成 . . . . 24
3.3 演習問題. . . . 31
3.3.1 関連入試問題 . . . . 31
4 素数 34 4.1 素数 . . . . 34
4.2 演習問題. . . . 36
4.2.1 関連入試問題 . . . . 38
5 合同式 40 5.1 合同式 . . . . 40
5.2 一次合同方程式 . . . . 43
5.3 合同方程式の解法 . . . . 46
5.4 演習問題. . . . 50
5.4.1 関連入試問題 . . . . 52
6 オイラーの関数ϕ(n) 53 6.1 オイラーの関数ϕ(n) . . . . 53
6.2 メービスの反転公式 . . . . 57
6.3 演習問題. . . . 59
7 １の n乗根 60 7.1 １のn乗根 . . . . 60
7.2 演習問題. . . . 62
7.2.1 関連入試問題 . . . . 63
8 フェルマの小定理 64
8.1 フェルマの小定理 . . . . 64
8.2 素数分布論への応用 . . . . 65
8.3 循環小数. . . . 68
8.4 演習問題. . . . 71
8.4.1 関連入試問題 . . . . 72
9 原始根と指数 73 9.1 原始根 . . . . 73
9.2 指数 . . . . 75
9.3 演習問題. . . . 78
9.3.1 関連入試問題 . . . . 79
10 平方剰余の相互法則 80 10.1 平方剰余とルジャンドルの記号 . . . . 80
10.2 整数を平方数の和に分解すること . . . . 82
10.3 平方剰余の相互法則 . . . . 85
10.4 ガウス和を用いる証明 . . . . 89
10.5 三角法の補題による証明 . . . . 94
10.6 演習問題. . . . 96
10.6.1 関連入試問題 . . . . 97
11 ガウス整数 98 11.1 ガウス整数 . . . . 98
11.2 演習問題. . . . 102
11.2.1 関連入試問題 . . . . 103
12 ペル方程式の解の構造と存在 104 12.1 ペル方程式の解の構造 . . . . 104
12.2 ディリクレの原理 . . . . 112
12.3 ペル方程式の解の存在 . . . . 113
12.4 演習問題. . . . 115
12.4.1 関連入試問題 . . . . 115
13 二次行列と実数の連分数展開 116 13.1 実数のメービス変換と連分数展開 . . . . 116
13.2 近似分数. . . . 119
13.3 実数の対等 . . . . 122
13.4 演習問題. . . . 123
13.4.1 関連入試問題 . . . . 123
14 数の幾何 125 14.1 格子点と近似分数 . . . . 125
14.2 連分数と格子点 . . . . 127
14.3 演習問題. . . . 131
14.3.1 関連入試問題 . . . . 131
15 二次無理数の連分数展開とペル方程式の解の構成 133 15.1 二次無理数の連分数展開 . . . . 133
15.2 ペル方程式の解の構成 . . . . 137
15.3 解構成のアルゴリズム . . . . 142
15.4 演習問題. . . . 145
16 問題解答 147 16.1 演習問題解答 . . . . 147
16.2 入試問題解答 . . . . 174
1 整数の除法
整数の系統だった勉強をはじめよう．ところでこれから考えていく対象である「整数」とは一体 何か．それはどのようなものとして把握されるのか．
それを明らかにするためにはまず「自然数」を明確につかまなければならない．
人間がはじめて身につける数が自然数である．子供ははじめ，「3個のリンゴ」と「3枚の皿」の 間に同じ「3」があることを知らない．あくまで「3個のリンゴ」と「3枚の皿」だ．それが同じ
「3」であることを知ることができるのは，2〜3歳のころではないかといわれている．「3個のリン ゴ」を「3枚の皿」に一つずつ乗せると，皿が不足もせず余りもしない．なにか「同じ」ことが成 り立っている．その「同じこと」を個数としてつかむ．これが自然数の始まりだ．もちろん順序と しての自然数も獲得され，数の世界が広がる．
このように言っても，これが本当に子供のなかで起こることなのか，それとも，集合と集合の要 素の対応という考え方を知った後の理屈づけに過ぎないのかは，わからない．ただいずれにしても，
自然数の獲得には長い人類の歴史と，それを身につける子供の成長とがあることを覚えておこう．
数学的にいえばここでさらに転換である．数学は自然数を土台に発展してきた．ところが19世 紀になって集合論がはじまり，数学の基礎が問題にされるにつれ，自然数をどのように把握し直 すのかが問われるようになった．自然にある対象をつかみ直す，これが19世紀の基本思想だった．
あらためて自然数とは何か，それはどんなものかを，人は問うたのだ．
それを『数学対話』から振り返り，自然数の性質を土台にして，整数論の土台である除法の原理 を証明する．
1.1 整数の除法
自然数とは
1 からはじめて，「1たす」という操作で作られる数の集合
と定義しよう．この集合をN と記す．これを定式化することは『数学対話』「自然数と数学的帰納 法」をみてほしい．
自然数の集合Nは次のような性質をもつ集合になる．
(1) 自然数の部分集合に最小の要素が存在する．
(2) (数学的帰納法の原理)Nの部分集合Aが条件「1∈A，かつx∈Aならx+ 1∈A」を満 たすなら、AはN 自身である．
(3) a < bである任意の自然数に対し，b < naとなる自然数nが存在する．
自然数の集合には，演算として加法が定義され，さらに積が定義される．
ところが，任意のN の要素 xに対してx+e=xとなるe，つまり0はN に存在しない．さ
らにxに対してx+y= 0となるy，つまり−xもまたN には存在しない．これらの要素を構成
し，それら全体の集合を考える．これを整数の集合といいZで表す．集合Z の各要素を「整数」
という．
Z ={· · ·, −3, −2, −1, 0, 1, 2, · · ·}
である．
整数の和・差・積は再びZ に属する，つまり整数である．これを「整数の集合は加法・減法・
乗法の演算で閉じている」という．一方，乗法の逆演算である除法についてZは閉じていない．2 と3に対して2÷3によって得られる数 2
3 は一般にはZの要素でない．
整数の研究の第一歩は，この整数の集合のもう一つの演算である「除法」を見直し，その基本性 質を明らかにすることである．
Zの任意の要素aと任意の正の要素bに対して，次の定理1 が示すように，a
b =q+r
b となる
整数qと，0<=r < bの範囲の整数rがただ一つ存在する．そのときqをaをbで割った商，rを 余りという．これがつまり，割り算がただ一通りにできるということである．いいかえれば，割り 算の可能性と一意性の成立である．
これが「除法の原理」である．整数の多くの事実の根拠がここにある．
この節では自然数の性質に基礎づけて，「除法の原理」を証明しよう．整数の性質は土台としての 自然数の性質から証明される．
定理 1 (除法の原理)
aを任意の整数,bはb >0の整数とする．このとき，
a=qb+r , 0<=r < b となる整数q, rがただ１組，存在する．
証明 整数aと正整数bに対して
qb <=a <(q+ 1)b となる整数qが存在することを示そう．
a <(t+ 1)bを満たす整数tよりなる集合をAとする．これは整数Zの部分集合である．
自然数の性質(3)から|a|< biとなる自然数 iが存在する．ここに|a|はaの絶対値，つまり
|a|= {
a (a >= 0)
−a (a <0) を表す．
−bi < a < biとなるiが存在したので，t <=−biなるtはAに属さない．したがってAは自然数 と有限個の整数の和集合M
M ={ −i, −i+ 1, · · ·, 0} ∪N
の部分集合である．よってこの集合の中に最小の元がある．それをqとする．すなわちa <(q−1+1)b を満たさない．つまりqb <=aが成立する．
そこでr=a−qbとおく．qb <=a <(q+ 1)b より0<=r < bで a=qb+r
である．
つぎに，このようなq, r が二通りあったとする．それを q1, r1 と q2, r2 とする．q1 =q2なら r1=r2である．q1> q2とする．つまり,q1>=q2+ 1 とする．このとき，
a >=q1b >= (q2+ 1)b=q2b+b > q2b+r=a
となり，矛盾である． q1< q2 のときも同様．よってq1=q2 であり，その結果r1 =r2である．
□
qのことをaをbで割った商，rのことを余りという．r= 0であるとき，つまり a=bq (b6= 0)
となる整数qが存在するとき，aはbで割り切れるといい，b|aと表す．このとき，aは bの倍数，
b はaの約数である，という．
整数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 はそれぞれ，自然数，整数，有理数，実 数，複素数の集合を表すものとする．
例 1.1 b= 12とする．
• a= 50：50 = 4·12 + 2．q= 4 = [50
12 ]
．r= 2
• a=−50：−50 = (−5)·12 + 10．q=−5 = [−50
12 ]
．r= 10
• a=−5：−5 = (−1)·12 + 7．q=−1 = [−5
12 ]
．r= 7
1.2 整式の除法
ところでこの定理をよくみると，同様なことが整式でも成り立つことに気づく．
xの整式は，つぎの基本性質をもつ．ここでdegf(x)は整式f(x)の次数を表す．
定理 2 (整式の除法の原理)
整式f(x), g(x)(degg(x)>= 1)とする．このとき，
f(x) =g(x)·q(x) +r(x), degr(x)<degg(x) となる整式q(x), r(x)がただ１組，存在する．
証明 degf(x)<degg(x)ならばq(x) = 0, r(x) =f(x)でよい．
degf(x)>= degg(x)のとき, degf(x) =n, degg(x) =m とする．f(x)と g(x)の n, m次の 項をそれぞれ a0xn, bxmとする．
f1(x) =f(x)−a0
b xn−mg(x)
と定めれば, degf1(x)<degf(x) である．f1(x)と g(x)について同様の操作を繰り返す．fk(x) の次数がnk で最高次数の係数が ak とすれば
fk+1(x) =fk(x)−ak
b xnk−mg(x) l回の操作の後, degfl(x)<degg(x)となったとき，
fl(x) =r(x), q(x) =
l−1
∑
k=0
ak b xnk−m とする．この f1(x)に対し
f(x) = g(x)a0
b xn−m+f1(x)
= g(x)a0
b xn−m+g(x)a1
b xn1−m+f2(x)
· · ·
= g(x)q(x) +fl(x) となるので，定理の等式を満たす．
これが１組しかないことを示す．2組あったとする．
f(x) = g(x)·q1(x) +r1(x)
= g(x)·q2(x) +r2(x) すると，
g(x)· {q1(x)−q2(x)}=r2(x)−r1(x) (1) となる．ここでもしq1(x)−q2(x)6= 0ならdeg(r2(x)−r1(x))>= degg(x)である．
ところが一方，degr1(x) < degg(x), degr2(x) < degg(x) だから，deg(r2(x)−r1(x)) <
degg(x)．これは矛盾．
ゆえに等式(1)が成立するのは，q1(x) = q2(x)のときのみである．このとき,r1(x) = r2(x)
となる． □
このように除法の原理が成立すると，因数分解の一意性がなり立ち，約数，倍数，公約数，公倍 数などに関する以下の議論の多くが成り立つ．
1.3 演習問題
1.3.1 関連入試問題
入試問題 1 (解答1)［96大教大］
(1) F(x) = 2x3+ 5x2−3x+ 7, G(x) =x−3 とする．このとき，F(x) =G(x)Q(x) +rを満 たすxの整式Q(x)と実数rを求めよ．
(2) F(x)をxの１次以上の整式， G(x) =x−a，ただしaは実数とする．このとき，
(i) F(x) =G(x)Q1(x) +F1(x)を満たすxの整式Q1(x), F1(x), ただし F1(x)の次数は F(x)の次数より小さい，が存在することを示せ．
(ii) F(x) =G(x)Q(x) +rを満たすxの整式 Q(x)と実数rが存在することをF(x)の次 数に関する数学的帰納法を使って証明せよ．
(3) F(x)をxの整式とする．実数aに対して， F(a) = 0となるならF(x) = (x−a)Q(x)を 満たすxの整式 Q(x)が存在することを示せ．
(4) F(x)をxのn次式とする．このとき，方程式F(x) = 0の相異なる実数解はn個以下であ ることを示せ．
2 最大公約数と最小公倍数
最大公約数と最小公倍数，小学校や中学校で習ったままである．そのときにはしっかりとした証 明もなかった．24，180，42 の最大公約数を求めるのに
2 ) 24 180 42 3 ) 12 90 21 4 30 7
∴ 24，180，42の最大公約数は2×3 = 6
と習った．しかしこのときに，もし素因数が37等ととか大きかったら簡単には見つけられない，
と思った人はいないだろうか．いつでも最大公約数を見つけることはできるのだろうか．
実は常に最大公約数を求める方法がある．それを学ぶことがこの節の内容である．
2.1 最大公約数と最小公倍数
二つ以上の整数a, b, c, · · ·に共通な倍数をそれらの整数の公倍数という．0は常に公倍数であ る．それを除けば公倍数の絶対値はa, b, c, · · · のいずれの絶対値よりも小さくはないので，公 倍数の中に正で最小のものがある．それを最小公倍数(least common multiple略してL.C.M.)と いう．
二つ以上の整数a, b, c, · · ·に共通な約数をそれらの整数の公約数という．1は常に公約数であ る．公約数の絶対値はa, b, c, · · ·のいずれの絶対値よりも大きくはないので，公約数の中に最大 のものがある．それを最大公約数(greatest common measure略してG.C.M.)という．
定理 3
(1) 二つ以上の整数の公倍数は，最小公倍数の倍数である．
(2) 二つ以上の整数の公約数は，最大公約数の約数である．
(3) a, bの最小公倍数をl ，最大公約数をdとすればab=dl ．
(4) a, bが互いに素で，他の整数 cと bとの積 bcがaで割りきれるなら，実は cが aで割り きれる．
証明
(1) a, b, c, · · · の最小公倍数をlとし,mを任意の公倍数とする．mをl で割った商をq，余 りをrとすると
m=ql+r, 0<=r < l
となる．l もmも aの倍数であるからl=al0, m=am0 とおくと r=m−ql=a(m0−ql0)
より,rは aの倍数である．同様にb, c, · · ·の倍数でもあり，r はa, b, c, · · · の公倍数と なる．ところがl は正で最小の公倍数であったから，もしr が0でないとすると, l より小 さい正の公倍数があることになり, lの最小性に反する．
∴ r= 0 つまりmはl の倍数である．
(2) a, b, c, · · ·の最大公約数をdとし,mを任意の公約数とする．l をdとmの最小公倍数と する．aは mの倍数であり，dの倍数である．つまりmとdの公倍数であるから(1)より aはlの倍数である．同様にb, c, · · ·も lの倍数である．つまりl はa, b, c, · · · の公約数 である．dが最大の公約数なので，
l <=d 一方,lはdとm の最小公倍数なのでd <=l
∴ l=d
dとmの最小公倍数l がdに一致した．dはm の倍数，つまり任意の公約数m は最大公 約数dの約数である．
(3) lは a, bの最小公倍数であるから適当な整数a0とb0を用いて，
l=ab0=ba0
とおける．abはa, bの公倍数だから(1)からabは lの倍数である．
ab=ml とする．よって
ab=ml=ma0b, ab=ml=mab0
∴ a=ma0, b=mb0
つまりmはa, bの公約数である．(2)より最大公約数dの約数なので，d=meとおける．
一方dは a, bの最大公約数なのでa=da00, b=db00 とおける．よって a=da00=mea00, b=db00=meb00
一方，a=ma0, b=mb0であるからma0=mea00，mb0 =meb00が成り立つ．
∴ a0=ea00, b0 =eb00 その結果，
l=ab0=aeb00, l=a0b=ea00b
∴ l
e =ab00=a00b ところがこれは l
e がa, b の公倍数であることを示している．l が最小の公倍数なのでその 最小性によりe= 1．
∴ m=d つまり ab=dl
(4) a, bの最大公約数が 1 なのでa, b の最小公倍数は abである．仮定からbcは aの倍数で あり，したがってaとb の公倍数である．よってbcはabの倍数であり，
bc ab = c
a が整数
つまりcはaの倍数である． □
この定理の証明において，前節の「除法の原理」が基本定理として用いられてることがわかる．
日頃当然のように論証で使っていることが，「除法の原理」を基礎に厳密に示される．
整数a, b, c, · · · の最大公約数を，座標と混同する恐れのないときは(a, b, c, · · ·)と書く．
整数a, b, c, · · · の最大公約数が1であることを簡単に「公約数をもたない」という．この場
合，(a, b, c, · · ·) = 1．特に二つの整数a, bが公約数をもたないとき，つまり(a, b) = 1のとき，
a, bは互いに素であるという．
2.2 ユークリッドの互除法
ここで，最大公約数を求める一般的な方法であるユークリッドの互除法をまとめよう．
ユークリッド
ユークリッドは紀元前300年ごろのヘレニズム時代の数学者で，『(幾何学)原論』の著者である．
アテナイで学びプトレマイオス1世治下のアレクサンドリアで教えた．『原論』はラテン語圏・ア ラビア語圏にもたらされ，その後各地で二千数百年にわたって幾何学，いや数学そのものの基本と なる書物であった．この書は13巻から成り，1〜6巻は平面幾何，7〜9巻は数論，10巻は無理量，
11〜13巻は立体幾何を取り扱っている．
図形以外では，最大公約数を求める方法であるユークリッドの互除法，素数の個数は無限である 証明，などが書かれている．
定義から始まり，公準（要請）・公理・命題とその作図・証明・結論という形式で書かれている．
このような形式で数学を論述することが，長く模範となった．
定理 4 (ユークリッドの互除法)
(1) a > b >0を整数とし,aを bで割った余りをrとする．このとき (a, b) = (r, b)
が成り立つ．
(2) 数列{rn}を次のように定める．
r1=a, r2=b n >= 2のとき
rn>0なら，rn+1=rn−1をrnで割った余り rn= 0なら，rn+1= 0
このときある番号N で rN 6= 0で rN+1= 0となるものがあり，このとき rN = (a, b)
が成り立つ．
証明
(1) (a, b) =d1とするとa=a0d1, b=b0d1とおける.
r=a0d1−b0d1q=d1(a0−b0q)
これよりr も d1 で割れる. よって,d1 は bとr の公約数なので, d1 <= (b, r) = d2．次に (b, r) =d2とすると,b=b0d2, r=r0d2とおける.
a=b0d2q+r0d2=d2(b0q+r0) より同様にd2<= (a, b) =d1．よってd1=d2 ，つまり
(a, b) = (b, r) (2) 除法の原理からrk>0なら
r1=a > r2=b > r3>· · ·> rk > rk+1>=rk+2>=· · ·>= 0 自然数の単調減少列なのである番号N で
rN >0かつrN+1= 0 となる．このときrN−1はrN の倍数になる．よって(1)より
(a, b) = (b, r3) =· · ·= (rN−1, rN) =rN □
これが最大公約数を求める一般的な方法でユークリッドの互除法といわれる．このように「必 ずできる一般的方法」をアルゴリズムという．ユークリッドの互除法はアルゴリズムの基本例で ある．
三つ以上の整数a, b, c, · · ·の最大公約数もこれを応用して求めることができる．
aがa, b, c, · · ·のなかの最小の数とする．aで他の数を割った余りをb0, c0, · · · とする．する と上の定理と同様に
(a, b, c, · · ·) = (a, b0, c0, · · ·)
この操作を繰り返すと余りのなかに0が現れる．それを取り除いてさらに同様の操作を繰り返す．
ついにはただひとつの数が残る．それがa, b, c, · · · の最大公約数である．
例 2.1 (6188,4709)を求めよう．
順次割り算を行うことにより次の系列を得る．
(6188,4709) = (4709,1479)
= (1479,272)
= (272,119)
= (119,34)
= (34,17) = 17 例 2.2
(629,391,255) = (119,136,255) = (119,17,17) = 17
