1. No category

初等数論 I
SHINOBU YOKOYAMA
概要. 本日は忙しい中集まって頂き感謝に尽きる.
講習という名目ではあるものの, 時間の制限により講義という形式
をとらせてもらう. それでも始終リラックスして聞いてほしい. 人
数を考えればほぼ対話形式になるだろうから, 質問は自由に, そして
積極的にしてほしい. ノートはとらないですむような内容を心がけ
るが, それも自由にしてくれればいい. 計算ミスなど気づく点があれ
ば指摘してくれるとありがたい.
この文の内容は参考書というより教科書的に書いた部分が大きい.
とはいえ冗長でつまらない内容は避けるようにしたし, 厳密である
と同時にそのまま生徒に教えて理解できる内容を心がけてて書いた.
「こう言うと理解されやすい」というエッセンスもできるだけ盛り込
んだつもりである.
初等数論を高校等で履修していない人に, ある程度習得して帰っ
てもらうという主旨で進むが, もちろん, 高校生に教えることを想定
したとき, 各自演習が必要なことは自身で判断して欲しい. 初等数
論という名称は一般的なものだが, 簡単という意味では決してない.
数学において初等がその意味で使われてるのは, 少なくとも僕は聞
いたことがない (e.g. 初等変形). 割り算のない数の性質は環論とい
う分野で研究され, 最近では幾何学と代数学の橋渡しになっている.
応用では暗号理論や保険数学が華であろう. 専門でない人にも, 興味
を持って取り組んで頂けることを切に願う.
1
2
SHINOBU YOKOYAMA
1. 用語
用語には共通の認識が要るため, ここで列挙する.
e.g.:=exempli gratia:
例えば. 例を挙げるときにつかう.
i.e.:=id est:
すなわち. つまるところ.
d:=divider:
記号で断りなく d と言えば約数を表す.
q:=quotient:
記号で断りなく q と言えば商を表す (e.g. 31 = 4q + 3).
r:=residue:
記号で断りなく r と言えば余りを表す (e.g. 31 = 4 · 7 + r).
lcm:=least common multiple:
最小公倍数 (e.g. lcm(2, 3) = 6).
gcd:=greatest common divider:
最大公約数 (e.g. gcd(32, 24) = 8).
a|b:
整数 a が整数 b を割り切る.
初等数論 I
3
定理 1. (剰余定理) 整数 x,y に対し
y = xq + r
(|x| > |r|)
を満たす整数 q, r が一意的に存在する (x を除数, q を商, r を剰余とい
う).
命題 1. 整数 x, y (y > x) に対し, y を x で割ったときの余りを r とす
る. このとき x と y の最大公約数は, x と r の最大公約数に等しい.
y = xq + r と表したときに gcd(x, y) = d, gcd(x, r) = f とおくと
d|r, f |y
であって d は (x,r) の約数とみなせる. f はそのようなものの最大の
数であるから d ≤ f . 同様に f を (x,y) の約数とみなすとき, d がそのよ
うなものの最大の数であるから f ≤ d. 故に d = f
命題 2. (ユークリッドの互除法) 与えられた整数 x, y の最大公約数は
有限回の代数演算で求まる.
有限回の代数演算とは有限回の加減乗除と根号をとる操作のことを
言う. 与えられた整数 x, y (y¿x) に対し定理 1 を繰り返し適用すれば,
y
x
r
r1
= xq + r
= rq1 + r1
= r1 q1 + r2
= r2 q1 + r3
···
rn−1 = rn qn−1
のようにできる (除数を余りで割る操作を繰り返すと, 最終的に余り
が 0 となるようにできる). そこで命題 1 を使って,
gcd(y, x) = gcd(x, r)
gcd(x, r) = gcd(r, r1 )
gcd(r, r1 ) = gcd(r1 , r2 )
=
=
···
= gcd(rn−2 , rn−1 ) = gcd(rn−1 , rn )
となる. 結局たかだか n 回の代数演算で最大公約数 gcd(x, y) = rn が
求まることが分かる
(S. Yokoyama) Hyogo 561-2113, Japan
E-mail address: [email protected]