В теории чисел , лемма Евклида является лемма , которая фиксирует фундаментальное свойство простых чисел , а именно: [примечание 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] Он используется для определения простых элементов , обобщения простых чисел на произвольные коммутативные кольца . Лемма Евклида показывает, что в целых числах неприводимые элементы также являются простыми элементами. Доказательство использует индукцию, поэтому оно не применимо ко всем областям целостности .
Составы
Позволять быть простым числом , и предположим делит произведение двух целых чисел а также . В символах это написано. Его отрицание, не делит , написано . потом или же (или оба). Эквивалентные утверждения:
- Если а также , тогда .
- Если а также , тогда .
Лемму Евклида можно обобщить с простых чисел на любые целые:
Теорема - Если, а также является взаимно простым с, тогда .
Это обобщение, потому что если простое, либо
- или же
- относительно проста с . В этой второй возможности так .
История
Эта лемма впервые появляется как предложение 30 в VII книге « Элементов » Евклида . Он включен практически во все книги, посвященные элементарной теории чисел. [4] [5] [6] [7] [8]
Обобщение леммы на целые числа появилось в учебнике Жана Престе « Nouveaux Elémens de Mathématiques» в 1681 году [9].
В трактате Карла Фридриха Гаусса Disquisitiones Arithmeticae утверждение леммы представляет собой предложение Евклида 14 (раздел 2), которое он использует для доказательства единственности произведения разложения простых множителей целого числа (теорема 16), признавая существование как "очевидный". Затем из этого существования и уникальности он выводит обобщение простых чисел на целые. [10] По этой причине обобщение леммы Евклида иногда называют леммой Гаусса, но некоторые считают, что это использование неверно [11] из-за путаницы с леммой Гаусса о квадратичных вычетах .
Доказательство
Подтверждение личности Безу
В современной математике обычное доказательство включает результат, называемый тождеством Безу , который был неизвестен во времена Евклида. [12] Тождество Безу гласит, что если 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 и a взаимно просты, поскольку, если p делит оба, то делит их сумму и, таким образом, делит как n, так и a . Итак, вывод следует из предположения индукции.
Если n > a , то
Как и выше, n - a и a взаимно просты. По предположению индукции существует такое целое число r , что Так
и можно получить q = ar , разделив на n - a . Таким образоми делением на a получаем 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 .
QED [18]
Смотрите также
- Личность Безу
- Евклидов алгоритм
- Основная теорема арифметики
- Неприводимый элемент
- Главный элемент
- простое число
Сноски
Заметки
- ^ Это также называется первая теорема Евклида [1] [2] , хотя это название более правильно относится к условию бокового угла стороны , показывающимчто треугольники являются конгруэнтны . [3]
- ^ В общем, чтобы показать, что область является единственной областью факторизации , достаточно доказать лемму Евклида и условие возрастающей цепи на главных идеалах (ACCP)
- ^ Если a: b= c: d , то ad= bc ; и наоборот. [13]
- ^ Если a: b= c: d , а a , b - наименьшие числа среди тех, которые имеют такое же отношение, то c= na , d= nb , где n - некоторое целое число. [14]
- ^ Если a: b= c: d и a , b просты друг с другом, то a , b - наименьшие числа среди тех, которые имеют такое же отношение. [15]
- ^ Если a простое число и не измеряет b , то a , b взаимно просты. [16]
- ^ Если c , простое число, мера ab , c измеряет либо a, либо b . [17]
Цитаты
- ^ Байнок 2013 , теорема 14.5
- ^ Джойнер, Kreminski & Turisco 2004 , предложение 1.5.8, стр. 25
- ^ Мартин 2012 , стр. 125
- Перейти ↑ Gauss 2001 , p. 14
- ^ Харди, Райт и Уайлс 2008 , теорема 3
- ^ Ирландия и Розен 2010 , Предложение 1.1.1
- ^ Ландау и Гудман 1999 , теорема 15
- ^ Ризель 1994 , теорема A2.1
- Перейти ↑ Euclid 1994 , pp. 338–339
- ^ Гаусс 2001 , статья 19
- ^ Вайсштейн, Эрик В. "Лемма Евклида" . MathWorld .
- ^ Харди, Райт и Уайлс 2008 , §2.10
- ^ Евклид 1956 , стр. 319
- ^ Евклид 1956 , стр. 321
- ^ Евклид 1956 , стр. 323
- ^ Евклид 1956 , стр. 331
- ^ Евклид 1956 , стр. 332
- ↑ Евклид, 1956 , стр. 331−332.
Рекомендации
- Байнок, Бела (2013), Приглашение к абстрактной математике , Тексты для студентов по математике , Springer, ISBN 978-1-4614-6636-9.
- Евклид (1956), Тринадцать книг стихий , т. 2 (Книги III-IX), переведенные Хитом, Томасом Литтлом , Dover Publications, ISBN 978-0-486-60089-5
|volume=
есть дополнительный текст ( справка )CS1 maint: обескураженный параметр ( ссылка )- т. 2 - Евклид (1994), Les Éléments, traduction, commentaires et notes (на французском), 2 , переведено Vitrac, Bernard, стр. 338–339, ISBN 2-13-045568-9 CS1 maint: обескураженный параметр ( ссылка )
- Гаусс, Карл Фридрих (2001), Disquisitiones Arithmeticae , переведенный Кларком, Артуром А. (Второе, исправленное изд.), Нью-Хейвен, Коннектикут: Yale University Press, ISBN 978-0-300-09473-2
- Гаусс, Карл Фридрих (1981), Untersuchungen uber hohere Arithmetik [ Исследования по высшей арифметике ], перевод Мазера, = Х. (Второе изд.), Нью-Йорк: Челси, ISBN 978-0-8284-0191-3
- Харди, GH ; Райт, EM ; Уайлс, AJ (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
- Мартин, GE (2012), Основы геометрии и неевклидовой плоскости , Тексты для студентов по математике, Springer, ISBN 978-1-4612-5725-7.
- Ризель, Ханс (1994), Простые числа и компьютерные методы факторизации (2-е изд.), Бостон: Birkhäuser, ISBN 978-0-8176-3743-9.
Внешние ссылки
- Вайсштейн, Эрик В. «Лемма Евклида» . MathWorld .