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

Не путать с Фундаментальной теоремой алгебры или Фундаментальной теоремой исчисления .

В Disquisitiones Arithmetica (1801 г.) Гаусс доказал уникальную теорему факторизации. и использовал его для доказательства закона квадратичной взаимности .

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

$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 можно представить в виде произведения простых чисел, и, во-вторых, как бы это ни было сделано, всегда будет ровно четыре двойки, одна тройка, две пятерки и никаких других. штрихи в продукте.

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

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

Теорема обобщается на другие алгебраические структуры , которые называются уникальными областями факторизации и включают области главных идеалов , евклидовы области и кольца многочленов над полем . Однако теорема не справедлива для целых алгебраических чисел . Эта неудача однозначной факторизации является одной из причин трудности доказательства Великой теоремы Ферма . Неявное использование уникальной факторизации в кольцах целых алгебраических чисел лежит в основе ошибок многих из многочисленных ложных доказательств, которые были написаны в течение 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 и частично доказывает, что разложение уникально – момент критически важный. отметил Андре Вейль . Действительно, в этом предложении все показатели степени равны единице, поэтому для общего случая ничего не сказано.

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

Статья 16 « Гаусса Арифметических исследований» представляет собой раннее современное утверждение и доказательство, использующее модульную арифметику .

Приложения

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

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

$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 ).

Это представление называется каноническим представлением. n или стандартная форма из н . Например,

999 = 3 ³ ×37,

1000 = 2 ³ ×5 ³ ,

1001 = 7×11×13.

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

$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 :

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

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

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

Предположим, что $s$ — наименьшее целое положительное число, которое является произведением простых чисел двумя разными способами. Это, кстати, означает, что $s$, если оно существует, должно быть составным числом, большим, чем $1$. Теперь скажи

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

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

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

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

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

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

Обобщения

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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

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

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

• Гаусс, Карл Фридрих (1828), Теория биквадратичных вычетов, Первый комментарий , Геттинген: Комментарий. Соц. королевская наука, Геттинген 6
• Гаусс, Карл Фридрих (1832), Теория биквадратных вычетов, Второй комментарий , Геттинген: Комментарий. Соц. королевская наука, Геттинген 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 г.