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

Простой делитель произведения делит один из множителей

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

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

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

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

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

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

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

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

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

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

Теорема  —  Если целое число 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, такие что

${\displaystyle rx+sy=1.}$

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

${\displaystyle rn+sa=1.}$

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

${\displaystyle rnb+sab=b.}$

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

По индукции

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

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

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

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

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

Если n < a , то имеем

${\displaystyle n(q-b)=(a-n)b.}$

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

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

${\displaystyle (n-a)q=a(b-q),}$

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

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

Лемма Евклида доказана в предложении 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. Ее также называют первой теоремой Евклида ^{[1] [2],} хотя это название более точно относится к условию «сторона-угол-сторона», показывающему, что треугольники равны . [ 3 ^]
2. В общем случае, чтобы показать, что область является областью единственной факторизации , достаточно доказать лемму Евклида и условие обрыва возрастающей цепи на главных идеалах .
3. Если a：b＝c：d , то ad＝bc ; и наоборот. ^[13]
4. Если a：b＝c：d , и a , b являются наименьшими числами среди тех, которые имеют одинаковое отношение, то c＝na , d＝nb , где n — некоторое целое число. ^[14]
5. Если a：b＝c：d , и a , b являются простыми числами друг для друга, то a , b являются наименьшими числами среди тех, которые имеют одинаковое отношение. ^[15]
6. Если a — простое число и не измеряет b , то a и b являются простыми по отношению друг к другу. ^[16]
7. Если c , простое число, измеряет ab , c измеряет либо a, либо b . ^[17]

Цитаты

1. Байнок 2013, Теорема 14.5
2. Джойнер, Кремински и Туриско 2004, Предложение 1.5.8, стр. 25
3. Мартин 2012, стр. 125
4. Гаусс 2001, стр. 14
5. Харди, Райт и Уайлс 2008, Теорема 3
6. Айрленд и Розен 2010, Предложение 1.1.1
7. Ландау 1999, Теорема 15
8. Ризель 1994, Теорема A2.1
9. Евклид 1994, стр. 338–339.
10. Гаусс 2001, Статья 19
11. Вайсштейн, Эрик В. «Лемма Евклида». Математический мир .
12. Харди, Райт и Уайлс 2008, §2.10
13. Евклид 1956, стр. 319
14. Евклид 1956, стр. 321
15. Евклид 1956, стр. 323
16. Евклид 1956, стр. 331
17. Евклид 1956, стр. 332
18. Евклид 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.

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

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