Лемма Евклида - 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] Он используется для определения основные элементы, обобщение простых чисел на произвольные коммутативные кольца. Лемма Евклида показывает, что в целых числах неприводимые элементы также простые элементы. Доказательство использует индукция так что это не относится ко всем целостные области.

Составы

Позволять быть простое число, и предположим делит произведение двух целых чисел и . (В символах это написано . Его отрицание, не разделяет написано .) Потом или же (или оба). Эквивалент заявления:

  • Если и , тогда .
  • Если и , тогда .

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

Теорема — Если , и является относительно простой к , тогда .

Это обобщение, потому что если простое, либо

  • или же
  • относительно проста с . В этой второй возможности так .

История

Лемма впервые появляется как предложение 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 такой, что

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

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

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

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

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

Предложение 19.
Если четыре числа пропорциональны, число, полученное из первого и четвертого, равно числу, полученному из второго и третьего; и, если число, полученное из первого и четвертого, равно числу, полученному из второго и третьего, четыре числа пропорциональны.[заметка 3]
Предложение 20.
Наименьшее количество тех, у кого такое же соотношение с ними, измеряет тех, у кого такое же соотношение, одинаковое количество раз - чем больше, тем больше и меньше, тем меньше.[примечание 4]
Предложение 21.
Простые числа по отношению друг к другу - наименьшее из тех, которые имеют с ними одинаковое отношение.[примечание 5]
Предложение 29.
Любое простое число является простым с любым числом, которое оно не измеряет.[примечание 6]
Предложение 30.
Если два числа, умножая друг друга, дают одно и то же число, и любое простое число измеряет произведение, оно также измеряет одно из исходных чисел.[примечание 7]
Доказательство 30
Если c, простое число, мера ab, c меры либо а или же б.
Предполагать c не измеряет а.
Следовательно c, а важны друг для друга. VII. 29
Предполагать abMC.
Следовательно c : аб : м. VII. 19
Следовательно [VII. 20, 21бNC, куда п - некоторое целое число.
Следовательно c меры б.
Аналогично, если c не измеряет б, c меры а.
Следовательно c измеряет одно из двух чисел а, б.
Q.E.D.[18]

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

Сноски

Примечания

  1. ^ Его еще называют Первая теорема Евклида[1][2] хотя это имя более точно принадлежит боковой угол-сторона условие для демонстрации этого треугольники находятся конгруэнтный.[3]
  2. ^ В общем, чтобы показать, что домен это уникальная область факторизации, достаточно доказать лемму Евклида и условие возрастающей цепи на главных идеалах (ACCP)
  3. ^ Если абcd, тогда объявлениедо н.э; и наоборот.[13]
  4. ^ Если абcd, и а, б - наименьшие числа среди тех, у которых такое же соотношение, то cна, dnb, куда п - некоторое целое число.[14]
  5. ^ Если абcd, и а, б взаимно взаимовыгодны, тогда а, б - наименьшие числа среди тех, у которых такое же соотношение.[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

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

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