Лемма Евклида

Лемма Евклида — классический результат элементарной теории чисел. Она сформулирована как предложение 30 в книге VII «Начал» Евклида и является ключевой для доказательства основной теоремы арифметики. Современная формулировка[1]:

Если произведение нескольких сомножителей делится на простое число , то по крайней мере один из сомножителей делится на .

Все числа в данной статье подразумеваются целыми, если не оговорено иное.

Пример. 19 — простое число, и оно делит Следовательно, один из сомножителей делится на 19, а именно:

Если — не простое число, то теорема может не выполняться. Пример: делится на 20, однако ни один из сомножителей на 20 не делится.

Доказательство

Пусть делится на , но не делится на . Тогда и  — взаимно простые, следовательно, найдутся целые числа и такие, что

(соотношение Безу).

Умножая обе части на , получаем

Оба слагаемых в левой части делятся на , значит, и правая часть делится на , ч. т. д.[2]

Обобщения

Если произведение делится на и взаимно просты, то[3] делится на

Лемма Евклида имеет место не только в кольце целых чисел, но и в других факториальных кольцах, где роль простых чисел играют неприводимые элементы. В частности, она справедлива в евклидовых кольцах[4], например:

Примечания

  1. Виноградов, 1952, с. 20.
  2. Калужнин Л. А. Основная теорема арифметики. М.: Наука, 1969. — С. 13 (теорема 4). — 32 с. — (Популярные лекции по математике).
  3. Бухштаб А. А. Теория чисел. М.: Просвещение, 1966. — С. 46 (теорема 41). — 384 с.
  4. Ленг С. Алгебра. М.: Мир, 1968. — С. 89—90. — 564 с.

Литература

Ссылки

`* Weisstein, Eric W. Euclid's Lemma (англ.) на сайте Wolfram MathWorld.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.