整数のDNA - Biglobe

数のイマージュ、形のパサージュ
―
数と戯れ、図形と遊ぶ
―
伊那
闊歩
14．整数のＤＮＡ
遺伝子研究の最先端の成果のひとつとして、数年前から流布している話
に、人とチンパンジーの遺伝子配列を比べてみると、98.5 パーセントは同じで、
違いはほんの 1.5 パーセントにすぎないというのがある。しかし、最近の研究
によれば、人とチンパンジーのゲノムには、お互いに大きな違いがあるともい
う。おそらく、コンピュータ処理だけに頼っていたのでは何も分からないとい
うことではないか。そんな単純なものではないらしい。未知の部分にこそ、も
のの本質がひそんでいるにちがいない。
数学にも DNA 研究に似たような事情があると思われる。生化学研究者か
らは、見かけだけのことで、何の関係もないと反発されるであろうが、数を生
物と見做して観察するのも面白いと思う。次の２つの数を見ていただきたい：
1702 、
2553
これら２数はお互いに見た目はまるで違うが、それぞれ約数の積に分解して書
けば
1702 = 2 ×23 ×37
2553 = 3 ×23 ×37
となって、これら２数の約数の配列（DNA の塩基配列に対応？）は最初の約数
が、2 か 3 かの（ほんの少しの）違いだけなのだ。
生物の研究において DNA の塩基配列を知ることが現代では必須である
ように（見えるが）、整数の性質を知る上で、その約数（の配列）を調べること
は同じく重要である。ここでは最後まで負の整数は考えないことにする。
整数 1702 は、8 個の約数（1, 2, 23, 37, 46, 74, 851, 1702 ）をもってい
る。1 と 1702（自分自身）も約数であるが、特に 1 と自分自身を除いた約数
を真の約数という。1702 の真の約数は、2, 23, 37, 46, 74, 851 である。真の約
数を持たない整数を素数という。1 は素数ではないことにするが、それにはま
た別の理由があるのだ（ 2 は偶数であるが素数である。偶数なのに素数という
ことにすこし違和感を持たれるかもしれない）。2, 3, 23, 37 などは素数である。
真の約数をもつ整数を合成数という。1702 は（2553 も）合成数である。
整数 0 は、0 以外の整数で割りきれて（ 0 になるから）無限に多くの
約数を持っていると考えられる。一方、1 はたったひとつの約数しかもってい
ない。以上、整数を約数によって分類してまとめると次のようになる：
（１）たったひとつの約数をもつもの
（２）無限に多くの約数をもつもの
（３）約数が 1 と自分自身だけのもの、
1
0
つまり真の約数がないもの
（４）真の約数をもつもの
素数
合成数
合成数は、素数の積に分解することができる。分解の結果は、順序はど
うでもいいこととして、ただひと通りに書くことができる。それでは、素数は
いくらでも存在するのであろうか？とてつもなく大きな素数は存在するのか？
大きな数には約数があって、いずれすべて合成数になるのではなかろうか？と
いうのは素朴な疑問であるが、次の定理は、ユークリッドの証明とともに昔か
ら有名である：
素数は無限にたくさん存在する。
以下に、ユークリッドの『原論』にある巧妙な証明を簡単に記しておこう：
素数の数は有限であるとして、それらを p, q, ・・・r としよう。そこで、
a = p×q×・・・×r + 1
とする。この整数 a が
（１）もし素数ならば、a は明らかにすべての素数よりも大きい。
（２）もし合成数ならば、a は、p, q, ・・・r
どの素数によっても割り切
れないから、もっと大きな素数が存在して、それによって割り切れるこ
とを意味する。
つまり、素数の数は有限にとどまらず、無数にあることが証明された。
2 つ以上の整数
a, b, c, ・・・に共通な倍数をそれらの整数の公倍数
という。上記の整数 1702 、2553 の公倍数は、5106,
4345206 、など無
数にあるが、そのうち最も小さいものを最少公倍数といい、記号 L であらわす
ことにする。1702 、2553
の L = 5106 である。2 つ以上の整数
a, b,
c, ・・・に共通な約数を公約数といい、そのうち最大のものを最大公約数と
いう。3 整数 a, b, c の最大公約数を G( a, b, c ) と書く。また、最大公約数
を単に記号 G であらわすこともある。
G( 1702 、2553 ) = 851 = G
次の問題は、２整数の最大公約数を求めることであるが、ユークリッドの
考案による「ユークリッドの互徐法」と呼ばれるうまい方法が昔から知られて
いる。例として、G( 1702 、2553 ) をユークリッドの互徐法を用いて求めて
みよう。まず、2553 を 1702 で割って、次のように書く：
2553 = 1 × 1702 + 851
ここで、徐数 1702 をあまり 851 でわる：
1702 = 2 × 851 + 0
このような計算をあまりが 0 になるまでつづけ、そこで計算をストップする。
このとき、最後の式の徐数、つまり、ひとつ前の式の余りが最大公約数になる。
答は、G( 1702 、2553 ) = 851 となる。もうひとつ、少し大きな数 11804537 と
206863 でやってみよう：
11804537 = 57 × 206863 + 13346
206863 = 15 × 13346 + 6673
13346 =
2 × 6673 + 0
となって、
G( 11804537 ,
206863 ) =
6673
であることがわかる。
２整数 a, b ( a は b よりも大きいとする ) の最大公約数 G が、
ユークリッドの互徐法によって正しく計算されることは、上記の計算例からも
明らかなように、余りの中に G が受け継がれるためである。
a
= s × b
+ t
と書いてみると G は a 、b の約数であると同時に t
わかる。つまり、次の式がなりたつ。
の約数でもあることが
G( a 、b )
= G( b 、t )
t は余りであるから、当然 b よりも小さな整数であり、つぎつぎに計算すべ
き数は小さくなってゆき、こうして互徐法の計算をつづけていけば、ついには
求める G にたどりつくのである。
最後に重要な注意をひとつ書いておかねばならない。上のユークリッド
の互徐法を使った計算において、
a
= 11804537,
b
=
206863
として余りを書き下していけば、
13346
= a
－ 57b
6673
= b
－
15×（a －
57b）= －15 a + 58b
となる。つまり、最大公約数は、 a と b の一次式として必ず書けることを
ガッテンしておいていただきたい。さらに、一次方程式：
11804537
X +
206863
Y
= 6673
と
－15 a + 58b
＝
6673
とを比べてみる。なにをしているのか、いぶかしく思われるかもしれないが、
驚くべきことがここに起こっているのだ。つまり、この複雑な一次方程式を満
たす整数解のひと組みがいとも簡単に求められているではないか。答えは
X = －15,
Y = 58
なのだ。
参考文献
（１）高木貞治「初等整数論講義」（共立出版）
（２）Ｊ．Ｈ．シルヴァーマン「はじめての数論」（ピアソン）

Download Report