Введение
Простой делитель произведения делит один из множителей.
В алгебре и теории чисел лемма Евклида отражает фундаментальное свойство простых чисел, а именно:
Например, если , , , то , и поскольку это число делится на 19, то из леммы следует, что одно или оба числа 133 или 143 также должны делиться на 19. В действительности,
Если предпосылка леммы не выполняется, то есть p является составным числом, то ее заключение может быть как истинным, так и ложным. Например, в случае , , , составное число 10 делит , но 10 не делит ни 4, ни 15. Это свойство является ключевым в доказательстве основной теоремы арифметики. Оно используется для определения простых элементов, являющихся обобщением простых чисел на произвольные коммутативные кольца. Лемма Евклида показывает, что в кольце целых чисел неприводимые элементы также являются простыми элементами. Доказательство использует индукцию, поэтому оно не применимо ко всем целостностным областям.
If the premise of the lemma does not hold, i. e., p is a composite number, its consequent may be either true or false. For example, in the case of , , , composite number 10 divides , but 10 divides neither 4 nor 15. This property is the key in the proof of the fundamental theorem of arithmetic. It is used to define prime elements, a generalization of prime numbers to arbitrary commutative rings. Euclid's Lemma shows that in the integers irreducible elements are also prime elements. The proof uses induction so it does not apply to all integral domains.
История
Лемма впервые появляется как предложение 30 в книге VII «Начал» Евклида. Она включена практически во все учебники, посвященные элементарной теории чисел. Обобщение леммы на целые числа появилось в учебнике Жана Престе «Nouveaux Elémens de Mathématiques» в 1681 году. В трактате Карла Фридриха Гаусса «Disquisitiones Arithmeticae» формулировка леммы соответствует Предложению 14 Евклида (Раздел 2), которое он использует для доказательства единственности разложения целого числа на простые множители (Теорема 16), принимая существование как "очевидное". Из этого существования и единственности он затем выводит обобщение понятия простых чисел на целые числа. По этой причине обобщение леммы Евклида иногда называют леммой Гаусса, однако некоторые считают такое употребление некорректным из-за путаницы с леммой Гаусса о квадратичных остатках.
Доказательства
Первые два подраздела содержат доказательства обобщенной версии леммы Евклида, а именно: если n делит произведение ab и взаимно просто с a, то n делит b. Оригинальная лемма Евклида следует из этого немедленно, поскольку если n – простое число, то оно либо делит a, либо не делит a, в этом случае оно взаимно просто с a, и, согласно обобщенной версии, делит b.