Основная теорема арифметики

Целые числа имеют уникальные простые факторизации.

В Disquisitiones Arithmeticae (1801) Гаусс доказал уникальную теорему факторизации ^[1] и использовал ее для доказательства закона квадратичной взаимности . ^[2]

В математике фундаментальная теорема арифметики , также называемая теоремой об уникальной факторизации и теоремой о факторизации простых чисел , утверждает, что каждое целое число больше 1 может быть однозначно представлено как произведение простых чисел с точностью до порядка множителей. ^{[3] [4] [5]} Например,

${\displaystyle 1200=2^{4}\cdot 3^{1}\cdot 5^{2}=(2\cdot 2\cdot 2\cdot 2)\cdot 3\cdot (5\cdot 5)=5\cdot 2\cdot 5\cdot 2\cdot 3\cdot 2\cdot 2=\ldots }$

Теорема говорит об этом примере две вещи: во-первых, что 1200 можно представить в виде произведения простых чисел, и, во-вторых, как бы это ни было сделано, всегда будет ровно четыре двойки, одна тройка, две пятерки и никакие другие. штрихи в продукте.

Требование, чтобы множители были простыми, необходимо: факторизации, содержащие составные числа , могут быть неуникальны (например, ). ${\displaystyle 12=2\cdot 6=3\cdot 4}$

Эта теорема является одной из основных причин, почему 1 не считается простым числом : если бы 1 было простым, то разложение на простые числа не было бы уникальным; например, ${\displaystyle 2=2\cdot 1=2\cdot 1\cdot 1=\ldots }$

Теорема обобщается на другие алгебраические структуры , которые называются уникальными областями факторизации и включают области главных идеалов , евклидовы области и кольца многочленов над полем . Однако теорема не справедлива для целых алгебраических чисел . ^[6] Эта неудача однозначной факторизации является одной из причин трудности доказательства Великой теоремы Ферма . Неявное использование уникальной факторизации в кольцах целых алгебраических чисел лежит в основе ошибок многих из многочисленных ложных доказательств, которые были написаны в течение 358 лет между утверждением Ферма и доказательством Уайлса .

История

Фундаментальную теорему можно вывести из книги VII, предложений 30, 31 и 32, и книги IX, предложения 14 « Начал » Евклида .

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

-  Евклид, Книга VII «Начала», предложение 30.

(В современной терминологии: если простое число p делит произведение ab , то p делит либо a , либо b , либо оба.) Предложение 30 называется леммой Евклида и является ключевым в доказательстве основной теоремы арифметики.

Любое составное число измеряется некоторым простым числом.

-  Евклид, Книга VII «Начала», предложение 31.

(В современной терминологии: каждое целое число больше единицы делится без остатка на некоторое простое число.) Предложение 31 доказывается непосредственно бесконечным спуском .

Любое число либо является простым, либо измеряется некоторым простым числом.

-  Евклид, Книга VII «Начала», предложение 32.

Предложение 32 выводится из предложения 31 и доказывает, что разложение возможно.

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

-  Евклид, Книга IX «Начала», предложение 14.

(В современной терминологии: наименьшее общее кратное нескольких простых чисел не кратно любому другому простому числу.) Предложение 14 книги IX выведено из предложения 30 книги VII и частично доказывает, что разложение уникально, - критически важный момент. отметил Андре Вейль . ^[7] Действительно, в этом предложении все показатели степени равны единице, поэтому для общего случая ничего не сказано.

В то время как Евклид сделал первый шаг на пути к существованию факторизации простых чисел, Камаль ад-Дин аль-Фариси сделал последний шаг ^[8] и впервые сформулировал основную теорему арифметики. ^[9]

Статья 16 « Disquisitiones Arithmeticae» Гаусса представляет собой раннее современное утверждение и доказательство, использующее модульную арифметику . ^[1]

Приложения

Каноническое представление натурального числа

Каждое положительное целое число n > 1 можно представить ровно одним способом в виде произведения простых степеней.

${\displaystyle n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\prod _{i=1}^{k}p_{i}^{n_{i}},}$

где p ₁ < p ₂ < ... < p _k — простые числа, а n _i — целые положительные числа. Это представление обычно распространяется на все положительные целые числа, включая 1, согласно соглашению, что пустое произведение равно 1 (пустое произведение соответствует k = 0 ).

Это представление называется каноническим представлением ^[10] n или стандартной формой ^{[11] [12} ] n . Например,

999 = 3 ³ ×37,

1000 = 2 ³ ×5 ³ ,

1001 = 7×11×13.

Коэффициенты p ⁰ = 1 могут быть вставлены без изменения значения n (например, 1000 = 2 ³ ×3 ⁰ ×5 ³ ). Фактически, любое положительное целое число можно однозначно представить как бесконечное произведение всех положительных простых чисел, как

${\displaystyle n=2^{n_{1}}3^{n_{2}}5^{n_{3}}7^{n_{4}}\cdots =\prod _{i=1}^{\infty }p_{i}^{n_{i}},}$

где конечное число n i _{являются} целыми положительными числами, а остальные равны нулю.

Разрешение отрицательных показателей обеспечивает каноническую форму для положительных рациональных чисел .

Арифметические операции

Канонические представления произведения, наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) двух чисел a и b могут быть просто выражены через канонические представления самих чисел a и b :

${\displaystyle {\begin{alignedat}{2}a\cdot b&=2^{a_{1}+b_{1}}3^{a_{2}+b_{2}}5^{a_{3}+b_{3}}7^{a_{4}+b_{4}}\cdots &&=\prod p_{i}^{a_{i}+b_{i}},\\\gcd(a,b)&=2^{\min(a_{1},b_{1})}3^{\min(a_{2},b_{2})}5^{\min(a_{3},b_{3})}7^{\min(a_{4},b_{4})}\cdots &&=\prod p_{i}^{\min(a_{i},b_{i})},\\\operatorname {lcm} (a,b)&=2^{\max(a_{1},b_{1})}3^{\max(a_{2},b_{2})}5^{\max(a_{3},b_{3})}7^{\max(a_{4},b_{4})}\cdots &&=\prod p_{i}^{\max(a_{i},b_{i})}.\end{alignedat}}}$

Однако факторизация целых чисел , особенно больших чисел, намного сложнее, чем вычислительные произведения, НОД или НОК. Поэтому эти формулы имеют ограниченное применение на практике.

Арифметические функции

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

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

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

Существование

Необходимо доказать, что каждое целое число больше 1 является либо простым, либо произведением простых чисел. Во-первых, 2 — простое число. Затем по сильной индукции предположим, что это верно для всех чисел больше 1 и меньше n . Если n простое, доказывать больше нечего. В противном случае существуют целые числа a и b , где n = ab и 1 < a ≤ b < n . По предположению индукции a = p ₁ p ₂ ⋅⋅⋅ p _j и b = q ₁ q ₂ ⋅⋅⋅ q _k являются произведениями простых чисел. Но тогда n = ab = p ₁ p ₂ ⋅⋅⋅ p _j q ₁ q ₂ ⋅⋅⋅ q _k является произведением простых чисел.

Уникальность

Предположим, наоборот, что существует целое число, которое имеет две различные простые факторизации. Пусть n — наименьшее такое целое число, и запишите n = p ₁ p ₂ ... p _j = q ₁ q ₂ ... q _k , где каждый _pi и q i _— простые числа. Мы видим, что p ₁ делит q ₁ q ₂ ... q _k , поэтому p ₁ делит некоторое q _i по лемме Евклида . Без ограничения общности, скажем, p ₁ делит q ₁ . Поскольку p1 и q1 оба простые, отсюда _{следует , что} p1 ₌ q1 . Возвращаясь к нашей факторизации n , мы можем отменить эти два фактора и заключить, что p ₂ ... p _j = q ₂ ... q _k . Теперь у нас есть две различные простые факторизации некоторого целого числа, строго меньшего n , что противоречит минимальности n .

Единственность без леммы Евклида.

Основную теорему арифметики можно доказать и без использования леммы Евклида. ^[13] Следующее доказательство основано на оригинальной версии алгоритма Евклида .

Предположим, что это наименьшее положительное целое число, которое является произведением простых чисел двумя разными способами. Между прочим, это означает, что , если оно существует, должно быть составным числом, большим, чем . Сейчас скажи ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle 1}$

${\displaystyle {\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}}}$

Каждое должно отличаться от каждого. В противном случае, если скажем, существовало бы некоторое положительное целое число , меньшее s и имеющее две различные простые факторизации. Можно также предположить, что , поменяв местами две факторизации, если это необходимо. ${\displaystyle p_{i}}$ ${\displaystyle q_{j}.}$ ${\displaystyle p_{i}=q_{j},}$ ${\displaystyle t=s/p_{i}=s/q_{j}}$ ${\displaystyle p_{1}<q_{1},}$

Установка и у человека Кроме того, поскольку у него есть Из этого следует, что ${\displaystyle P=p_{2}\cdots p_{m}}$ ${\displaystyle Q=q_{2}\cdots q_{n},}$ ${\displaystyle s=p_{1}P=q_{1}Q.}$ ${\displaystyle p_{1}<q_{1},}$ ${\displaystyle Q<P.}$

${\displaystyle s-p_{1}Q=(q_{1}-p_{1})Q=p_{1}(P-Q)<s.}$

Поскольку предполагалось, что положительные целые числа меньше s имеют уникальную простую факторизацию, она должна присутствовать при факторизации либо или Q . Последний случай невозможен, так как Q , будучи меньшим, чем s , должен иметь уникальную простую факторизацию и отличаться от каждого. Первый случай также невозможен, так как, если является делителем его, должен быть также делитель которого невозможен как и являются различными простыми числами. ${\displaystyle p_{1}}$ ${\displaystyle q_{1}-p_{1}}$ ${\displaystyle p_{1}}$ ${\displaystyle q_{j}.}$ ${\displaystyle p_{1}}$ ${\displaystyle q_{1}-p_{1},}$ ${\displaystyle q_{1},}$ ${\displaystyle p_{1}}$ ${\displaystyle q_{1}}$

Следовательно, не может существовать наименьшее целое число с более чем одной различной простой факторизацией. Каждое положительное целое число должно быть либо само по себе простым числом, которое будет разлагаться однозначно, либо составным числом, которое также однозначно разлагается на простые числа, либо, в случае целого числа , не разлагаться ни на какое простое число. ${\displaystyle 1}$

Обобщения

Первое обобщение теоремы можно найти во второй монографии Гаусса (1832 г.) о биквадратичной взаимности . В этой статье было представлено то, что сейчас называется кольцом гауссовских целых чисел , набор всех комплексных чисел a + bi , где a и b — целые числа. Теперь оно обозначается как Он показал, что это кольцо имеет четыре единицы ±1 и ± i , что ненулевые и неединичные числа делятся на два класса: простые и составные, и что (за исключением порядка) составные числа имеют единственная факторизация как произведение простых чисел ( с точностью до порядка и умножения на единицы). ^[14] ${\displaystyle \mathbb {Z} [i].}$

Точно так же в 1844 году, работая над кубической взаимностью , Эйзенштейн ввёл кольцо , где – кубический корень из единицы . Это кольцо целых чисел Эйзенштейна , и он доказал, что оно состоит из шести единиц и имеет уникальную факторизацию. ${\displaystyle \mathbb {Z} [\omega ]}$ ${\textstyle \omega ={\frac {-1+{\sqrt {-3}}}{2}},}$   ${\displaystyle \omega ^{3}=1}$ ${\displaystyle \pm 1,\pm \omega ,\pm \omega ^{2}}$

Однако было также обнаружено, что уникальная факторизация не всегда выполняется. Пример приводит . В этом кольце имеется ^[15] ${\displaystyle \mathbb {Z} [{\sqrt {-5}}]}$

${\displaystyle 6=2\cdot 3=\left(1+{\sqrt {-5}}\right)\left(1-{\sqrt {-5}}\right).}$

Подобные примеры привели к изменению понятия «простое число». В нем можно доказать, что если какой-либо из приведенных выше факторов можно представить в виде произведения, например, 2 = ab , то один из a или b должен быть единицей. Это традиционное определение слова «простой». Можно также доказать, что ни один из этих факторов не подчиняется лемме Евклида; например, 2 не делит ни (1 + √ −5 ), ни (1 − √ −5 ), хотя делит их произведение 6. В теории алгебраических чисел 2 называется несократимой (делящейся только на себя или на единицу), но не простым числом . в (если он делит продукт, он должен разделить один из факторов). Упоминание необходимо, поскольку 2 является простым и неприводимым. Используя эти определения, можно доказать, что в любой области целостности простое число должно быть неприводимым. Классическую лемму Евклида можно перефразировать так: «В кольце целых чисел каждая неприводимая является простой». Это также верно в и , но не в ${\displaystyle \mathbb {Z} \left[{\sqrt {-5}}\right]}$ ${\displaystyle \mathbb {Z} \left[{\sqrt {-5}}\right]}$ ${\displaystyle \mathbb {Z} \left[{\sqrt {-5}}\right]}$ ${\displaystyle \mathbb {Z} \left[{\sqrt {-5}}\right]}$ ${\displaystyle \mathbb {Z} .}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {Z} [i]}$ ${\displaystyle \mathbb {Z} [\omega ],}$ ${\displaystyle \mathbb {Z} [{\sqrt {-5}}].}$

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

В 1843 году Куммер ввёл в современную теорию идеалов , особых подмножеств колец, понятие идеального числа , которое было развито далее Дедекиндом (1876). Для идеалов определено умножение, а кольца, в которых они имеют единственную факторизацию, называются областями Дедекинда .

Существует версия уникальной факторизации для ординалов , однако она требует некоторых дополнительных условий для обеспечения уникальности.

Любой коммутативный моноид Мёбиуса удовлетворяет единственной теореме факторизации и, таким образом, обладает арифметическими свойствами, аналогичными свойствам мультипликативной полугруппы натуральных чисел. Фундаментальная теорема арифметики по сути является частным случаем единственной теоремы факторизации в коммутативных моноидах Мёбиуса.

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

• Целочисленная факторизация  - разложение числа на произведение.
• Простая подпись  - мультимножество простых показателей в простой факторизации.

Примечания

1. Гаусс (1986, ст. 16)
2. Гаусс (1986, ст. 131)
3. Лонг (1972, стр. 44)
4. Петтофреззо и Биркит (1970, стр. 53)
5. Харди и Райт (2008, часть 2)
6. В кольце целых алгебраических чисел факторизация на простые элементы может быть неоднозначной, но можно восстановить уникальную факторизацию, если разложить на идеалы .
7. Вейль (2007, стр. 5): «Даже у Евклида мы не можем найти общего утверждения о единственности факторизации целого числа на простые числа; конечно, он мог знать об этом, но все, что у него есть, это утверждение (Евкл.IX.I4) о НЦМ любого числа данных простых чисел».
8. А. Гоксель Агаргун и Э. Мехмет Озкан. «Исторический обзор основной теоремы арифметики» (PDF) . Historia Mathematica : 209. Можно сказать, что Евклид делает первый шаг на пути к существованию факторизации простых чисел, а аль-Фаризи делает последний шаг, фактически доказывая существование конечной факторизации простых чисел в своем первом предложении.
9. Рашид, Рошди (11 сентября 2002 г.). Энциклопедия истории арабской науки. Рутледж. п. 385. ИСБН 9781134977246. Знаменитый физик и математик Камаль ад-Дин аль-Фариси составил статью, в которой намеренно намеревался доказать теорему Ибн Курры алгебраическим способом. Это заставило его понять первые арифметические функции и провести полную подготовку, которая позволила ему впервые сформулировать основную теорему арифметики.
10. Лонг (1972, стр. 45)
11. Петтофреззо и Биркит (1970, стр. 55)
12. Харди и Райт (2008, § 1.2)
13. Доусон, Джон В. (2015), Зачем доказывать это снова? Альтернативные доказательства в математической практике. , Спрингер, с. 45, ISBN 9783319173689
14. Гаусс, BQ, §§ 31–34
15. Харди и Райт (2008, § 14.6)

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

Disquisitiones Arithmeticae переведена с латыни на английский и немецкий языки. Немецкое издание включает все его статьи по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса, исследования биквадратичной взаимности и неопубликованные заметки.

• Гаусс, Карл Фридрих (1986), Disquisitiones Arithemeticae (второе, исправленное издание), перевод Кларка, Артура А., Нью-Йорк: Springer , ISBN 978-0-387-96254-2
• Гаусс, Карл Фридрих (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae и другие статьи по теории чисел) (второе издание) (на немецком языке), перевод Мазера, Х., Нью-Йорк: Челси, ISBN 0-8284-0191-8

Две монографии Гаусса, опубликованные по биквадратичной взаимности, имеют последовательную нумерацию разделов: первая содержит §§ 1–23, вторая – §§ 24–76. Сноски, ссылающиеся на них, имеют форму «Gauss, BQ, § n ». Сноски, относящиеся к Disquisitiones Arithmeticae , имеют форму «Gauss, DA, Art. n ».

• Гаусс, Карл Фридрих (1828), Theoria residuorum biquadraticorum, Commentatio prima , Геттинген: Комментарий. Соц. Regiae Sci, Геттинген 6
• Гаусс, Карл Фридрих (1832), Theoria residuorum biquadraticorum, Commentatio secunda , Геттинген: Комментарий. Соц. Regiae Sci, Геттинген 7

Они находятся в Werke Гаусса , том II, стр. 65–92 и 93–148; Немецкие переводы — стр. 511–533 и 534–586 немецкого издания Disquisitiones .

• Евклид (1956), Тринадцать книг Элементов , т. 2 (Книги III-IX), перевод Томаса Литтла Хита (второе издание, полное издание), Нью-Йорк: Дувр , ISBN 978-0-486-60089-5
• Харди, штат Джорджия ; Райт, Э.М. (2008) [1938], Введение в теорию чисел , отредактированное Д. Р. Хит-Брауном и Дж. Х. Сильверманом . Предисловие Эндрю Уайлса . (6-е изд.), Оксфорд: Oxford University Press , ISBN 978-0-19-921986-5, МР  2445243, Збл  1159.11001
• Лонг, Кэлвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Лексингтон: DC Heath and Company , LCCN  77-171950.
• Петтофреззо, Энтони Дж.; Биркит, Дональд Р. (1970), Элементы теории чисел , Энглвуд Клиффс: Прентис Холл , LCCN  77-81766.
• Ризель, Ганс (1994), Простые числа и компьютерные методы факторизации (второе издание) , Бостон: Birkhäuser, ISBN 0-8176-3743-5
• Вейль, Андре (2007) [1984], Теория чисел: подход к истории от Хаммурапи до Лежандра , Modern Birkhäuser Classics, Бостон, Массачусетс: Birkhäuser, ISBN 978-0-817-64565-6

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

• Почему основная теорема арифметики не очевидна?
• НОД и основная теорема арифметики при разрубании узла .
• PlanetMath: доказательство фундаментальной теоремы арифметики
• Блог «Великая теорема Ферма: Уникальная факторизация» — блог, в котором освещается история Великой теоремы Ферма от Диофанта Александрийского до доказательства Эндрю Уайлса .
• «Фундаментальная теорема арифметики» Гектора Зенила, Демонстрационный проект Wolfram , 2007.
• Грайм, Джеймс, «1 и простые числа», Numberphile , Брэди Харан , заархивировано из оригинала 11 декабря 2021 г.