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

Уникальная теорема факторизации была доказана Гауссом в его книге 1801 года «Арифметические исследования» . ^[1] В этой книге Гаусс использовал основную теорему для доказательства закона квадратичной взаимности . ^[2]

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

${\ Displaystyle 1200 = 2 ^ {4} \ CDOT 3 \ 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 }$

Исходная версия Евклида [ править ]

Книга VII, предложения 30, 31 и 32, и книга IX, утверждение 14 из Евклида «s элементов , по существу , утверждение и доказательство основной теоремы.

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

-  Евклид, Книга Элементов VII , Предложение 30

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

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

-  Евклид, Книга Элементов VII , Предложение 31

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

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

-  Евклид, Книга Элементов VII , Предложение 32

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

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

-  Евклид, Книга Элементов IX , Предложение 14

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

Статья 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).

Это представление называется каноническим представлением ^[8] числа n или стандартной формой ^{[9] [10]} числа 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 - натуральные числа, а остальные равны нулю. Разрешение отрицательных показателей обеспечивает каноническую форму для положительных рациональных чисел .

Арифметические операции [ править ]

Канонические представления продукта, наибольший общий делитель (GCD), и наименьшее общее кратное (LCM) из двух чисел и б может быть выражено просто в терминах канонических представлений и б себя:

${\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}}}$

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

Арифметические функции [ править ]

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

Доказательство [ править ]

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

Существование [ править ]

Необходимо показать, что каждое целое число больше 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 простое число. (Обратите внимание, что j и k не меньше 2.) Мы видим, что p ₁ делит q ₁ q ₂ ... q _k , поэтому p ₁делит некоторое q _i по лемме Евклида . Без ограничения общности скажем, что p ₁ делит q ₁ . Поскольку p ₁ и q ₁ простые числа, p ₁ = q ₁ . Возвращаясь к факторизации n , мы можем сократить эти два члена, чтобы заключить, что p ₂ ... p _j = q ₂ ... q _k . Теперь у нас есть две различные простые факторизации некоторого целого числа, строго меньшего, чем n, что противоречит минимальности n .

Единственность без леммы Евклида [ править ]

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

Предположим, что это наименьшее положительное целое число, которое является произведением простых чисел двумя разными способами. Между прочим, это означает, что , если оно существует, должно быть составное число больше, чем . Сейчас скажи ${\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 (q_{1}-p_{1})Q=p_{1}(P-Q)<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 г.) о биквадратичной взаимности . Этот документ представил то , что теперь называется кольцом из гауссовых целых чисел , множество всех комплексных чисел + би , где и Ь целые числа. Теперь это обозначено как Он показал, что это кольцо имеет четыре единицы ± 1 и ± i , что ненулевые, неединичные числа делятся на два класса, простые числа и составные части, и что (за исключением порядка) композиты имеют уникальная факторизация как произведение простых чисел. ^[11]${\displaystyle \mathbb {Z} [i].}$

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

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

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

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

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

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

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

" 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 резидуум biquadraticorum, Commentatio prima , Геттинген: Комментарий. Soc. regiae sci, Göttingen 6
• Гаусс, Карл Фридрих (1832), Theoria резидуум biquadraticorum, Commentatio secunda , Геттинген: Комментарий. Soc. regiae sci, Göttingen 7

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

• Бейкер, Алан (1984), Краткое введение в теорию чисел , Кембридж, Великобритания: Cambridge University Press, ISBN 978-0-521-28654-1
• Евклид (1956), Тринадцать книг Элементов , 2 (Книги III-IX), Перевод Томаса Литтла Хита (Второе издание, несокращенное издание), Нью-Йорк: Дувр , ISBN 978-0-486-60089-5
• Харди, GH ; Райт, EM (2008) [1938]. Введение в теорию чисел . Отредактировано DR Heath-Brown и JH Silverman . Предисловие Эндрю Уайлса . (6-е изд.). Оксфорд: Издательство Оксфордского университета . ISBN 978-0-19-921986-5. Руководство по ремонту  2445243 . Zbl  1159.11001 .
• А. Корнилович; П. Рудницки (2004), "Основная теорема арифметики", Формализованная математика , 12 (2): 179–185
• Лонг, Кальвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Lexington: DC Heath and Company , LCCN  77-171950.
• Петтофреццо, Энтони Дж .; Биркит, Дональд Р. (1970), Элементы теории чисел , Englewood Cliffs: Prentice Hall , LCCN  77-81766.
• Ризель, Ханс (1994), Простые числа и компьютерные методы факторизации (второе издание) , Бостон: Биркхойзер, ISBN 0-8176-3743-5
• Вейль, Андре (2007) [1984]. Теория чисел: подход через историю от Хаммурапи до Лежандра . Современная классика Биркхойзера. Бостон, Массачусетс: Биркхойзер. ISBN 978-0-817-64565-6.
• Вайсштейн, Эрик В. «Аномальное число» . MathWorld .
• Вайсштейн, Эрик В. "Основная теорема арифметики" . MathWorld .

Внешние ссылки [ править ]

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