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

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

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

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

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

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

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

Формулировки

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

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

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

Теорема — Если целое число $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 | ab$ . По тождеству Безу существуют $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$ , то имеем

n(qb)=(an)b.

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

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

(na)q=a(bq),

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

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

Лемма Евклида доказана в предложении 30 в книге VII «Начал» Евклида . Оригинальное доказательство трудно понять в таком виде, поэтому мы цитируем комментарий Евклида (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
^ Вайсштейн, Эрик В. «Лемма Евклида». MathWorld .
^ Харди, Райт и Уайлс 2008, §2.10
↑ Евклид 1956, стр. 319
↑ Евклид 1956, стр. 321
↑ Евклид 1956, стр. 323
↑ Евклид 1956, стр. 331
↑ Евклид 1956, стр. 332
↑ Евклид 1956, стр. 331−332

Ссылки

Байнок, Бела (2013), Приглашение к абстрактной математике, Бакалаврские тексты по математике , Springer, ISBN 978-1-4614-6636-9.
Евклид (1956), Тринадцать книг «Начал» , т. 2 (книги III–IX), перевод Хита, Томаса Литтла , Dover Publications, ISBN 978-0-486-60089-5- т. 2
Евклид (1994), Les Éléments, перевод, комментарии и примечания (на французском языке), vol. 2, перевод Витрака, Бернарда, стр. 338–339, ISBN. 2-13-045568-9
Гаусс, Карл Фридрих (2001), Disquisitiones Arithmeticae , перевод Кларка, Артура А. (Второе, исправленное издание), Нью-Хейвен, Коннектикут: Yale University Press, ISBN 978-0-300-09473-2
Гаусс, Карл Фридрих (1981), Untersuchungen uber hohere Arithmetik [ Исследования по высшей арифметике ], перевод Мазера Х. (второе изд.), Нью-Йорк: Челси, ISBN 978-0-8284-0191-3
Харди, Г. Х.; Райт , Э. М.; Уайлс , А. Дж. (15 сентября 2008 г.), Введение в теорию чисел (6-е изд.), Оксфорд: Oxford University Press , ISBN 978-0-19-921986-5
Айрленд, Кеннет; Розен, Майкл (2010), Классическое введение в современную теорию чисел (второе издание), Нью-Йорк: Springer , ISBN 978-1-4419-3094-1
Джойнер, Дэвид; Креминский, Ричард; Туриско, Джоанн (2004), Прикладная абстрактная алгебра, JHU Press, ISBN 978-0-8018-7822-0.
Ландау, Эдмунд (1999), Элементарная теория чисел , перевод Гудмана, Дж. Э. (2-е изд.), Провиденс, Род-Айленд: Американское математическое общество, ISBN 978-0-821-82004-9
Мартин, GE (2012), Основы геометрии и неевклидова плоскость, Бакалаврские тексты по математике, Springer, ISBN 978-1-4612-5725-7.
Ризель, Ганс (1994), Простые числа и компьютерные методы факторизации (2-е изд.), Бостон: Birkhäuser, ISBN 978-0-8176-3743-9.

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

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