ユークリッドの補題

ユークリッドの補題

ユークリッドの補題（あるいはユークリッドの第一定理とも称される）は、整数論において素数が持つ極めて基本的な性質を示す定理です。紀元前3世紀頃、古代ギリシアの数学者アレクサンドリアのエウクレイデス（ユークリッド）によって、その主著『原論』の第7巻 命題30として示されました。この定理は、現代の数論において、あらゆる正の整数が素数の積としてただ一通りに表される（素因数分解の一意性）という、整数論の基本定理を証明する上で欠かせない役割を担っています。

定理の内容

ユークリッドの補題は、次のように述べられます。

ある素数 `p` が、二つの整数 `a` と `b` の積 `ab` を割り切るならば、`p` は `a` を割り切るか、または `p` は `b` を割り切る。

数論の記号を用いると、これは `p | ab` であれば `p | a` または `p | b` (`p | ab ⇒ p | a ∨ p | b`) と表現されます。ここで `p | x` は「`p` が `x` を割り切る」ことを意味します。

この主張は、いくつかの同値な表現でも知られています。例えば：

もし素数 `p` が整数 `a` も整数 `b` も割り切らないならば、その積 `ab` も `p` では割り切れない (`p ∤ a ∧ p ∤ b ⇒ p ∤ ab`)。
もし素数 `p` が整数 `a` を割り切らないにもかかわらず、積 `ab` を割り切るならば、必ず `p` は整数 `b` を割り切る (`p ∤ a ∧ p | ab ⇒ p | b`)。

これらの表現は、元の補題と同じ内容を異なる視点から述べたものです。

具体例

定理の内容を確認するために、具体的な数値で考えてみましょう。

素数 `p = 19` を選び、二つの整数として `a = 133` と `b = 143` を取ります。
これらの積 `ab` は `133 × 143 = 19019` です。
`19019` を `19` で割ると `1001` となり、割り切れます (`19 | 19019`)。
ユークリッドの補題によれば、この場合、`a = 133` と `b = 143` のうち、少なくとも一方は `19` で割り切れるはずです。
実際に `a = 133` を `19` で割ってみると、`133 ÷ 19 = 7` となり、割り切れることがわかります (`19 | 133`)。このように、定理の主張が成り立っています。

合成数の場合の注意点

ユークリッドの補題が成り立つためには、「割り切る数 `p` が素数である」という条件が不可欠です。もし `p` が素数ではなく合成数である場合、この主張は一般には成り立ちません。

例として、合成数 `p = 10` を考えます。二つの整数として `a = 4`、`b = 15` を選びましょう。
積 `ab = 4 × 15 = 60` は `10` で割り切れます (`10 | 60`)。
しかし、`a = 4` は `10` で割り切れず (`10 ∤ 4`)、`b = 15` も `10` で割り切れません (`10 ∤ 15`)。
このように、`p` が合成数である場合は、積は割り切れても、その因子が個々に割り切られるとは限らないのです。この反例は、素数性の条件がなぜ重要であるかを明確に示しています。

一般化された形

ユークリッドの補題は、素数という条件を少し緩めた、より一般的な形で述べることもできます。

ある整数 `c` が、整数 `a` と互いに素であり、かつ `c` が二つの整数 `a` と `b` の積 `ab` を割り切るならば、必ず `c` は `b` を割り切る。

ここで「互いに素」とは、二つの整数が1以外の公約数を持たないことを指します。もし `c` が素数 `p` であり、かつ `p` が `a` を割り切らないならば、素数の性質から `p` と `a` は互いに素になります。したがって、この一般化された命題に `c=p` を代入すれば、「`p` が `a` と互いに素であり (`p ∤ a` の場合)、かつ `p` が `ab` を割り切るならば、`p` は `b` を割り切る」となり、これはユークリッドの補題の同値な表現の一つと一致します。このように、ユークリッドの補題はより一般的な整数の性質の特別な場合と見なすこともできます。

証明の概要

ユークリッドの補題やその一般化は、現代数学ではいくつかの方法で証明されます。代表的なものとしては、拡張されたユークリッドの互除法から導かれるベズーの補題を用いる方法があります。これは、互いに素な二つの整数 `x`, `y` に対して、`xr + ys = 1` を満たす整数 `r`, `s` が存在することを利用します。`c` と `a` が互いに素で `c | ab` の場合、`ar + cs = 1` から出発し、両辺に `b` を掛けるなどの操作によって `c | b` を導きます。

また、最小公倍数と最大公約数の性質、特に互いに素な二数の最小公倍数がその積に等しいという性質 (`lcm(a, c) = ac`) を利用して証明することも可能です。`c | ab` かつ `a | ab` より `ab` は `a` と `c` の公倍数であり、互いに素な場合の最小公倍数が `ac` であることから `ac | ab`、したがって `c | b` を導きます。

『原論』におけるオリジナルの証明は、現代の代数的な記法とは異なり、比例論に基づいた幾何学的な議論によって行われています。当時の数学的枠組みの中で、複数の命題を組み合わせて論理的にユークリッドの補題を導くその手法は、現代から見ても巧妙なものです。

ユークリッドの補題は、一見単純に見えますが、素数が持つ割り算に関する特別な性質を捉えており、整数論の多くの重要な結果の基礎となっています。

もう一度検索