Некоторые доказательства используют тот факт, что если простое число p делит произведение двух натуральных чисел a и b, то p делит либо a, либо b, утверждение, известное как лемма Евклида.
Для этого воспользуемся следующей леммой: если простое число p делит произведение ab, то оно делит a или делит b (лемма Евклида).