ユークリッドの補題
}
同値な言明として以下のようなものがある。
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 が 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 を割り切る。これが証明すべきことであった。