素因数分解の一意性(算術の基本定理)の証明

【目次】
1.証明の準備
  1-1.整数に関わる用語の定義
    1-1-1.自然数、整数、約数、倍数
    1-1-2.素数、合成数、因数、素因数、素因数分解
  1-2.素因数分解の一意性とは
  1-3.算術の基本定理とは
  1-4.素因数分解の存在の証明
2.素因数分解の一意性の証明
  2-1.補題1 剰余(余り)の一意性の証明
  2-2.定義 割り切るとは
  2-3.補題2 約数の一意性の証明
  2-4.補題3 ユークリッドの補題の証明
  2-5.定理 素因数分解の一意性の証明

教科書(数研出版、高校数学の教科書、以下同じ。詳しくは、高校数学マスター基本方針:参考にする教科書を参照ください)では、素因数分解の一意性は、証明抜きで紹介されています。

教科書では、この素因数分解の一意性のように、証明抜きで提示される事実がたくさんありますが、このような事実に疑問を持って、先生に質問をしたり、自分で本を調べたりできるかが、数学やその他の様々な能力の向上において、重要な素質になるだろうと思います。

このような事実に少しも疑問を持たずに、素通りして、問題を解くため、知識を使うことにのみ習熟することは、テストの点数を取ることには一時的には役立ちますが、結局は、もっと大切な「考えること」をなおざりにしてしまい、どこかで行き詰まることになります。

このページでは、素因数分解の一意性をきちんと証明したいと思います。

証明の準備

整数に関わる用語の定義

それでは、まず用語の定義から復習しましょう。

教科書によると、

自然数、整数、約数、倍数

自然数とは、1,2,3,・・・という数である。

整数とは、自然数と、0,-1,-2,-3,・・・を合わせた数である。

約数、倍数とは、2つの整数\(a,b\)について、ある整数\(k\)を用いて、\[a=bk\]と表されるとき、\(b\)は\(a\)の約数であるといい、\(a\)は\(b\)の倍数であるという。

ポイントは、「\(b\)が\(a\)の約数であること」、と「\(a\)は\(b\)の倍数であること」が同値であることです。この点は必ず押さえておきましょう。

ちなみに、この定義によると、\(0\)の約数はすべての整数であること、\(0\)の倍数は\(0\)のみであることを確認してみましょう。

加えて、\(a,-a,1,-1\)が\(a\)の約数であること、\(b,-b\)が\(b\)の倍数であること、\(1,-1\)の約数は\(1,-1\)のみであること、\(1,-1\)の倍数はすべての整数であること、なども確認すると良いと思います。

このようなことは、まったく覚える必要はありませんが、疑問を持って確認する癖を付けると、数学の学力が向上すると思います。つまり、定義の適用範囲、具体例をすべて列挙して確認しておくということです。

もちろん、数は無限にあるのですから、すべてというのは文字通りではなく、同じような性質があると明らかな具体例を繰り返し調べる必要は、あまりありません。

さらに注意点を挙げると、\(k\)の正負を入れ替えても、\(a\)の正負を入れ替えさえすれば、\(a=bk\)が成り立つことから、すべての整数において、その正の倍数の集合と負の倍数の集合は、正負を入れ替えれば一致することが分かります。

同様に、\(k\)の正負を入れ替えたときに、\(a\)ではなく、\(b\)の正負を入れ替えてもよいので、すべての整数において、その正の約数の集合と負の約数の集合も、正負を入れ替えれば一致することが分かります。

この倍数、約数の正負の対称性から、正の倍数、約数で成立することが、そのまま負の倍数、約数でも成立することが多くあります。

そのため、倍数、約数の議論をする際には、正の倍数、約数で成立することが、明らかに、負の倍数、約数でも成立する場合には、明確な断りなしに、正の倍数、約数のみしか議論を行わないことも、しばしばあります。

特に、議論が自然数の範囲で行われる場合には、明確な断りなしに、倍数、約数という言葉で、正の倍数、約数のみを対象としている場合が普通です。

ただ、例えば、最大公約数の定義が「最大の公約数」で済む一方で、最小公倍数の定義は「最小の”正の”公倍数」としなくてはならないように、記述の配慮が必要な場合もあります。

なぜなら、最大公約数の場合は、負の公約数を含めても含めなくても”最大の”公約数が変わることはありませんが、一方で、最小公倍数の場合には、負の公倍数を含めると、すべての負の公倍数が最小の”正の”公倍数よりも小さくなってしまい、定義の趣旨が異なってきてしまうからです。

素数、合成数、因数、素因数、素因数分解

素数とは、2以上の自然数で、1とそれ自身以外に正の約数をもたない数である。

合成数とは、2以上の自然数で、素数でない数である。

因数とは、整数がいくつかの整数の積で表されるとき、積を作る1つ1つの整数を、もとの整数の因数という。

素因数とは、素数である因数をいう。

素因数分解とは、自然数を素数だけの積の形に表すことをいう。

と定義されています。

素因数分解の一意性とは

その上で、教科書では、

合成数は、必ず素因数分解できることを簡単に証明しています。

さらに、合成数の素因数分解は、積の順序を除けばただ一通りであることを証明抜きで紹介し、これを「素因数分解の一意性」と呼ぶことになります。

したがって、素因数分解の一意性とは、合成数の素因数分解は、積の順序を除けばただ一通りであることです。

一意性とは、ただ一通りしかないこと、つまり、一つしかないことを意味します。

それは、ある自然数をどのように素因数分解しても、その素数を小さい順に左から並べたときに、左から順番に表れる素数は、必ず一致するということです。

これが一致しないのであれば、素因数分解は二通り以上ある、ということになります。

算術の基本定理とは

以上の合成数は、必ず素因数分解できること、と合成数の素因数分解は、積の順序を除けばただ一通りであることを合わせて、一般に「算術の基本定理」と呼びます。

言い換えると、前者は、素因数分解の存在、後者は、素因数分解の一意性、であり、この二つを合わせて、「算術の基本定理」と呼ぶのです。

素因数分解の存在の証明

素因数分解の存在は、教科書でも解説されていますが、ここでも少し復習すると、

【素因数分解の存在】
合成数は、必ず素数だけの積の形に表すことができる。

【証明】
まず、この命題の証明というより、前提となる事柄から確認しましょう。

素数と合成数の定義によると、自然数は、1と素数と素数でない合成数に分かれるのでした。

1の場合には、素数は2以上の自然数なので、1を素数だけの積の形では表せません。したがって、1は、元々、素因数分解することができません。

素数の場合を考えると、素数だけの積の形に表せるならば、少なくとも二つの素数の約数を持つことになります。しかし、素数は、1とそれ自身以外に正の約数をもたないので、素数だけの積の形ではやはり表せません。

したがって、素数も、元々、素因数分解することができません。

このため、素因数分解ができるのかどうか、その存在が問題となるのは、合成数の場合についてのみになるので、「合成数は」という限定が付いています。

さて、それでは、合成数の場合について考えたいと思います。

合成数は素数ではないので、1とそれ自身以外に正の約数を持つことになります。そして、その中のある一つの正の約数を因数として、合成数を二つの因数の積の形で表すことができます。

一方、その二つの因数の積のいずれの因数についても、やはり、素数であるか、合成数であるか、が決まります。素数である場合には、そのままで良く、合成数である場合には、再び、その因数の1とそれ自身以外の正の約数を取る操作を行います。

以上の操作を合成数が出てこなくなるまで繰り返します。そうすれば、始めの合成数はすべて素数だけの積の形に表すことができ、素因数分解ができました。

ここで、問題は、この操作が有限回で終了するのかということです。つまり、合成数が出てこなくなる、ことは必ず保証されているのかということです。

仮に、この操作が無限に続いてしまうとすると、表れる素数の総数も無限個ということになってしまいます。

素数は2以上の自然数なので、その積も無限に大きくなり、始めの合成数が有限であることに矛盾します。

したがって、表れる素数の総数は有限であり、この操作も有限回で終了します。

以上より、素因数分解の存在については、証明することができました。

教科書では、素因数分解の一意性の証明は、長くなってしまうので省略されてしまうことが多いのですが、このページでは、こちらが本題となります。

それでは、本題の「素因数分解の一意性」の証明に入りたいと思います。

素因数分解の一意性の証明

まず、証明の流れを確認すると、
「補題1 剰余(余り)の一意性」、「補題2 約数の一意性」、「補題3 ユークリッドの補題」の三つの補題を証明し、これらを使って、「定理 素因数分解の一意性」を証明します。

その他にも、異なる証明の手順や方法は、色々とあります。興味のある方は、様々な教科書を手に取ってみてください。高校の図書館、近くの本屋や公共図書館に適当な教科書がなくても、都道府県の図書館、国会図書館には必ず適当な教科書がたくさんあります。大きな本屋が近くにあったり、大学の図書館に入れるならば、そちらでもよいかもしれません。

できる限り簡単にアクセスできて、安く必要な教科書をそろえられるルートを開拓することは、勉強を深めていくためにはとても大切なことです。

補題1 剰余(余り)の一意性の証明

では、早速、「補題1 剰余(余り)の一意性」から証明を始めましょう。

【補題1 剰余(余り)の一意性】
すべての整数\(n\)と\(m\ (m \neq 0)\)について、次の式を満たす整数\(l\)と\(r\ (0\le r < |m|)\)がただ一つ存在する。
\begin{equation}
n\ =\ l \cdot m\ +\ r \tag{1}
\end{equation}
【証明】
まず、言葉の説明ですが、剰余とは、余りのことです。

数式(1)の意味は、整数\(n\)を\(m\)で割ると、商が\(l\)となり、余りが\(r\)になるということです。

そして、割られる数\(n\)と割る数\(m\)が決まれば、その商\(l\)と余り\(r\)もただ一通りに定まる、という事実がこの【補題1】です。

まずは、\(m>0\)の場合について考えます。

すべての整数\(k\)について、すべての整数は\(km\)で表されるか、否かが決まります。

\(n\)が\(km\)で表されるならば、\(l=k,r=0\)とすれば、少なくとも一つ\((l,r)\)の組がありました。

さらに、そのとき\(l \le k-1\)とすると、\(r\ge m\)となり、\(l \ge k+1\)とすると、\(r < 0\)となってしまい【補題1】の条件を満たす他の\((l,r)\)の組はないことが分かります。

したがって、ただ一通り、\(l=k,r=0\)の組しかないことが言えました。

一方、\(n\)が\(km\)で表されないならば、すべての整数\(k\)について、\((k-1)m<km\)なので、\(n\)を超えない最大の\(km\)となる整数\(k\)がただ一つあります。その最大の整数\(k\)を\(z\)としましょう。

\(n-zm=m\)とすると、\(n=(z+1)m\)となり、\(n\)が\(km\)で表されてしまうので、矛盾です。

\(n-zm > m\)とすると、\(n > (z+1)m\)であり、\((z+1)m > zm\)でもあります。

そのため、\((z+1)m\)は\(n\)を超えない、\(zm\)よりも大きな整数となり、\(zm\)が\(n\)を超えない最大の\(km\)で表される整数であることに矛盾します。

したがって、\(n-zm < m\)となります。加えて、\(zm\)は\(n\)を超えない整数なので、\(0 \le n-zm < m\)となります。

ここで、\(r^{‘}=n-zm\)とおけば、\((z,r^{‘})\)の組は、数式(1)\(n=zm+r^{‘}\)と、\(0 \le r^{‘} < m\)を満たします。

さらに、\(z\)はただ一つしかないので、\(r^{‘}=n-zm\)より、\(r^{‘}\)もただ一つしかないことが言え、【補題1】の条件を満たす\((l,r)\)の組がただ一通り\((z,r^{‘})\)しかないことが言えました。

\(m<0\)の場合には、\(m\)の符号が反転していることに気を付けて、\(k\)の増減を逆に取ったり、\(m\)の絶対値を用いたりすれば、同様に示すことができます。

定義 割り切るとは

「補題2 約数の一意性」を示す前に、一つ言葉の定義をしたいと思います。

【定義】
整数\(m(m\neq0)\)が整数\(n\)を割り切るとは、整数\(m\)が整数\(n\)を割ったときの剰余\(r\)が、\(r=0\)のことをいう。

したがって、整数\(m\)が整数\(n\)を割り切るとき、\(n=m\cdot l\)と表されるので、整数\(m\)は整数\(n\)の約数です。

逆に、整数\(m\)は整数\(n\)の約数であれば、\(n=m\cdot l\)と表されます。

一方、【補題1 剰余(余り)の一意性】により、\(n\ =\ l^{‘} \cdot m\ +\ r\)と\(0\le r\lt |m|\)を満たす\(( l^{‘},r)\)はただ一通りしかありません。

仮に\(l \neq l^{‘}\)とすると、\((l,0)\)と\((l^{‘},r)\)の二通りの【補題1】の条件を満たす整数の組があることになり、矛盾します。

したがって、\(l=l^{‘}\)であり、\(r=0\)であることが分かります。つまり、整数\(m\)が整数\(n\)を割り切ります。

以上から、整数\(m\neq0\)のとき、整数\(m\)が整数\(n\)を割り切ることと、整数\(m\)が整数\(n\)の約数であることは同値であることが分かります。

補題2 約数の一意性の証明

それでは、「補題2 約数の一意性」を証明したいと思います。

【補題2 約数の一意性】
整数\(n\)の約数の集合はただ一通りに定まる。

【証明】
\(0\)の約数は、すべての整数\(m\)について、\(0=m \cdot 0\)が成り立つので、すべての整数に定まる。

\(1\)の約数は、\(1=1 \cdot 1\)、\(1=-1 \cdot -1\)しかないので、\(1,-1\)に定まる。

\(-1\)の約数は、\(-1=1 \cdot -1\)、\(-1=-1 \cdot 1\)しかないので、\(1,-1\)に定まる。

そこで、以下では残りの整数\(|n|\ge2\)について考えます。

整数\(m(|m| \gt |n|)\)の場合、\(n=mk\)を満たす整数\(k\)があるとすると、\(k\neq0\)より、
\[|n|=|m||k| \ge |m| \]
となり矛盾します。

したがって、整数\(m(|m| \gt |n|)\)には、\(n\)の約数はありません。

そこで、整数\(n\)の約数は、整数\(m(|m| \le |n|)\)の有限個の中にしかないことが分かります。

そして、\(m=0\)の場合には、\(m=0\)は整数\(|n|\ge 2\)の約数ではありません。

それ以外の\(m \neq 0\)の場合には、【補題1 剰余(余り)の一意性】より、すべての整数\(m(|m| \le |n|)\)について、整数\(n\)を\(m\)で割った剰余\(0 \le r \lt |m|\)が一つに定まります。

そこで、\(r=0\)となる整数\(m\)、つまり、整数\(n\)を割り切る整数\(m\)は、ただ一通りに定まります。

一方、\(r=0\)となる整数\(m\)が\(n\)の約数であり、\(r\neq0\)となる整数\(m\)は\(n\)の約数ではないので、\(r=0\)となる整数\(m\)を取り出せば、それは、\(n\)の約数の集合となります。

したがって、\(n\)の約数の集合でもある、\(r=0\)となる整数\(m\)はただ一通りに定まるので、\(n\)の約数の集合は一通りに定まりました。

補題3 ユークリッドの補題の証明

【補題3 ユークリッドの補題】
素数\(p\)が自然数\(a,b\ge 2\)の積\(ab\)を割り切るならば、\(p\)は\(a\)又は\(b\)の少なくともいずれか一方を割り切る。

【証明】
【補題1 剰余(余り)の一意性】より、次を満たす整数\(l_{1},r_{1},l^{‘}_{1},r^{‘}_{1}\)が一通り存在します。

\[a=l_{1}p+r_{1}\hspace{30pt}0\le r_{1}\lt p \tag{1}\]

\[b=l^{‘}_{1}p+r^{‘}_{1}\hspace{30pt}0\le r^{‘}_{1}\lt p \tag{2}\]

証明の方針としては、結論「\(p\)は\(a\)又は\(b\)の少なくともいずれか一方を割り切る」の、否定を仮定して矛盾を導き出してみましょう。

つまり、「\(p\)は\(a\)と\(b\)のいずれも割り切らない」を仮定します。

仮定と式(1)(2)より、\(r_{1}\neq 0\)かつ\(r^{‘}_{1}\neq 0\)となります。

ここで、すべての自然数\(i\ (1\le i)\)について、\(r_{i}\neq 0\)かつ\(r^{‘}_{i}\neq 0\)が成り立てば、

【補題1 剰余(余り)の一意性】より、次を満たす整数\(l_{i+1},r_{i+1},l^{‘}_{i+1},r^{‘}_{i+1}\)が一通り存在します。

\[p=l_{i+1}r_{i}+r_{i+1}\hspace{30pt}0\le r_{i+1}\lt r_{i} \tag{3}\]

\[p=l^{‘}_{i+1}r^{‘}_{i}+r^{‘}_{i+1}\hspace{30pt}0\le r^{‘}_{i+1}\lt r^{‘}_{i} \tag{4}\]

特に、すべての\(i\ (1\le i)\)について、

\[r_{i}\gt r_{i+1}\ge 0\]

\[r^{‘}_{i}\gt r^{‘}_{i+1}\ge 0\]

なので、\(i\)が増えると、\(r_{i}\)と\(r^{‘}_{i}\)は、必ず減少し、かつ、\(0\)以上です。

したがって、\(r_{i}\)又は\(r^{‘}_{i}\)の少なくともいずれか一方が、先にあるいは同時に、\(0\)になります。

どちらが先にあるいは同時に\(0\)になっても、以下の議論は変わりがないので、

ここでは、先にあるいは同時に\(0\)となる\(r_{i}\)を\(r_{k}\)とします。

つまり、ある自然数\(k\ (2\le k)\)があって、\(r_{k}=0\)となるので、

式(3)で存在を認められるのは、\(r_{k}\)までとなり、したがって、\(1\le i\le k\)であることが分かります。

さらに、\(r_{k}=0\)と式(3)より、

\[p=l_{k}r_{k-1} \tag{5}\]

となります。

\(p\)は、素数なので、その正の約数は\(1\)又は\(p\)しかありません。

式(5)より、\(r_{k-1}\)は\(p\)の約数なので、したがって、\(r_{k-1}\)は、\(1\)又は\(p\)になりますが、

式(1)(3)より、\(r_{k-1}\le r_{1}\lt p\)なので、\(r_{k-1}\neq p\)であり、

\[r_{k-1}=1 \tag{6}\]

と分かります。

次に、式(1)(2)より、

\[(a-l_{1}p)(b-l^{‘}_{1}p)=ab-p(al^{‘}_{1}+bl_{1})+l_{1}l^{‘}_{1}p^2=r_{1}r^{‘}_{1} \tag{7}\]

であり、前提より\(ab\)は、\(p\)で割り切れるので、ある整数\(c_{1}\)があって、

\[ab=pc_{1} \tag{8}\]

と表すことができます。

式(8)を式(7)に代入して、

\[pc_{1}-p(al^{‘}_{1}+bl_{1}p)+l_{1}l^{‘}_{1}p^2=(c_{1}-al^{‘}_{1}-bl_{1}+l_{1}l^{‘}_{1}p)\cdot p=r_{1}r^{‘}_{1} \tag{9}\]

となるので、\(p\)は、\(r_{1}r^{‘}_{1}\)の約数であることが分かりました。

つまり、ある整数\(c_{2}\)があって、

\[r_{1}r^{‘}_{1}=pc_{2} \tag{10}\]

と表すことができます。

さらに、式(3)(4)より、

\[(p-l_{i+1}r_{i})(p-l^{‘}_{i+1}r^{‘}_{i})=p^2-p(l_{i+1}r_{i}+l^{‘}_{i+1}r^{‘}_{i})+l_{i+1}l^{‘}_{i+1}r_{i}r^{‘}_{i}=r_{i+1}r^{‘}_{i+1}\]

なので、\(p\)が\(r_{i}r^{‘}_{i}\)の約数であれば、\(p\)は\(r_{i+1}r^{‘}_{i+1}\)の約数でもあることが分かります。

これと、式(10)より、すべての自然数\(i(1\le i \le k)\)で、\(p\)は、\(r_{i}r^{‘}_{i}\)の約数であることが分かりました。

特に、ある整数\(c_{k}\)があって、

\[r_{k-1}r^{‘}_{k-1}=pc_{k}\]

と表せるので、これと式(6)より、

\[r^{‘}_{k-1}=pc_{k} \tag{11}\]

が分かります。

ここで、\(r_{k}\)は、一番先にあるいは同時に\(0\)となる\(r_{i}\)だったので、その前にある\(r^{‘}_{k-1}\)は、

\[r^{‘}_{k-1}\gt 0\]

となります。

したがって、これと式(11)より、\(c_{k}\gt 0\)となります。

さらに、これと式(11)より、\(r^{‘}_{k-1} \ge p\)となります。

しかし、式(2)(4)より、\(r^{‘}_{k-1}\le r^{‘}_{1}\lt p\)なので、矛盾することになります。

この証明のポイントは、その剰余の列が必ず減少すること、剰余が\(0\)になるまで繰り返し取れること、必ず素数\(p\)の約数となる剰余が出てくること、素数\(p\)より小さな素数\(p\)の正の約数は\(1\)しかないこと、そして、すべての剰余の積が素数\(p\)の倍数であり続けることです。

さらに、証明をよく読むと、すべての剰余の積が素数\(p\)の倍数であり続けること、には\(p\)が素数であることは何も証明に使われていないので、これを素数\(p\)ではなく整数一般に置き換えても良いと分かります。

つまり、すべての剰余の積が素数\(p\)の倍数であり続けること、は【補題1 剰余(余り)の一意性】から導き出される整数の積の性質と言えることが分かります。

したがって、この証明の本質は、【補題1 剰余(余り)の一意性】から導き出される整数の積の性質と、積で分割できないという素数の性質の合わせ技である、と言えるかと思います。

大学以降では、このような整数の積の性質や分割できない素数の性質が、整数全体の構造をかなり厳しく束縛していることを、様々な角度から学んでいきます。ユークリッドの補題は、その不思議で魅力的な整数の世界が垣間見える入口の定理とも言え、その意味でとても重要な命題であると思います。

定理 素因数分解の一意性の証明

さて、長くなりましたが、やっと本題である「定理 素因数分解の一意性」を証明するための準備が整いました。

【定理 素因数分解の一意性】
合成数の素因数分解は、積の順序を除けばただ一通りである。

【証明】
前述した通り、合成数の素因数分解の存在は示されています。

したがって、合成数を\(n\)とすると、\(n\)はすべて素数だけの積で表すことができます。

それでは、「積の順序を除けばただ一通りである」ことの否定を仮定して矛盾を導き出してみましょう。

つまり、「積の順序を除いても二通り以上ある」ことを仮定します。

ちなみに、「積の順序を除いても二通り以上ある」とは、その素数だけの積を小さい順に左から並べたときに、左から順番に表れる素数を比較していくと、異なる素数が少なくとも一つ表れる、ということと同値です。

つまり、「積の順序を除く」とは、組み合わせで考えるということです。

それでは、少なくとも二つある\(n\)を表したすべて素数だけの積に対して、それぞれの数の組の積を\(X\)、\(Y\)と名付けましょう。

前提として、\(n=X=Y\)が成り立っているので、もしも、\(X\)と\(Y\)に同じ素数があったとしたら、各辺から消すことができます。

同じ素数がある限り、各辺から消す操作を行い、操作後のそれぞれを\(n^{‘}\)、\(X^{‘}\)、\(Y^{‘}\)と名付けます。

もちろん、\(n^{‘}=X^{‘}=Y^{‘}\)が成立しています。

ここで、仮定より、\(X^{‘}\)には、少なくとも二つ以上の素数が残っています。

なぜなら、\(X^{‘}=1\)ならば、すべての素数は同じだったことになり矛盾します。

あるいは、\(X^{‘}\)が一つの素数ならば、素数の\(1\)でない約数はそれ自身のみなので、\(Y^{‘}\)も同じ素数となり、まだ消す操作ができるからです。

したがって、\(X^{‘}\)に含まれるある素数を\(p\)とし、\(p\)以外の\(X^{‘}\)に含まれる素数の積を\(a\)とすると、

\[n^{‘}=pa\]

であり、\(n^{‘}\)は\(p\)で割り切れます。

一方、\(X^{‘}\)と\(Y^{‘}\)には同じ素数がないはずなので、\(Y^{‘}\)に\(p\)は含まれません。

ここで、【補題3 ユークリッドの補題】の対偶を考えます。

つまり、【補題3 ユークリッドの補題】は、「素数\(p\)が自然数\(a,b\ge 2\)の積\(ab\)を割り切るならば、\(p\)は\(a\)又は\(b\)の少なくともいずれか一方を割り切る。」なので、その対偶は、

「素数\(p\)が自然数\(a\ge 2\)と\(b\ge 2\)のいずれも割り切らなければ、\(p\)は積\(ab\)を割り切らない。」となります。

今、\(Y^{‘}\)というすべて素数の積には\(p\)が含まれていません。

したがって、\(Y^{‘}\)に含まれるすべての素数は、\(p\)ではないので\(p\)によって割り切られません。

したがって、どの素数同士を掛けても、【補題3 ユークリッドの補題】の対偶より、その積は\(p\)によって割り切られません。

その積同士を掛けても、同様であり、\(p\)によって割り切られないことは、すべての掛け算を終えて\(n^{‘}\)になるまで、同様に成り立ちます。

したがって、\(n^{‘}\)は\(p\)によって割り切られません。

つまり、\(X^{‘}\)によると\(n^{‘}\)は\(p\)で割り切れますが、\(Y^{‘}\)によると\(n^{‘}\)は\(p\)で割り切れません。

言い換えれば、\(X^{‘}\)によると\(p\)は\(n^{‘}\)の約数ですが、\(Y^{‘}\)によると\(p\)は\(n^{‘}\)の約数ではありません。

これは、【補題2 約数の一意性】による事実、\(n^{‘}\)の約数の集合がただ一通りに定まることに矛盾します。

公開日:2019年7月05日
修正日:2019年7月09日 正負の倍数、約数の対称性についての注意を追加