その四 素因数分解と約数の話

 さて,今度は実際に数字を割って素因数分解をしてみよう.これまでの倍数判定や初歩的展開公式を利用して暗算でも三桁程度の数の素因数分解が可能だ.実際,目に入った車のナンバーを暗算で素因数分解して頭を試してるときもあるし…

 分解の第一歩は「その数が素数か否か」を見分ける事.200位までの数なら暗算ですぐに素数かどうか見分ける方法がある.それはその三の倍数判定を使うのだ.

 たとえば163という数を例に取ってみよう.この数が何かの数Aで割り切れて,
163=A×B
と書けたとしよう(ただしAとBは1でない自然数).すると,A,Bの少なくとも一方は13よりも小さいはずだ(もし両方が13よりも大ならA×Bは13×13=169より大きくなって不合理だ) .
だから,11以下の素数2,3,5,7,11の五つの倍数かどうか判定しさえすれば良いのだ.
では163について判定をやってみることにしよう.
2の倍数か?…一の位が3なので不可.
3の倍数か?…1+6+3=10なので不可.
5の倍数か?…一の位が3なので不可.
7の倍数か?…16-3×2=10なので不可.
11の倍数か?…1-6+3=-2なので不可.

したがって11以下の素因数はなく,163は素数であるといえる.

 もう一つ,今度はちょっと大きな1643を例にとってみよう.今度はちょっと違う方法で約数を探してみよう.1643が約数を持てば
1643=A×B
と書ける.A,Bの少なくとも一方は40より小さいことの確認はさっきと同じだが,先だっての倍数判定を使っても15までの倍数に引っかかってくれない.ということは,A,Bという約数が存在するならばきっとかなり近い素数同士の積になってるに違いない
そこでこんな方法を思いついた.
A,Bはともに奇数だ.ということは二つの自然数M,Nが存在して,A=M+N,B=M-Nを満たせると言っていい.すると
1643=M2-N2
と書ける.ここでM≧41だ.ではM=41から順に調べていくか.
M=41のときN2=412-1643=1681-1643=38,Nが整数にならない.
M=42のときN2=422-1643=1764-1643=121,N=11が見つかった.

したがってA=42+11=53,B=42-11=31という約数が見つかった.1643=31×53と素因数分解ができたのだ.


 具体的に素因数分解するには約数を見つけたらそれで割るということを続けて,すべての因数が素数にまで分解できたら終わりである. 中学一年の時の宿題にこんなのがあった.
123123の約数をみつけてきなさい
私がそのとき瞬時に見つけた約数は1,3,7,11,13,41,123,143,1001くらいだった.なぜこのときすべてを調べなかったのか今でも謎である.というか「しまった!」と後悔してさえいる.

 では素因数分解してみることにしよう.まず見つかるのは
123123=123×1001
だ.さらに,123と1001のそれぞれが分解できて
123=3×41
1001=7×11×13

となり,結局
123123=3×7×11×13×41
と素因数分解できた.
 それでは123123がどんな約数を持ってるか,ということになるとちと厄介かもしれない.
123123の約数,ということは123123を割り切ることができる数である.ということは123123の素因数の一部を抜き出してその積を作りさえすれば良い.
0個…1
1個…3,7,11,13,41
2個…3×7=21,3×11=33,3×13=39,3×41=123,7×11=77,7×13=91,7×41=287,11×13=143,11×41=451,13×41=533
3個…3×7×11=231,3×7×13=273,3×7×41=861,3×11×13=429,3×11×41=1353,3×13×41=1599,7×11×13=1001,7×11×41=3157,7×13×41=3731,11×13×41=5863
4個…123123÷3=41041,123123÷7=17589,123123÷11=11193,123123÷13=9471,123123÷41=3003
5個…123123

以上32個.

 約数の個数については高校のときに「個数の処理」の単元で扱うが,これについても中学一年の時に気付かされていた.
自然数Nが,
N=p1a*p2b*p3c*…*pnk
と素因数分解できたとする(p1,p2,…,pnは素数,a,b,…,kは自然数)と,Nの約数N'は,
N'=p1a'*p2b'*p3c'*…*pnk'
と素因数分解されるはずである.ただし0≦a'≦a,0≦b'≦b,…,0≦k'≦k.逆にこの形の数はNの約数たり得るので,a'には0からaまでのa+1個の可能性が,b'には0からbまでのb+1個の可能性が…,k'には0からkまでのk+1個の可能性があり,結果として約数の個数は
(a+1)(b+1)(c+1)…(k+1)
個であるといえる.実際123123の約数の個数は25=32個だった.
  ちなみに約数の総和は等比数列の和の公式を利用して
{(p1a+1-1)(p2b+1-1)(p3c+1-1)…(pnk+1-1)}/{(p1-1)(p2-1)(p3-1)…(pn-1)}
で与えられる.123123の約数の総和は
(9-1)(49-1)(121-1)(169-1)(1681-1)/{(3-1)(7-1)(11-1)(13-1)(41-1)}=8*48*120*168*1680/(2*6*10*12*40)=225792
となる.


 約数の話に触れたのなら複数の数の公約数についても触れておこう.まずは言葉の定義から.
自然数Cが自然数A,Bの公倍数であるとは,CがAの倍数であり,かつBの倍数でもあるということ.
公倍数のうち最小のものを最小公倍数と呼ぶ.
自然数Dが自然数A,Bの公約数であるとは,DがAの約数であり,かつBの約数でもあるということ.
公約数のうち最大のものを最大公約数と呼ぶ.
自然数A,Bが互いに素であるとは,AとBの公約数が1のみであること.

したがってCがA,Bの公倍数なら
C=pA
C=qB

なる自然数p,qがあり,p,qが互いに素なら公倍数CはA,Bの最小公倍数である(ア).
またDがA,Bの公約数なら
A=rD
B=sD

なる自然数r,sがあり,r,sが互いに素ならば公約数DはA,Bの最大公約数である(イ).

(ア)(イ)を証明しよう.
 (ア)の対偶は「公倍数CがA,Bの最小公倍数でなければp,qは1でない公約数を持つ」である.
A,Bの最小公倍数をMとすると,公倍数の性質から
M=tA
M=uB
と書ける(ウ).またCは最小公倍数でない公倍数なので1でない自然数kを用いて
C=kM
と書ける(エ).(ウ)(エ)より
C=kM=ktA=kuB
とかけて,(ア)で
p=kt
q=ku
と書くことができる.k,t,u,p,qはすべて自然数なのでp,qは1でない公約数kを持つことが分かった.
 (イ)の対偶は「公約数DがA,Bの最大公約数でなければr,sは1でない公約数を持つ」である.
A,Bの最大公約数をNとすると公約数の性質から
A=tN
B=uN
と書ける(オ).また,Dは最小公約数でない公約数なので1でない自然数kを用いて
N=kD
と書ける(カ).(オ)(カ)より
A=tkD
B=ukD
と書けて,(イ)で
r=tk
s=uk
と書くことができる,k,t,u,r,sはすべて自然数なのでr,sは1でない公約数kを持つことが分かった.

ほとんど同じ書き方やん.

 (ア)(イ)を使って次のように考えてみる.
E=rsDとすると
E=s*rD=sA
E=r*sD=rB

と書けるのでEはA,Bの公倍数だ.ここでr,sは互いに素だったので(ア)よりEはA,Bの最小公倍数Cに他ならない.したがって
s=p
r=q

が言えて
CD=rsD2=rD*sD=AB
が言える.二数の積がそれらの最小公倍数,最大公約数の積と一致するのである.


 さて次は簡単な最大公約数の見つけ方である.二つの数があったなら両方素因数分解して共通したものをすべて拾いあげてその積を作ればそれが最大公約数ではあるが二つの数が大きくなるとこの方法は困難である.
たとえば229970と372099の最大公約数を見つけてみよう.
とりあえずは愚直に素因数分解から.
229970=2*5*13*29*61
372099=3*13*29*329

となって公約数は共通素因数の積
13*29=377
となる.
  上の式ではさらっと書いてしまったけどいちいち素因数分解してたのではもっと大きな数なんかではまるで埒が空かない.こんなときに便利なのがユークリッドの互除法と呼ばれるアルゴリズム.
それは
AとBの最大公約数がDだとするとBとA-Bの最大公約数もDだ(キ)
というものだ.
 では229970と372099の最大公約数をユークリッドの互除法を使って計算してみよう.
372099-229970=142129
229970-142129=87841
142129-87841=54288
87841-54288=33553
54288-33553=20735
33553-20735=12818
20735-12818=7917
12818-7917=4901
7917-4901=3016
4901-3016=1885
3016-1885=1131
1885-1131=754
1131-754=377
754-377*2=0

最後の377が最大公約数だ.
 このように引き算と多少の掛け算だけで最大公約数が求まるのである.素因数分解するよりも計算量は圧倒的に少なくて済むのだ.
では(キ)を証明しよう.
(イ)よりAとBの最大公約数Dは
A=rD
B=sD
と書ける.注意するのはr,sが互いに素だということ.するとAとBとの差A-Bは
A-B=(r-s)D
と書ける.BとA-Bの最大公約数がDであるならば(イ)によりsとr-sが互いに素でなければならない.
背理法を使おう.もしsとr-sが互いに素でないとすると1でない公約数kが存在して
s=kx
r-s=ky
と書けるはずだ.しかし左辺の和はr,右辺の和はk(x+y)となる.
r=k(x+y)
s=kx
と書けることになりrとsに1でない公約数があることになり,仮定に矛盾した.したがってこのような公約数kは存在せずsとr-sとが互いに素であることがわかり,BとA-Bの最大公約数はDであるといえる.

一般に,自然数mに対してBとA-mBの最大公約数もDになる.


 A>Bなる二つの自然数A,Bの最大公約数を求める互除法のアルゴリズムは実際は次のとおりである.
AをBで割った商をQ1,あまりをR1とするとB>R1≧0で,
A=Q1B+R1
と書けて,AとBの最大公約数Dは(キ)によりBとR1の最大公約数になる.
今度はBをR1で割った商をQ2,あまりをR2とするとR1>R2≧0で,
B=Q2R1+R2
と書けて,DはR1とR2の最大公約数にもなる.
順次これを続けていき,どこかのRnで割り切れてRn+1=0となったならばD=Rnなのだ.

もしこのアルゴリズムでD=1と出たなら最大公約数が1,すなわち元の二数は互いに素だったということになる.

 別の例でこのアルゴリズムの威力を実感してみよう.16741117と11836597の最大公約数を求める.
16741117-11836597=4904520
11836597-4904520*2=2027557
4904520-2027557*2=849406
2027557-849406*2=328745
849406-328745*2=191916
328745-191916=136829
191916-136829=55087
136829-55087*2=26655
55087-26655*2=1777
26655-1777*15=0
したがって最大公約数は1777.

元の数が16741117=1777*9421,11836597=1777*6661.両方の素因数分解を見つけられますか?

付表 素因数分解表
自然数の素因数分解です.赤字は素数です.
素因数分解 素因数分解 素因数分解 素因数分解 素因数分解
1 - 11 11 21 3*7 31 31 41 41
2 2 12 22*3 22 2*11 32 25 42 2*3*7
3 3 13 13 23 23 33 3*11 43 43
4 22 14 2*7 24 23*3 34 2*17 44 22*11
5 5 15 3*5 25 52 35 5*7 45 32*5
6 2*3 16 24 26 2*13 36 22*32 46 2*23
7 7 17 17 27 33 37 37 47 47
8 23 18 2*32 28 22*7 38 2*19 48 24*3
9 32 19 19 29 29 39 3*13 49 72
10 2*5 20 22*5 30 2*3*5 40 23*5 50 2*52
素因数分解 素因数分解 素因数分解 素因数分解 素因数分解
51 3*17 61 61 71 71 81 34 91 7*13
52 22*13 62 2*31 72 23*32 82 2*41 92 22*23
53 53 63 32*7 73 73 83 83 93 3*31
54 2*33 64 26 74 2*37 84 22*3*7 94 2*47
55 5*11 65 5*13 75 3*52 85 5*17 95 5*19
56 23*7 66 2*3*11 76 22*19 86 2*43 96 25*3
57 3*19 67 67 77 7*11 87 3*29 97 97
58 2*29 68 22*17 78 2*3*13 88 23*11 98 2*72
59 59 69 3*23 79 79 89 89 99 32*11
60 22*3*5 70 2*5*7 80 25*5 90 2*32*5 100 22*52
素因数分解 素因数分解 素因数分解 素因数分解 素因数分解
101 101 111 3*37 121 112 131 131 141 3*47
102 2*3*17 112 24*7 122 2*61 132 22*3*11 142 2*71
103 103 113 113 123 3*41 133 7*19 143 11*13
104 23*13 114 2*3*19 124 22*31 134 2*67 144 24*32
105 3*5*7 115 5*23 125 53 135 33*5 145 5*29
106 2*53 116 22*29 126 2*32*7 136 23*17 146 2*73
107 107 117 32*13 127 127 137 137 147 3*72
108 22*33 118 2*59 128 27 138 2*3*23 148 22*37
109 109 119 7*17 129 3*43 139 139 149 149
110 2*5*11 120 23*3*5 130 2*5*13 140 22*5*7 150 2*3*52
素因数分解 素因数分解 素因数分解 素因数分解 素因数分解
151 151 161 7*23 171 32*19 181 181 191 191
152 23*19 162 2*34 172 22*43 182 2*7*13 192 26*3
153 32*17 163 163 173 173 183 3*61 193 193
154 2*7*11 164 22*41 174 2*3*29 184 23*23 194 2*97
155 5*31 165 3*5*11 175 52*7 185 5*37 195 3*5*13
156 22*3*13 166 2*83 176 24*11 186 2*3*31 196 22*72
157 157 167 167 177 3*59 187 11*17 197 197
158 2*79 168 23*3*7 178 2*89 188 22*47 198 2*32*11
159 3*53 169 132 179 179 189 33*7 199 199
160 25*5 170 2*5*17 180 22*32*5 190 2*5*19 200 23*52


戻る