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

Целые числа имеют уникальные простые множители

В «Арифметических исследованиях» (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

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

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

Статья 16 « Арифметических исследований» Гаусса представляет собой раннее современное утверждение и доказательство, использующее модульную арифметику . ^[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 , где каждое p _i и q _i является простым числом. Мы видим, что p ₁ делит q ₁ q ₂ ... q _k , поэтому p ₁ делит некоторое q _i по лемме Евклида . Без потери общности, скажем, p ₁ делит q ₁ . Поскольку p ₁ и q ₁ оба являются простыми числами, следует, что p ₁ = q ₁ . Возвращаясь к нашим разложениям на простые множители 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. Gauss (1986, ст. 16)
2. Гаусс (1986, ст. 131)
3. Лонг (1972, стр. 44)
4. Петтофреццо и Биркит (1970, стр. 53)
5. Харди и Райт (2008, Том 2)
6. В кольце целых алгебраических чисел разложение на простые элементы может быть неоднозначным, но можно восстановить однозначное разложение, если разложить на идеалы .
7. Вайль (2007, стр. 5): «Даже у Евклида мы не находим общего утверждения об уникальности разложения целого числа на простые множители; конечно, он мог знать об этом, но все, что у него есть, — это утверждение (Eucl.IX.I4) о НОК любого числа данных простых чисел».
8. А. Гоксель Агаргун и Э. Мехмет Озкан. «Исторический обзор основной теоремы арифметики» (PDF) . Historia Mathematica : 209. Можно сказать, что Евклид делает первый шаг на пути к существованию разложения на простые множители, а аль-Фариси делает последний шаг, фактически доказав существование конечного разложения на простые множители в своем первом предложении.
9. Рашед, Рошди (2002-09-11). Энциклопедия истории арабской науки. Routledge. стр. 385. ISBN 9781134977246. Известный физик и математик Камаль ад-Дин аль-Фариси составил статью, в которой он намеренно попытался доказать теорему Ибн Курры алгебраическим способом. Это заставило его понять первые арифметические функции и провести полную подготовку, которая привела его к тому, чтобы впервые сформулировать основную теорему арифметики.
10. Лонг (1972, стр. 45)
11. Петтофреццо и Биркит (1970, стр. 55)
12. Харди и Райт (2008, § 1.2)
13. Доусон, Джон В. (2015), Зачем доказывать это снова? Альтернативные доказательства в математической практике. , Springer, стр. 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, MR  2445243, Zbl  1159.11001
• Лонг, Кэлвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Лексингтон: DC Heath and Company , LCCN  77-171950.
• Петтофреццо, Энтони Дж.; Биркит, Дональд Р. (1970), Элементы теории чисел , Englewood Cliffs: Prentice Hall , 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

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

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