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

В алгебре и теории чисел лемма Евклида — это лемма , которая отражает фундаментальное свойство простых чисел : ^{[примечание 1]}

Лемма Евклида . Если простое число $p$ делит произведение $ab$ двух целых чисел $a$ и $b$ , то $p$ должно делить хотя бы одно из этих целых чисел $a$ или $b$ .

Например, если $p = 19$ , $a = 133$ , $b = 143$ , то $ab = 133 \times 143 = 19019$ , и поскольку оно делится на 19, из леммы следует, что одно или оба из 133 или 143 также должны быть кратными. Фактически $133 = 19\times7$ .

Лемма впервые появилась в «Началах » Евклида и является фундаментальным результатом элементарной теории чисел.

Если посылка леммы не выполняется, то есть если $p$ — составное число , его консеквент может быть либо истинным, либо ложным. Например, в случае $p = 10$ , $a = 4$ , $b = 15$ составное число 10 делит $ab = 4 \times 15 = 60$ , но 10 не делит ни 4, ни 15.

Это свойство является ключевым в доказательстве основной теоремы арифметики . ^{[примечание 2]} Он используется для определения простых элементов , что является обобщением простых чисел на произвольные коммутативные кольца . Лемма Евклида показывает, что в целых числах неприводимые элементы также являются простыми элементами. В доказательстве используется индукция , поэтому оно не применимо ко всем областям целостности .

Составы

Лемма Евклида обычно используется в следующей эквивалентной форме:

Теорема . Если — простое число, которое делит произведение и не делится, то оно делит. ${\ displaystyle p}$ $аб$ $а,$ $б.$

Лемму Евклида можно обобщить с простых чисел на любые целые числа следующим образом.

Теорема . Если целое число $n$ делит произведение $ab$ двух целых чисел и взаимно просто с $a$ , то $n$ делит $b$ .

Это обобщение, поскольку простое число $p$ взаимно просто с целым числом $a$ тогда и только тогда, когда $p$ не делит $a$ .

История

Лемма впервые появляется как предложение 30 в книге VII « Начал » Евклида . Он включен практически в каждую книгу, посвященную элементарной теории чисел. ^[4]^[5]^[6]^[7]^[8]

Обобщение леммы на целые числа появилось в учебнике Жана Престе «Новые элементы математики» в 1681 году. ^[9]

В трактате Карла Фридриха Гаусса Disquisitiones Arithmeticae формулировкой леммы является предложение Евклида 14 (раздел 2), которое он использует для доказательства единственности продукта разложения простых множителей целого числа (теорема 16), допуская существование как "очевидный". Из этого существования и единственности он затем выводит обобщение простых чисел на целые. ^[10] По этой причине обобщение леммы Евклида иногда называют леммой Гаусса, но некоторые считают, что это использование неверно ^[11] из-за путаницы с леммой Гаусса о квадратичных вычетах .

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

Два первых подраздела являются доказательством обобщенной версии леммы Евклида, а именно: если $n$ делит $ab$ и взаимно просто с $a$ , то оно делит $b$ .

Исходная лемма Евклида следует немедленно, поскольку, если $n$ простое, то оно делит $a$ или не делит $a,$ и в этом случае оно взаимно просто с $a$ , поэтому в обобщенной версии оно делит $b$ .

Использование личности Безу

В современной математике обычное доказательство включает тождество Безу , которое было неизвестно во времена Евклида. ^[12] Тождество Безу гласит, что если $x$ и $y$ являются взаимно простыми целыми числами (т.е. у них нет общих делителей, кроме 1 и -1), существуют целые числа $r$ и $s$ такие, что

rx+sy=1.

Пусть $a$ и $n$ взаимно просты и предположим, что $n | аб$ . По тождеству Безу существуют $r$ и $s$ такие, что

rn+sa=1.

Умножьте обе части на $b$ :

rnb+sab=b.

Первый член слева делится на $n$ , а второй член делится на $ab$ , который по условию делится на $n$ . Следовательно, их сумма $b$ также делится на $n$ .

По индукции

Следующее доказательство основано на версии алгоритма Евклида Евклида , которая использует только вычитания.

Предположим, что и что $n$ и $a$ взаимно просты ( т. е. их наибольший общий делитель равен $1$ ). Нужно доказать, что $n$ делит $b$ . Поскольку существует целое число $q$ такое , что Без ограничения общности можно предположить, что $n$ , $q$ , $a$ и $b$ положительны, поскольку отношение делимости не зависит от знаков задействованных целых чисел. $n\mid ab$ $n\mid ab,$ $nq=ab.$

Для доказательства этого методом сильной индукции предположим, что результат доказан для всех положительных нижних значений $ab$ .

Есть три случая:

Если $n = a$ , из взаимной простоты следует $n = 1$ , и $n$ делит $b$ тривиально.

Если $n < a$ , имеется

{\ displaystyle n (qb) = (an) b.}

Целые положительные числа $a - n$ и $n$ взаимно просты: их наибольший общий делитель $d$ должен делить их сумму и, таким образом, делит и $n$ , и $a$ . В результате по гипотезе взаимной простоты $d = 1$ . Итак, вывод следует из предположения индукции, поскольку $0 < (a - n) b < ab$ .

Аналогично, если $n > a$ , то

{\ displaystyle (na) q = a (bq),}

и тот же аргумент показывает, что $n - a$ и $a$ взаимно просты. Следовательно, имеем $0 < a (b - q) < ab$ , и из предположения индукции следует, что $n - a$ делит $b - q$ ; то есть для некоторого целого числа. Итак , разделив на $n$ $-$ $a$ , получим Следовательно, а разделив на $a$ , получим желаемый результат. $bq=r (na)$ ${\ displaystyle (na) q = ar (na),}$ $q=ar.$ $ab=nq=anr,$ $b=nr,$

ДоказательстваЭлементы

Лемма Евклида доказывается в предложении 30 седьмой книги « Начал » Евклида . Первоначальное доказательство трудно понять как таковое, поэтому мы цитируем комментарий Евклида (1956, стр. 319–332).

Предложение 19: Если четыре числа пропорциональны, то число, полученное из первого и четвертого, равно числу, полученному из второго и третьего; и если число, полученное из первого и четвертого, равно числу, полученному из второго и третьего, то эти четыре числа пропорциональны. ^{[заметка 3]}
Предложение 20: Наименьшее число тех, которые имеют одинаковое соотношение с ними, измеряет тех, у которых такое же соотношение, одинаковое число раз — чем больше, тем больше, и чем меньше, тем меньше. ^{[примечание 4]}
Предложение 21: Числа, простые друг другу, являются наименьшими из тех, которые имеют с ними одинаковое соотношение. ^{[примечание 5]}
Предложение 29: Любое простое число является простым с любым числом, которое оно не измеряет. ^{[примечание 6]}
Предложение 30: Если два числа, умножив друг друга, образуют одно и то же число, и любое простое число измеряет произведение, оно также измеряет одно из исходных чисел. ^{[примечание 7]}
Доказательство 30: Если c , простое число, измеряет ab , c измеряет либо a , либо b .
Предположим, что c не измеряет a .
Следовательно, c , a просты друг с другом.［VII. 29］
Предположим, ab＝mc .
Следовательно, c : a＝b : m . ［VII. 19］
Следовательно, ［VII. 20, 21］b＝nc , где n — некоторое целое число.
Следовательно, c измеряет b .
Аналогично, если c не измеряет b , c измеряет a .
Следовательно, c измеряет то или иное из двух чисел a , b .
КЭД ^[18]

Смотрите также

Сноски

Примечания

^ Ее также называют первой теоремой Евклида ^[1]^[2] , хотя это название более точно относится к условию сторона-угол-сторона, показывающему, что треугольники конгруэнтны . ^[3]
^ В общем, чтобы показать, что область является уникальной областью факторизации , достаточно доказать лемму Евклида и условие восходящей цепи на главных идеалах .
^ Если a : b＝c : d , то ad＝bc ; и наоборот. ^[13]
^ Если a : b＝c : d и a , b — наименьшие числа среди тех, которые имеют одинаковое соотношение, то c＝na , d＝nb , где n — некоторое целое число. ^[14]
^ Если a : b＝c : d и a , b простые друг другу, то a , b — наименьшие числа среди тех, которые имеют одинаковое соотношение. ^[15]
^ Если a является простым и не измеряет b , то a , b просты друг с другом. ^[16]
^ Если c , простое число, измерьте ab , c измеряет либо a , либо b . ^[17]

Цитаты

^ Байнок 2013, Теорема 14.5.
^ Джойнер, Кремински и Туриско 2004, Предложение 1.5.8, с. 25
^ Мартин 2012, с. 125
^ Гаусс 2001, с. 14
^ Харди, Райт и Уайлс 2008, Теорема 3
^ Ирландия и Розен, 2010, Предложение 1.1.1.
^ Ландау 1999, Теорема 15.
^ Ризель 1994, Теорема A2.1
^ Евклид 1994, стр. 338–339.
^ Гаусс 2001, статья 19.
^ Вайсштейн, Эрик В. «Лемма Евклида». Математический мир .
^ Харди, Райт и Уайлс 2008, §2.10
^ Евклид 1956, с. 319
^ Евклид 1956, с. 321
^ Евклид 1956, с. 323
^ Евклид 1956, с. 331
^ Евклид 1956, с. 332
^ Евклид 1956, стр. 331–332.

Внешние ссылки

Вайсштейн, Эрик В. «Лемма Евклида». Математический мир .