ユークリッドの補題

ユークリッドの補題（ユークリッドのほだい、英: Euclid's lemma）またはユークリッドの第一定理（ユークリッドのだいいちていり、英: Euclid's first theorem）とは素数に関する基本的な性質について述べた次の補題である： ユークリッドの補題 ― 素数 p が 2 つの整数の積 ab を割り切るなら、その素数 p は a または b の少なくとも 1 つを割り切る。 この性質は整数論の基本定理を証明する鍵となる。 ユークリッドの補題の名は、古代ギリシアの数学者アレクサンドリアのエウクレイデスの著作『原論』第7巻の命題30で示されたことによる。 たとえば、p = 19、a = 133、b = 143 の場合、ab = 133 × 143 = 19019 について、ab = 19019 は p = 19 で割り切れるので、ユークリッドの補題から a = 133, b = 143 の少なくとも一方は p = 19 で割り切ることができる。実際、133 ÷ 19 = 7 であり a = 133 は p = 19 で割り切れる。 ユークリッドの補題は p が合成数の場合には成り立たない。 たとえば、p = 10、a = 4、b = 15 の場合、合成数 p = 10 は積 ab = 4 × 15 = 60 を割り切るにもかかわらず、 p = 10 は a = 4 を割り切れないし b = 15 も割り切ることができない (ab = 60 = 10 × 6)。 p を素数とし、2 つの整数 a, b の積 ab は p で割り切れるとする（このことは記号的に p ∣ {\displaystyle \mid } ab と表す。これの否定は p ∤ {\displaystyle \nmid } ab と表され、ab が p で割り切れないことを示す）。このとき p ∣ {\displaystyle \mid } a または p ∣ {\displaystyle \mid } b、あるいはその両方が成り立つ。 p ∣ a b ⇒ p ∣ a ∨ p ∣ b ( p ∤ a b ∨ p ∣ a ∨ p ∣ b ) . {\displaystyle p\mid ab\Rightarrow p\mid a\lor p\mid b\qquad \left(p\nmid ab\lor p\mid a\lor p\mid b\right).} 同値な言明として以下のようなものがある。 p ∤ {\displaystyle \nmid } a かつ p ∤ {\displaystyle \nmid } b ならば p ∤ {\displaystyle \nmid } ab p ∤ a ∧ p ∤ b ⇒ p ∤ a b {\displaystyle p\nmid a\land p\nmid b\Rightarrow p\nmid ab} p ∤ {\displaystyle \nmid } a かつ p ∣ {\displaystyle \mid } ab ならば p ∣ {\displaystyle \mid } b p ∤ a ∧ p ∣ a b ⇒ p ∣ b {\displaystyle p\nmid a\land p\mid ab\Rightarrow p\mid b} 一般化された補題もまたユークリッドの補題と呼ばれる： 定理 ― c が a と互いに素であり、かつ c ∣ {\displaystyle \mid } ab ならば、c ∣ {\displaystyle \mid } b である。 この定理がユークリッドの補題の一般化であることは、c が素数なら c ∣ {\displaystyle \mid } a c は a と互いに素のため c ∤ {\displaystyle \nmid } a、従って c ∣ {\displaystyle \mid } b のいずれかであることによる。 ベズーの補題を利用した証明をする。ベズーの補題によれば、x, y が互いに素な整数であるなら（x, y の最大公約数が 1 であるなら）、 r x + s y = 1 {\displaystyle rx+sy=1} (1) を満たすような整数 r, s が存在する。 a, c が互いに素であり、かつ c ∣ {\displaystyle \mid } ab であるとすれば、ベズーの等式 (1) より、以下の等式を得る。 r c + s a = 1. {\displaystyle rc+sa=1.} (2) (2) の両辺に b を掛ければ r c b + s a b = b {\displaystyle rcb+sab=b} (3) となる。(3) の左辺の第一項は c で割り切れ、第二項は ab で割り切れるので仮定より c でも割り切れる。従ってそれらの和も c で割り切れるから c ∣ {\displaystyle \mid } b が成り立つ。これは上述のユークリッドの補題の一般化になっている。 公倍数は最小公倍数の倍数である。…① 公約数は最大公約数の約数である。…② 二つの正整数 a , c {\displaystyle a,c} の最小公倍数を l {\displaystyle l} 、最大公約数を g {\displaystyle g} とするとき、 a c = l g {\displaystyle ac=lg} の関係がある。…③ ③は①②より直接証明できる。 今 a , c {\displaystyle a,c} が互いに素であるとき g = 1 {\displaystyle g=1} ．ゆえに l = l c m ( a , c ) = a c {\displaystyle l=lcm(a,c)=ac} ．…④ ここでユークリッドの補題の前提条件として a , c {\displaystyle a,c} が互いに素であり、かつ c ∣ a b {\displaystyle c\mid ab} のとき， a b {\displaystyle ab} は c {\displaystyle c} の倍数かつ、当然 a {\displaystyle a} の倍数であるから、 a b {\displaystyle ab} は a , c {\displaystyle a,c} の公倍数． ④より l c m ( a , c ) = a c {\displaystyle lcm(a,c)=ac} で①より a c ∣ a b {\displaystyle ac\mid ab} ．ゆえに c ∣ b {\displaystyle c\mid b} . これが証明すべきことであった． 『原論』では第7巻の命題30において、ユークリッドの補題が証明されている。『原論』にある証明はそのままでは意味を理解することが難しいので、Heath (1956, pp. 331f)にある証明を引用する。 命題19 もし四つの数が比例するならば，第1と第4の積は第2と第3の積に等しいであろう。そしてもし第1と第4の積が第2と第3の積に等しいならば，四つの数は比例するであろう。 命題20 同じ比をもつ2数のうち最小の数はそれと同じ比をもつ2数を，大きい数が大きい数を，小さい数が小さい数をそれぞれ割り切り，その商は等しい。 命題21 互いに素である2数はそれらと同じ比をもつ2数のうち最小である。 命題29 すべて素数はそれが割り切らないすべての数に対して素である。 命題30 もし二つの数が互いにかけあわせてある数をつくり，2数の積を何らかの素数が割り切るならば，それは最初の2数の一つを割り切るであろう。 証明 素数 c が ab を割り切るならば，c は a または b を割り切るであろう。 c が a を割り切らないと仮定せよ。 そうすれば，［命題29］より，c と a は互いに素である。 ab＝mc と仮定せよ。 そうすれば，［命題19］より，c ： a＝b ： m となる。 そうすれば，［命題20］と［命題21］より，自然数 n≧1 があって，b＝nc となる。 したがって，c は b を割り切る。 同様にして，c が b を割り切らないとき，c は a を割り切る。 したがって，c は a または b を割り切る。 これが証明すべきことであった。