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

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

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

Например, если $p = 19$ , $a = 133$ , $b = 143$ , то $ab = 133 \times 143 = 19019$ , и поскольку оно делится на 19, из леммы следует, что одно или оба из 133 или 143 также должны делиться. Фактически $133 = 19\times7$ .

Лемма впервые появилась в и » Евклида «Началах является фундаментальным результатом элементарной теории чисел.

Если посылка леммы не выполняется, то есть если $p$ — составное число , его консеквент может быть либо истинным, либо ложным. Например, в случае $p = 10$ , $a = 4$ , $b = 15$ составное число 10 делит $ab = 4 \times 15 = 60$ , но 10 не делит ни 4, ни 15.

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

Составы

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

Теорема — Если $p$ простое число, которое делит произведение $ab$ и не делит $a,$ тогда он делится $b.$

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

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

rx+sy=1.

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

rn+sa=1.

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

rnb+sab=b.

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

По индукции

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

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

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

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

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

Если $n < a$ , имеется

n(q-b)=(a-n)b.

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

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

(n-a)q=a(b-q),

и тот же аргумент показывает, что $n - a$ и $a$ взаимно просты. Следовательно, имеем $0 < a (b - q) < ab$ , и из предположения индукции следует, что $n - a$ делит $b - q$ ; то есть, $b-q=r(n-a)$ для некоторого целого числа. Так, $(n-a)q=ar(n-a),$ и, разделив на $n - a$ , получим $q=ar.$ Поэтому, $ab=nq=anr,$ и, разделив на $,$ получим $b=nr,$ желаемый результат.

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

Лемма Евклида доказывается в предложении 30 седьмой книги « Евклида Начал» . Первоначальное доказательство трудно понять само по себе, поэтому мы цитируем комментарий Евклида (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 .
КЭД ^{[ 18 ]}

См. также

Сноски

Примечания

^ Ее также называют первой теоремой Евклида. ^{[ 1 ]}^{[ 2 ]} хотя это название скорее принадлежит условию сторона-угол-сторона, показывающему, треугольники конгруэнтны что . ^{[ 3 ]}
^ В общем, чтобы показать, что область является уникальной областью факторизации , достаточно доказать лемму Евклида и условие восходящей цепи на главных идеалах .
^ Если 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
^ Джойнер, Кремински и Туриско 2004 , Предложение 1.5.8, с. 25
^ Мартин 2012 , с. 125
^ Гаусс 2001 , с. 14
^ Харди, Райт и Уайлс 2008 , Теорема 3
^ Ирландия и Розен 2010 , Предложение 1.1.1.
^ Ландау 1999 , Теорема 15.
^ Ризель 1994 , Теорема A2.1
^ Евклид 1994 , стр. 338–339.
^ Гаусс 2001 , статья 19.
^ Вайсштейн, Эрик В. «Лемма Евклида» . Математический мир .
^ Харди, Райт и Уайлс 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 - об. 2
Евклид (1994), Элементы, перевод, комментарии и примечания (на французском языке), том. 2, перевод Витрака Бернарда, стр. 338–339, ISBN 2-13-045568-9
Гаусс, Карл Фридрих (2001), Disquisitiones Arithmeticae , перевод Кларка, Артура А. (второе, исправленное издание), Нью-Хейвен, Коннектикут: Издательство Йельского университета, ISBN 978-0-300-09473-2
Гаусс, Карл Фридрих (1981), по высшей арифметике , Исследования перевод Мазера Х. (второе изд.), Нью-Йорк: Челси, ISBN 978-0-8284-0191-3
Харди, штат Джорджия ; Райт, Э.М .; Уайлс, AJ (15 сентября 2008 г.), Введение в теорию чисел (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 .

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

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

[4] Ее также называют первой теоремой Евклида. ^{[ 1 ]}^{[ 2 ]} хотя это название скорее принадлежит условию сторона-угол-сторона, показывающему, треугольники конгруэнтны что . ^{[ 3 ]}

[5] В общем, чтобы показать, что область является уникальной областью факторизации , достаточно доказать лемму Евклида и условие восходящей цепи на главных идеалах .

[16] Если a : b ＝ c : d , то ad ＝ bc ; и наоборот. ^{[ 13 ]}

[18] Если a : b ＝ c : d и a , b — наименьшие числа среди тех, которые имеют одинаковое соотношение, то c ＝ na , d ＝ nb , где n — некоторое целое число. ^{[ 14 ]}

[20] Если a : b ＝ c : d и a , b простые друг другу, то a , b — наименьшие числа среди тех, которые имеют одинаковое соотношение. ^{[ 15 ]}

[22] Если a является простым и не измеряет b , то a , b просты друг с другом. ^{[ 16 ]}

[24] Если c , простое число, измерьте ab , c измеряет либо a , либо b . ^{[ 17 ]}

[1] Чемпион 2013 , Теорема 14.5

[2] Джойнер, Кремински и Туриско 2004 , Предложение 1.5.8, с. 25

[3] Мартин 2012 , с. 125

[DA1-6] Гаусс 2001 , с. 14

[7] Харди, Райт и Уайлс 2008 , Теорема 3

[8] Ирландия и Розен 2010 , Предложение 1.1.1.

[9] Ландау 1999 , Теорема 15.

[10] Ризель 1994 , Теорема A2.1

[11] Евклид 1994 , стр. 338–339.

[DA2-12] Гаусс 2001 , статья 19.

[13] Вайсштейн, Эрик В. «Лемма Евклида» . Математический мир .

[14] Харди, Райт и Уайлс 2008 , §2.10

[15] Евклид 1956 , с. 319

[17] Евклид 1956 , с. 321

[19] Евклид 1956 , с. 323

[21] Евклид 1956 , с. 331

[23] Евклид 1956 , с. 332

[25] Евклид 1956 , стр. 331–332.

[ примечание 1 ]

[ примечание 2 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ примечание 3 ]

[ примечание 4 ]

[ примечание 5 ]

[ примечание 6 ]

[ примечание 7 ]

[ 18 ]

[ 1 ]

[ 2 ]

[ 3 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]