Лемма Евклида - Euclid's lemma

В теории чисел , лемма Евклида является лемма , которая фиксирует фундаментальное свойство простых чисел , а именно:

Лемма Евклида  -  если простое число 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.

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

Составы

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

  • Если и , то .
  • Если и , то .

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

Теорема  -  Если и является взаимно простым с , то .

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

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

История

Эта лемма впервые появляется как предложение 30 в VII книге « Элементов » Евклида . Он включен практически во все книги, посвященные элементарной теории чисел.

Обобщение леммы на целых появилась в Жан Prestet учебнику «s Nouveaux Elémens де Mathématiques в 1681.

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

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

Доказательство личности Безу

В современной математике обычное доказательство включает результат, называемый тождеством Безу , который был неизвестен во времена Евклида. Тождество Безу утверждает, что если x и y являются относительно простыми целыми числами (т. Е. У них нет общих делителей, кроме 1 и -1), существуют целые числа r и s такие, что

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

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

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

Прямое доказательство

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

Предположим, что и . Мы хотим это показать . Поскольку существует n взаимно простых с a ( т. Е. Их единственные общие делители - 1 и –1 ) такие, что

Нужно доказать, что n делит b . Чтобы доказать это с помощью сильной индукции , предположим, что это доказано для всех положительных нижних значений ab .

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

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

Если n < a , то

Положительные целые числа a - n и n взаимно просты: если любое простое число делит оба, то оно делит их сумму и, таким образом, делит как n, так и a . Это противоречие гипотезе взаимной примитивности. Как следствие правой стороны , д - б положителен. Итак, вывод следует из предположения индукции, поскольку a - n < a .

Если n > a , то

Как и выше, n - a и a взаимно просты. Поскольку b - q < b , по предположению индукции существует такое целое число r , что So

и можно получить q = ar , разделив на n - a . Таким образом , делением на a получаем b = nr , что и является желаемым выводом.

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

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

Предложение 19.
Если четыре числа пропорциональны, число, полученное из первого и четвертого, равно числу, полученному из второго и третьего; и, если число, полученное из первого и четвертого, равно числу, полученному из второго и третьего, четыре числа пропорциональны.
Предложение 20.
Наименьшее количество тех, у кого такое же соотношение с ними, измеряет количество тех, у кого такое же соотношение, одинаковое количество раз - чем больше, тем больше и меньше, тем меньше.
Предложение 21.
Простые числа по отношению друг к другу - это наименьшее из тех, которые имеют с ними одинаковое отношение.
Предложение 29.
Любое простое число является простым с любым числом, которое оно не измеряет.
Предложение 30.
Если два числа, умножая одно на другое, дают одно и то же число, и любое простое число измеряет произведение, оно также измеряет одно из исходных чисел.
Доказательство 30
Если c , простое число, мера ab , c измеряет либо a, либо b .
Предположим, что c не измеряет a .
Следовательно, c , a взаимно просты.VII. 29
Предположим, что abmc .
Следовательно, c  : ab : m . VII. 19
Отсюда VII. 20 , 21bnc , где n - некоторое целое число.
Следовательно, c измеряет b .
Аналогично, если c не измеряет b , c измеряет a .
Следовательно, c измеряет одно из двух чисел a , b .
QED

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

Сноски

Примечания

Цитаты

использованная литература

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