ユークリッドの補題
すべて素数はそれが割り切らないすべての数に対して素である。
ベズーの補題を利用した証明をする。ベズーの補題によれば、x, y が互いに素な整数であるなら(x, y の最大公約数が 1 であるなら)、
を満たすような整数 r, s が存在する。
a, c が互いに素であり、かつ c ∣ {\displaystyle \mid } ab であるとすれば、ベズーの等式 (1) より、以下の等式を得る。
(2) の両辺に b を掛ければ
となる。(3) の左辺の第一項は c で割り切れ、第二項は ab で割り切れるので仮定より c でも割り切れる。従ってそれらの和も c で割り切れるから c ∣ {\displaystyle \mid } b が成り立つ。これは上述のユークリッドの補題の一般化になっている。