stringtranslate.com

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

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

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

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

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

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

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

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

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

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

По индукции

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

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

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

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

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

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

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

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

и тот же аргумент показывает, что na и a взаимно просты. Следовательно, 0 < a ( bq ) < ab , и предположение индукции подразумевает, что na делит bq ; то есть для некоторого целого числа. Итак, и, разделив на na , получаем Следовательно, и разделив на a , получаем желаемый результат.

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

Лемма Евклида доказана в предложении 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]
Предположим, что abmc .
Следовательно , c  : ab : m . [VII.19]
Следовательно [VII. 20, 21]bnc , где n — некоторое целое число.
Следовательно , c измеряет b .
Аналогично, если c не измеряет b , c измеряет a .
Следовательно, c измеряет одно или другое из двух чисел a , b .
ЧТЭ [18]

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

Сноски

Примечания

  1. ^ Ее также называют первой теоремой Евклида [1] [2], хотя это название более точно относится к условию «сторона-угол-сторона», показывающему, что треугольники равны . [ 3 ]
  2. ^ В общем случае, чтобы показать, что область является областью единственной факторизации , достаточно доказать лемму Евклида и условие обрыва возрастающей цепи главных идеалов .
  3. ^ Если abcd , то adbc ; и наоборот. [13]
  4. ^ Если abcd , и a , b являются наименьшими числами среди тех, которые имеют одинаковое отношение, то cna , dnb , где n — некоторое целое число. [14]
  5. ^ Если abcd , и 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. ^ Вайсштейн, Эрик В. «Лемма Евклида». MathWorld .
  12. ^ Харди, Райт и Уайлс 2008, §2.10
  13. Евклид 1956, стр. 319
  14. Евклид 1956, стр. 321
  15. Евклид 1956, стр. 323
  16. Евклид 1956, стр. 331
  17. Евклид 1956, стр. 332
  18. Евклид 1956, стр. 331−332

Ссылки

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