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

Не путать с Основной теоремой алгебры .

В 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 Гаусса » « Disquisitiones Arithmeticae представляет собой раннее современное утверждение и доказательство, использующее модульную арифметику .

Приложения

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

Каждое положительное целое число 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 — наименьшее такое целое число, и запишите = p 1 _p 2 _... p j ₌ q 1 _q 2 _... q k _, где каждый pi _n и 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), Лекции по высшей арифметике (второе издание) (на немецком языке), перевод Мазера Х., Нью-Йорк: Челси, 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 г.