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

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

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

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

Пример. 19 — простое число, и оно делит $19019=133\cdot 143.$ Следовательно, один из сомножителей делится на 19, а именно: $133=19\cdot 7.$

Если $p$ — не простое число, то теорема может не выполняться. Пример: $4\cdot 15=60$ делится на 20, однако ни один из сомножителей на 20 не делится.

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

Пусть $x\cdot y$ делится на $p$ , но $x$ не делится на $p$ . Тогда $x$ и $p$ — взаимно простые, следовательно, найдутся целые числа $u$ и $v$ такие, что

x\cdot u+p\cdot v=1

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

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

(x\cdot y)\cdot u+p\cdot v\cdot y=y.

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

Обобщения

Если произведение $bc$ делится на $a$ и $a,b$ взаимно просты, то^[3] $c$ делится на $a.$

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

Кольцо целых гауссовых чисел $\mathbb {Z} [i].$
Кольцо многочленов от одной переменной $K[x]$ над полем $K.$

Примечания

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

Литература

Виноградов И. М. Основы теории чисел. — М.—Л.: ГИТТЛ, 1952. — 180 с.
Жиков В.В. Основная теорема арифметики // Соросовский Образовательный Журнал. — 2000. — Т. 6, № 3. — С. 112—117.

Ссылки

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

Похожие исследовательские статьи

<span class="mw-page-title-main">Простое число</span> натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя

Просто́е число́ — натуральное число, имеющее ровно два различных натуральных делителя. Другими словами, натуральное число $\text{[math]}$ является простым, если оно отлично от $\text{[math]}$ и делится без остатка только на $\text{[math]}$ и на само $\text{[math]}$ .

<span class="mw-page-title-main">Арифметика</span> раздел математики, изучающий числа, их отношения и свойства

Арифме́тика — раздел математики, изучающий числа, их отношения и свойства. Предметом арифметики является понятие числа и его свойства. В арифметике рассматриваются измерения, вычислительные операции и приёмы вычислений. Изучением свойств отдельных целых чисел занимается высшая арифметика, или теория чисел. Теоретическая арифметика уделяет внимание определению и анализу понятия числа, в то время как формальная арифметика оперирует логическими построениями предикатов и аксиом. Арифметика является древнейшей и одной из основных математических наук; она тесно связана с алгеброй, геометрией и теорией чисел.

Теория чисел или высшая арифметика — раздел математики, первоначально изучавший свойства целых чисел. В современной теории чисел рассматриваются и другие типы чисел — например, алгебраические и трансцендентные, а также функции различного происхождения, которые связаны с арифметикой целых чисел и их обобщений.

Основная теорема арифметики утверждает, что каждое натуральное число $\text{[math]}$ можно факторизовать (разложить) на простые множители, то есть записать в виде $\text{[math]}$ , где $\text{[math]}$ — простые числа, причём такое представление единственно, если не учитывать порядок следования множителей.

Ма́лая теоре́ма Ферма́ — теорема теории чисел, которая утверждает, что:

Если $\text{[math]}$ — простое число и $\text{[math]}$ — целое число, не делящееся на $\text{[math]}$ то $\text{[math]}$ делится на $\text{[math]}$

Сравне́ние двух целых чисел по мо́дулю натурального числа $\text{[math]}$ — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на $\text{[math]}$ один и тот же остаток. Любое целое число при делении на $\text{[math]}$ даёт один из $\text{[math]}$ возможных остатков: число от 0 до $\text{[math]}$ ; это значит, что все целые числа можно разделить на $\text{[math]}$ групп, каждая из которых отвечает определённому остатку от деления на $\text{[math]}$ . Эти группы называются классами вычетов по модулю $\text{[math]}$ , а содержащиеся в них целые числа — вычетами по модулю $\text{[math]}$ .

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел. Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII и X книгах «Начал». Это один из старейших численных алгоритмов, используемых в наше время.

Наибольшим общим делителем (НОД) для двух целых чисел $\text{[math]}$ и $\text{[math]}$ называется наибольший из их общих делителей. Пример: для чисел 54 и 24 наибольший общий делитель равен 6.

Многочле́н — фундаментальное понятие в алгебре и математическом анализе. В простейшем случае многочленом называется функция вещественной или комплексной переменной $\text{[math]}$ следующего вида:

\text{[math]}

, где

\text{[math]}

— фиксированные коэффициенты.

Китайская теорема об остатках — несколько связанных утверждений о решении линейной системы сравнений.

<span class="mw-page-title-main">Функция Эйлера</span> мультипликативная арифметическая функция

Фу́нкция Э́йлера $\text{[math]}$ — мультипликативная арифметическая функция, значение которой равно количеству натуральных чисел, меньших либо равных $\text{[math]}$ и взаимно простых с ним.

<span class="mw-page-title-main">Взаимно простые числа</span> числа, не имеющие общего делителя

Взаимно простые числа — целые числа, не имеющие никаких общих делителей, кроме ±1. Равносильное определение: целые числа взаимно просты, если их наибольший общий делитель (НОД) равен 1.

Мультипликативная группа кольца вычетов по модулю m — мультипликативная группа обратимых элементов кольца вычетов по модулю m. При этом в качестве множества элементов может рассматриваться любая приведенная система вычетов по модулю m.

Соотноше́ние Безу́ — представление наибольшего общего делителя целых чисел в виде их линейной комбинации с целыми коэффициентами.

Га́уссовы це́лые чи́сла — это комплексные числа, у которых как вещественная, так и мнимая часть — целые числа.

Факториа́льное кольцо́ — область целостности, в которой каждый ненулевой элемент x либо обратим, либо однозначно представляется в виде произведения неприводимых элементов x = p₁ ⋯ p_n (n ≥ 1), с точностью до перестановки сомножителей и умножения на обратимый элемент (аналогично разложению целого числа на простые). Факториальные кольца часто называются гауссовыми в честь Гаусса.

Расширенный алгоритм Евклида — модификация алгоритма Евклида, вычисляющая, кроме наибольшего общего делителя (НОД) целых чисел $\text{[math]}$ и $\text{[math]}$ , ещё и коэффициенты соотношения Безу, то есть такие целые $\text{[math]}$ и $\text{[math]}$ , что

Теорема Евклида — основной элемент теории чисел. Она утверждает, что для любого конечного списка простых чисел найдётся простое число, не вошедшее в этот список.

<span class="mw-page-title-main">Арифметические исследования (Гаусс)</span> Монография Гаусса по теории чисел, 1801 г.

«Арифметические исследования» — первый крупный труд 24-летнего немецкого математика Карла Фридриха Гаусса, опубликованный в Лейпциге в сентябре 1801 года. Эта монография стала ключевым этапом в развитии теории чисел; она содержала как обстоятельное изложение результатов предшественников, так и собственные глубокие результаты Гаусса. Среди последних особенную важность представляли:

Квадратичный закон взаимности, основа теории квадратичных вычетов. Гаусс впервые дал его доказательство.
Теория композиции классов и родов квадратичных форм, ставшая важнейшим вкладом в создание теории алгебраических чисел.
Теория деления круга. Это не только пример приложения общих методов, но и, как далее выяснилось, прообраз на частном примере открытой в 1830-х годах общей теории Галуа.

Квадрати́чная иррациона́льность — иррациональное число, которое является вещественным корнем некоторого квадратного уравнения $\text{[math]}$ с рациональными коэффициентами $\text{[math]}$ . В части источников под квадратичными иррациональностями понимаются в общем случае комплексные корни указанных уравнений.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.