Лемма Евклида - Euclids lemma - Wikipedia

Не путать с Лемма Евклида о делении, Теорема евклида, или же Евклидов алгоритм.

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

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

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

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

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

Составы

Позволять ${\displaystyle p}$ быть простое число, и предположим ${\displaystyle p}$ делит произведение двух целых чисел ${\displaystyle a}$ и ${\displaystyle b}$. (В символах это написано ${\displaystyle p\mid ab}$. Его отрицание, ${\displaystyle p}$ не разделяет ${\displaystyle ab}$ написано ${\displaystyle p\nmid ab}$.) Потом ${\displaystyle p\mid a}$ или же ${\displaystyle p\mid b}$ (или оба). Эквивалент заявления:

• Если ${\displaystyle p\nmid a}$ и ${\displaystyle p\nmid b}$, тогда ${\displaystyle p\nmid ab}$.
• Если ${\displaystyle p\nmid a}$ и ${\displaystyle p\mid ab}$, тогда ${\displaystyle p\mid b}$.

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

Теорема — Если ${\displaystyle n\mid ab}$, и ${\displaystyle n}$ является относительно простой к ${\displaystyle a}$, тогда ${\displaystyle n\mid b}$.

Это обобщение, потому что если ${\displaystyle n}$ простое, либо

• ${\displaystyle n\mid a}$ или же
• ${\displaystyle n}$ относительно проста с ${\displaystyle a}$. В этой второй возможности ${\displaystyle n\nmid a}$ так ${\displaystyle n\mid b}$.

История

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

Обобщение леммы на целые числа появилось в Жан Престе учебник Nouveaux Elémens de Mathématiques в 1681 г.^[9]

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

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

Доказательство с использованием леммы Безу.

Обычное доказательство включает другую лемму, называемую Личность Безу.^[12] Это гласит, что если Икс и у находятся относительно простые целые числа (т.е. у них нет общих делителей, кроме 1 и -1) существуют целые числа р и s такой, что

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

Позволять а и п быть относительно простым, и предположим, что п|ab. По личности Безу, есть р и s изготовление

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

Умножьте обе стороны на б:

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

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

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

Лемма Евклида доказана в предложении 30 книги VII книги. Евклида Элементы. Исходное доказательство сложно понять как оно есть, поэтому мы цитируем комментарий из Евклид (1956, стр. 319-332).

Предложение 19.

Если четыре числа пропорциональны, число, полученное из первого и четвертого, равно числу, полученному из второго и третьего; и, если число, полученное из первого и четвертого, равно числу, полученному из второго и третьего, четыре числа пропорциональны.^{[заметка 3]}

Предложение 20.

Наименьшее количество тех, у кого такое же соотношение с ними, измеряет тех, у кого такое же соотношение, одинаковое количество раз - чем больше, тем больше и меньше, тем меньше.^{[примечание 4]}

Предложение 21.

Простые числа по отношению друг к другу - наименьшее из тех, которые имеют с ними одинаковое отношение.^{[примечание 5]}

Предложение 29.

Любое простое число является простым с любым числом, которое оно не измеряет.^{[примечание 6]}

Предложение 30.

Если два числа, умножая друг друга, дают одно и то же число, и любое простое число измеряет произведение, оно также измеряет одно из исходных чисел.^{[примечание 7]}

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

Если c, простое число, мера ab, c меры либо а или же б.
Предполагать c не измеряет а.
Следовательно c, а важны друг для друга. ［VII. 29 ］
Предполагать ab＝MC.
Следовательно c : а ＝ б : м. ［VII. 19 ］
Следовательно [VII. 20, 21 ］ б＝NC, куда п - некоторое целое число.
Следовательно c меры б.
Аналогично, если c не измеряет б, c меры а.
Следовательно c измеряет одно из двух чисел а, б.
Q.E.D.^[18]

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

• Личность Безу
• Евклидов алгоритм
• Основная теорема арифметики
• Неприводимый элемент
• Главный элемент
• простое число

Сноски

Примечания

1. Его еще называют Первая теорема Евклида^[1][2] хотя это имя более точно принадлежит боковой угол-сторона условие для демонстрации этого треугольники находятся конгруэнтный.^[3]
2. В общем, чтобы показать, что домен это уникальная область факторизации, достаточно доказать лемму Евклида и условие возрастающей цепи на главных идеалах (ACCP)
3. Если а ： б＝c ： d, тогда объявление＝до н.э; и наоборот.^[13]
4. Если а ： б＝c ： d, и а, б - наименьшие числа среди тех, у которых такое же соотношение, то c＝на, d＝nb, куда п - некоторое целое число.^[14]
5. Если а ： б＝c ： d, и а, б взаимно взаимовыгодны, тогда а, б - наименьшие числа среди тех, у которых такое же соотношение.^[15]
6. Если а простое и не измеряет б, тогда а, б важны друг для друга.^[16]
7. Если c, простое число, мера ab, c меры либо а или же б.^[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. Вайсштейн, Эрик В. «Лемма Евклида». MathWorld.
12. Харди, Райт и Уайлс, 2008 г., §2.10
13. Евклид 1956, п. 319
14. Евклид 1956, п. 321
15. Евклид 1956, п. 323
16. Евклид 1956, п. 331
17. Евклид 1956, п. 332
18. Евклид 1956, стр. 331−332

Рекомендации

• Байнок, Бела (2013), Приглашение к абстрактной математике, Тексты для бакалавриата по математике, Спрингер, ISBN  978-1-4614-6636-9.
• Евклид (1956), Тринадцать книг стихий, Vol. 2 (Книги III-IX), перевод Хит, Томас Литтл, Dover Publications, ISBN  978-0-486-60089-5- т. 2
• Евклид (1994), Les Éléments, перевод, комментарии и примечания (На французском), 2, перевод Vitrac, Bernard, стр. 338–339, ISBN  2-13-045568-9
• Гаусс, Карл Фридрих (2001), Disquisitiones Arithmeticae, переведено Кларком, Артур А. (Второе, исправленное изд.), Нью-Хейвен, Коннектикут: Издательство Йельского университета, ISBN  978-0-300-09473-2
• Гаусс, Карл Фридрих (1981), Untersuchungen uber hohere Arithmetik [Исследования по высшей арифметике], перевод Мазера, = Х. (Второе изд.), Нью-Йорк: Челси, ISBN  978-0-8284-0191-3
• Харди, Г. Х.; Райт, Э.М.; Уайлс, А. Дж. (2008-09-15), Введение в теорию чисел (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
• Мартин, Г. Э. (2012), Основы геометрии и неевклидовой плоскости, Тексты для бакалавриата по математике, Springer, ISBN  978-1-4612-5725-7.
• Ризель, Ганс (1994), Простые числа и компьютерные методы факторизации (2-е изд.), Бостон: Birkhäuser, ISBN  978-0-8176-3743-9.

внешняя ссылка

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