最大公約数と最小公倍数を求める～2/3 素因数分解を利用する～

最大公約数と最小公倍数を求める～1/3 割れるだけ割ってみる～
最大公約数と最小公倍数を求める～2/3 素因数分解を利用する～ ←この記事
最大公約数と最小公倍数を求める～3/3 ユークリッドの互除法を利用する～

ここでは 素因数分解 を使って
最大公約数と、最小公倍数を求める方法を勉強する

素因数分解を利用する
参考にした書籍/サイトさん

素因数分解を利用する

前の記事の事前知識で述べた通り、2 以上の数は素数1つ、またはいくつかの素数の掛け合わせによって表現できる

ここで、2 以上のある数を $X$
それから抽出できる素因数を $p$ としたとき
それらの関係を

${\hspace{6pt}}X=p_1{\times}p_2{\times}p_3{\times}p_4{\cdots}$

のような掛け算の式で表現することを 素因数分解 と呼ぶ

f:id:DarkCrowCorvus:20171202081223j:plain

この素因数分解を使って2つの値の最大公約数と最小公倍数を求める。

■求め方..
2つの値を素因数分解する。

見つかった素因数のうち、同じ素因数を指数を使ってまとめる。
2つの数の素因数分解の結果は、どちらも次の通りに表現できるようになるはず

${\hspace{6pt}}X=(p_1)^{r1}{\times}(p_2)^{r2}{\times}(p_3)^{r3}{\times}(p_4)^{r4}{\cdots}$

f:id:DarkCrowCorvus:20171202205657j:plain

その後、2つの式を縦に並べて、同じ素因数の「指数が小さい方」を片側に、「指数が大きい方」をもう片側に寄せる。

f:id:DarkCrowCorvus:20171202222530j:plain
なおここでは、片方にあって、もう片方にはない素因数が存在する場合、
ない方の式でその素因数を $(p_i)^{0}$ のように表現する

そうしてできた指数の小さい方を集めた式の答えが 2つの数の 最大公約数
指数の大きい方を集めた式の答えが 2つの数の 最小公倍数 になる

f:id:DarkCrowCorvus:20171202222557j:plain

素因数分解の一意性

これの理解のために、
先に「素因数分解の一意性」について知っておきたい

■ 素因数分解の一意性とは...

ある数を素因数分解するとき、素因数の並び順を考慮しないとするならば、それを表す式はただ一通りしか存在しない..という定理

またこの「素因数分解の一意性」の理解のために、先に「ユークリッドの補題」について知っておきたい

■ ユークリッドの補題とは...

ある2つの数の積 $ab$ を、
ある数 $p$ で割り切ることができるならば、

$p$ は $a$ と $b$ の
少なくともどちらか一方を割り切ることができる…という定理

この定理は一見アタリマエのように見える。数学ではこれを 自明である というらしいのだけど、実際のところこれは自明ではないらしい。

この証明のために、先に「ベズーの補題」という定理を知る必要があるらしい...が、これ以上細かく見ていくと、本題から離れすぎて何の記事だかよくわからなくなりそう。
今回は単に「そういった定理があるからユークリッドの補題は成り立つ」とだけ覚えておいて、先に進みたい。

■ 証明 (素因数分解の一意性)

ある数を素因数分解した結果が、2通りになる可能性があるとする

f:id:DarkCrowCorvus:20171203152058j:plain

${\hspace{6pt}}X=p_1{\times}p_2{\times}p_3{\cdots}{\times}p_n$
$\hspace{16pt}=q_1{\times}q_2{\times}q_3{\cdots}{\times}q_m \hspace{15pt}_{(n \leq m)}$

ここで、片方の素因数分解「 $p_1{\times}p_2{\cdots}$ 」の中に含まれる、
素因数 $p_1$ に着目してみる。

左辺の $X$ は $p_1$ を素因数にもつ。
よって $p_1$ の倍数であるため、
$X$ は $p_1$ によって、割りきることができる $\cdots$ ①

もう片方の素因数分解「 $q_1{\times}q_2{\cdots}$ 」は、
同じ $X$ を成す掛け算の式である。

さきほどの「ユークリッドの補題」の定理に従うならば、①によってそのもう片方の素因数分解の中に、 $p_1$ で割り切れる素因数が存在するはずである。

f:id:DarkCrowCorvus:20171203152128j:plain

ここで、 $p_1$ によって割り切れる素因数 $q_1$ が見つかったとする。

$q_1$ は素因数。つまり 1 か自身と同じ数でしか割り切ることができない。そして事前知識で述べたとおり、1 は素数に含まれないため、素因数分解の中に 1 が現れることはない

よってこの要件を満たす $q_1$ は「 $q_1=p_1$ 」ということになる。
「 $p_2,p_3{\cdots}$ 」についても、同じくそれらと一致する「 $q_2,q_3{\cdots}$ 」を見つけられるはず

f:id:DarkCrowCorvus:20171203152212j:plain

次に $p_1{\cdots}p_n$ すべてに一致する $q_1{\cdots}q_n$ を見つけられた後、まだ片方の素因数分解の中に $q_{n+1}{\cdots}q_m$ が残る場合があるかを考えてみる

${\hspace{6pt}}X=p_1{\times}p_2{\times}p_3{\cdots}{\times}p_n$
$\hspace{16pt}=q_1{\times}q_2{\times}q_3{\cdots}{\times}q_m \hspace{15pt}_{(n \leq m)}$

この式を満たすためには、片方の式に余分に存在する素因数 $q_{n+1}{\cdots}q_m$ は全て 1 でなければならない。しかし前述のとおり、1 が素因数分解の中に含まれるのは不適である。

f:id:DarkCrowCorvus:20171203152234j:plain

よって双方の素因数の数は一致する $(n=m)$
どちらか一方が多かったり、少なかったりする場面は存在しない

これらを踏まえて、上記 2つの素因数分解の式は一致する。
素因数分解の結果は、その並び順を考慮しないならば一意になる。

自分なりに解釈 (最大公約数)

2つの数の素因数分解の結果、素因数の指数が小さい (または等しい) ほうを集めた式から、最大公約数が求められる。

その式に含まれる素因数は、元の2つの数と比べてどれも指数が小さい、または等しくなるため、前述の事実に従って、その式から成る数は、2つの数にとっての約数 (公約数) になる

またその式から成る数が、2つの数の公約数であるためには、式中のどの素因数の指数もそれ以上大きくすることができない。

たとえば、今よりも大きな公約数を作ろうとする時、その数の少なくとも1つ以上の素因数の指数は、もとの公約数の同じ素因数の指数よりも大きくなる

しかし、どの素因数の指数が今より大きくなっても、もとの2つの数のうち、少なくともどちらか一方の同じ素因数の指数よりも大きくなってしまう

f:id:DarkCrowCorvus:20171205010943j:plain

前述の事実「約数なら素因数の指数がどれも小さいか等しい」を満たさなくなるため
その一方、あるいは両方の約数になることができず、結果公約数ではなくなる

素因数の指数が小さい (または等しい) ほうを集めた式から成る数について、結局それより大きな公約数を作ることはできないため、それが 2つの数にとっての最大公約数になる

自分なりに解釈 (最小公倍数)

2つの数の素因数分解の結果、素因数の指数が大きい (または等しい) ほうを集めた式から、最小公倍数が求められる

その式に含まれる素因数は、もとの2つの数と比べてどれも指数が大きいか、または等しい。一つ上の項で解説した事実に従い、もとの2つの数はその式から成る数の約数、よってその式から成る数はもとの2つの数の倍数 (公倍数) になる

またその式から成る数が、2つの数の公倍数であるためには、式中のどの素因数の指数も今より小さくすることができない。

理屈は上の項で説明したのと大体同じ。
今よりも小さな公倍数を作れないため、結果それが 最小公倍数 になる