結城浩
2005年4月6日
長男「ねえ、問題出して！」
結城「2つの整数aとbがあるとする。簡単のために両方とも1以上だとしよう」
長男「ふんふん」
結城「aとbの最大公約数が1のとき、aとbの最小公倍数はa×bになる。ホントかウソか？」
長男「ええっ、ええ？」
結城「もう一回言おうか？」
長男「いや、いいや。…ええと…ホント！」
結城「はい、正解です！」
長男「だって両方とも素数のときでしょ」
結城「がく。違うよ」
長男「えっ、そうかなあ」
結城「素数同士でなくても最大公約数が1になることがあるよ。たとえば…」
長男「2と3とか」
結城「それじゃ、両方素数じゃん」
長男「あそっか。…4と5とか？」
結城「そうそう」
長男「わかった！ 差が1ならいいんだ！」
結城「がく。違うって。だって4と9もそうでしょう」
長男「そうか。そうだね。4は2×2, 9は3×3か」
結城「そうそう。最大公約数が1になるのは、aとbの素因数に共通部分がなければいい。4の素因数は2で、9の素因数は3。両方には共通部分がない。もちろん、aとbの両方が素数でもいいけれどね。共通な素因数がないことを『互いに素』っていう」
長男「ふんふん」
結城「2×2×5と7×11も互いに素だ。共通の素因数がないからね」
長男「2×2×5は20で、7×11は77だね。20と77は互いに素なんだ」
結城「そう。素数は誰に対しても「互いに素」だ。「互いに素」っていうのは「相手にとって素数」という役割を持っているということだね」
余談：
素因数は、ベクトル空間の直交基底に似ている。 素因数を掛け合わせて整数を作るのは、直交基底が空間を張るのに似ている。 「整数aとbが互いに素」を「a⊥b」と表記することがあるのも、むべなるかな。
素因数は、元素に似ている。 整数を素因数に分解するのは、化合物を元素に分解するのに似ている。 化学で「2つの化合物a, bに共通元素がない」ことを表す記号はあるんだろうか。 「a⊥b」で表したりして。
先日の日記 「互いに素」という概念 の中に書いた「素因数は、ベクトル空間の直交基底に似ている」に対して、 大学院生の森田さんという方から、 なんだかすごいコメントをもらっちゃいました。
森田さん：
はじめまして。いつも楽しく読ませていただいております。
実際、0を除く有理数は(有理数としての)乗算を(ベクトルとしての)和、 整数乗をスカラー倍とみなせば素数を基底とした無限次元、整数係数のベクトル空間を成しますね。
結城：
ええと、ええと、うーんと…。ははあ、なるほど、なるほど。以下のような感じでしょうかね。
素数を基底とした無限次元のベクトルの要素は、たとえばこんな姿をしている。
(0, 2, 0, 1, -1, 0, 0, ...)
これは(-1)^0 * 2^{2} * 3^{0} * 5^{1} * 7^{ -1 } * 11^{0} * 13^{0} * ...に対応(指数のところを抜き出したのがベクトル)。 これは有理数 20/7 に対応している(ベクトルの一番最初の成分は符号ビット(指数は0または1)とする)。
2は2^nの軸の基底。3は3^mの軸の基底, ...とする。 12という有理数は、2と3の基底を使って、(-1)^{0} * 2^{2} * 3^{1}と一意にあらわせる。 だから、(0, 2, 1, 0, 0, 0, ...)というベクトルと対応。-1/2 という有理数は、(-1)^{1} * 2^{-1}だから、(1, -1, 0, 0, 0, 0, ...)というベクトルと対応。
零ベクトル(0, 0, 0, 0, ...)に対応する有理数は1。
いま、p/qという有理数を考えよう。 pを素因数分解したベクトルを (p_{-1}, p_2, p_3, p_5, ...) とし、 qを素因数分解したベクトルを (q_{-1}, q_2, q_3, q_5, ...) とすると、 p/qは (p_{-1} - q_{-1}, p_2 - q_2, p_3 - q_3, p_5 - q_5, ...) に対応する(ただし符号ビットのところは2の剰余系で計算)。
有理数p/q(ただしpもqも非0とする)に対応するベクトルの逆ベクトルは、q/pに対応するベクトルになる。
こんな感じでしょうか。
そうか、こういうベクトル空間を考えると、 素因数分解というのは「ひとつのベクトルがそれぞれの軸に落とした影を見つける」という計算なのですね。
そして、2つの整数の最大公約数が1（互いに素）というのは、 ベクトルaとベクトルbの成分で非ゼロの部分に重なりがない（直交する）ということなのか。 で、a⊥bだと。
ところで「互いに素」を「a⊥b」と表記するという話題は、Knuth先生たちの 『コンピュータの数学』 に出てきます。 「互いに素」を簡潔に表す表記法がないので「世界中の数学者たちよ、もう待てない」というふうに書かれていますね （いま記憶で書いているので不正確かも。あとで確かめます→おおむね合ってました。邦訳p.115）。
以下はおまけ。
追記(2005-04-11)
『コンピュータの数学』のp.107には、 ちょうどこの「素数を基底とした無限次元のベクトル空間」に似た「素数指数表現」という話題が書かれていました。
読者さんからコメントをいただいたので、さらに追記(2005-04-12)
読者さんからコメント
すごく瑣末なんですが，このケースでは確かに素数を基底とした自由加群ですが， 係数環が体ではない場合，数学ではベクトル空間という言い方をしません． ＃本当に瑣末ですね．ちょっと気になったので．
ところで，Hamel基底をご存知でしょうか？ 実数体は有理数体上無限次元のベクトル空間なのですが，その基底にはHamel基底という名前がついています．もちろん具体的な構成はできないのですが．
地味にプログラミングの勉強。 自分の理解が正しいかどうか、実際にプログラムを書いて確かめる。 これができるから、プログラミングは独学しやすいんですよね。
* * *
ところで、昨晩Knuth先生の『コンピュータの数学』を読んでいて、 改めて「互いに素」という概念の重要性を確認。 たとえば、小学校で分数の「約分」ってしますよね。 あれは分子と分母を「互いに素」にするための操作なわけです。 で、そのためには分子と分母の公約数で繰り返し割る。 最大公約数がわかっているならそれで1回割ればよい。 つまり…
(a/gcd(a,b)) ⊥ (b/gcd(a,b))
ということですね。ここで、gcd(a,b)はaとbの最大公約数。a/gcd(a,b)はaを「aとbの最大公約数」で割ったもの。 上の式は「aとbを最大公約数で割った数は、互いに素」という意味。
話は飛びますが。
AB=0
のとき、AまたはBは0ですね(両方0でもよい)。いま、AとBをそれぞれ(x-a), (x-b)としてみます。すると、
(x-a)(x-b)=0
このとき、x-a=0、または、x-b=0になります。要するに、xはaまたはbです。 上の式を展開すると、
x^2 - (a+b)x + ab = 0
という二次方程式になる。つまり、もし
x^2 + ●x + ■ = 0
という形の二次方程式を見かけたら、
● = -(a+b)
■ = ab
という形になるようなaとbを見つければ、 それが上の二次方程式の解になるのですね。 まあ、いわゆる「解と係数の関係」です。
何を当たり前のことを書いているかというと、 二次方程式を解くというのは、 x^2 + ●x + ■ = 0 のような形をしているものを、もっと取り扱いやすい (x-a)(x-b)=0 という形に変形することなのだなあ、と改めて思ったからなのです(で、そのための方策のひとつが解と係数の関係だと)。 両方は方程式としては等価なのに、取り扱いやすさ(?)という点では大きく違う。 これもまた「構造を見抜く」ことのバリエーションでしょうか。
この形は、素因数分解と似ていますよね。 たとえば、1441149131980013567という大きな数があるとする。 この数の構造を見抜くことができれば、 524287×2748779069441 という形に分解できる。
多項式の因数分解が、整数の素因数分解に似ているということからさらに発想を広げる。 多項式にとっての「素数」は何だろう？ って思いますよね。つまり、それ以上「因数分解」できない多項式。 それには既約多項式という名前がついている。
素因数分解は難しい計算。 一般に構造を見抜くことというのは、難しい情報処理なのかもしれないなあと、ぼんやり思う。 そこからの想像なんだけれど、一般の多項式を既約多項式に分解するって、 ものすごく難しい計算ではないだろうか。どうだろう。
さて、と。 x^2 - 1 は(x+1)(x-1)のように因数分解できる。 でも、x^2 + 1は因数分解できない。 x+1, x-1, x^2+1は既約多項式。
ん？でも、虚数iを持ってくればx^2+1だって因数分解できるねえ。 x^2+1 = (x+i)(x-i) だものね。ということは、実数の範囲で、とか、複素数の範囲で、のように 範囲を定めないとまずいんでしょうね。
「範囲を定めないとまずい」というのを整数の素因数分解の話に逆輸入すると… 3は素数だけれど、3が素数なのは整数の範囲で、ということですね。 たとえば、実数に話を広げちゃったら、√3 × √3という積の形に書けちゃいますもんね。 有理数の範囲でも1.5×2とかね。
ふむふむ。 多項式の世界における既約多項式を基底に持つベクトル空間も考えられそうですね。 ひゃあ。
（ちなみに、最近書いている「基底」の話題は、 『プログラマの数学』と直接の関係はありません）