Основная теорема арифметики - Fundamental theorem of arithmetic

Теорема единственной факторизации была доказана Гаусс с его книгой 1801 года Disquisitiones Arithmeticae.^[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 из Евклид с Элементы по сути, являются формулировкой и доказательством основной теоремы.

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

Это представление называется каноническое представление^[8] из п, или стандартная форма^[9][10] из п. Например,

999 = 3³×37,

1000 = 2³×5³,

1001 = 7×11×13.

Факторы п⁰ = 1 можно вставить без изменения значения п (например, 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}},}$

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

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

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

${ displaystyle { begin {alignat} {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 {alignat}}}$

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

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

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

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

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

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

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

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

Предположим, что существует целое число, которое имеет две различные простые факторизации. Позволять п быть наименьшим таким целым числом и написать п = п₁ п₂ ... п_j = q₁ q₂ ... q_k, где каждый п_я и q_я простое. (Примечание j и k оба не меньше 2.) Мы видим п₁ разделяет q₁ q₂ ... q_k, так п₁ разделяет некоторые q_я по лемме Евклида. Без потери общности скажем п₁ разделяет q₁. С п₁ и q₁ оба простые числа, отсюда следует, что п₁ = q₁. Возвращаясь к нашим факторизациям п, мы можем отменить эти два условия, чтобы заключить п₂ ... п_j = q₂ ... q_k. Теперь у нас есть две различные простые факторизации некоторого целого числа, строго меньшего, чем п, что противоречит минимальности п.

Элементарное доказательство уникальности

Фундаментальная теорема арифметики также может быть доказана без использования леммы Евклида следующим образом:

Предположить, что s > 1 - наименьшее положительное целое число, которое является произведением простых чисел двумя разными способами. Если s были простыми, тогда он был бы уникальным как сам, поэтому s не является простым числом, и в каждой факторизации должно быть не менее двух простых чисел. s:

${ displaystyle { begin {align} s & = p_ {1} p_ {2} cdots p_ {m} & = q_ {1} q_ {2} cdots q_ {n}. end {выравнивается}} }$

Если есть п_я = q_j затем при отмене s/п_я = s/q_j было бы другим положительным целым числом, отличным от s, которое больше 1 и также имеет две различные факторизации. Но s/п_я меньше чем s, смысл s на самом деле не будет наименьшим таким целым числом. Поэтому каждый п_я должен отличаться от каждого q_j.

Без потери общности возьмем п₁ < q₁ (если это еще не так, переключите п и q обозначений.)

${ displaystyle t = (q_ {1} -p_ {1}) (q_ {2} cdots q_ {n}),}$

и заметим, что 1 < q₂ ≤ т < s. Следовательно т должен иметь уникальное разложение на простые множители. По перестановке мы видим,

${ displaystyle { begin {align} t & = q_ {1} (q_ {2} cdots q_ {n}) - p_ {1} (q_ {2} cdots q_ {n}) & = s- p_ {1} (q_ {2} cdots q_ {n}) & = p_ {1} ((p_ {2} cdots p_ {m}) - (q_ {2} cdots q_ {n}) ). end {align}}}$

Здесь ты = ((п₂ ... п_м) - (q₂ ... q_п)) положительно, поскольку если бы оно было отрицательным или нулевым, то таким же было бы его произведение с п₁, но этот продукт равен т что положительно. Так ты либо 1, либо делится на простые числа. В любом случае, т = п₁ты дает разложение на простые множители т, который, как мы знаем, уникален, поэтому п₁ появляется в простом факторизации т.

Если (q₁ - п₁) равняется 1, то разложение на простые множители т было бы все q 's, что исключило бы п₁ от появления. Таким образом (q₁ - п₁) не 1, но положительный, поэтому делится на простые числа: (q₁ - п₁) = (р₁ ... р_час). Это дает разложение на простые множители

${ displaystyle t = (r_ {1} cdots r_ {h}) (q_ {2} cdots q_ {n}),}$

который, как мы знаем, уникален. Сейчас же, п₁ появляется в простом факторизации т, и он не равен никакому q, значит, это должен быть один из р'с. Это означает п₁ является фактором (q₁ - п₁), поэтому существует положительное целое число k такой, что п₁k = (q₁ - п₁), и поэтому

${ displaystyle p_ {1} (k + 1) = q_ {1}.}$

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

Обобщения

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

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

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

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

Примеры, подобные этому, привели к изменению понятия «простое число». В ${ displaystyle mathbb {Z} [{ sqrt {-5}}]}$ можно доказать, что если любой из вышеперечисленных факторов может быть представлен как продукт, например, 2 = ab, затем один из а или же б должно быть единицей. Это традиционное определение «прайм». Также можно доказать, что ни один из этих факторов не подчиняется лемме Евклида; например, 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}.}$ Используя эти определения, можно доказать, что в любом область целостности простое число должно быть несократимым. Классическую лемму Евклида можно перефразировать как «в кольце целых чисел ${ Displaystyle mathbb {Z}}$ каждая неприводимая проста ". Это также верно в ${ Displaystyle mathbb {Z} [я]}$ и ${ 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, § п". Сноски, относящиеся к Disquisitiones Arithmeticae имеют вид «Гаусс Д.А., ст. п".

• Гаусс, Карл Фридрих (1828), Theoria резидуум biquadraticorum, комментарий прима, Гёттинген: Комментарий. Soc. regiae sci, Göttingen 6
• Гаусс, Карл Фридрих (1832 г.), Theoria резидуум biquadraticorum, комментарий secunda, Гёттинген: Комментарий. Soc. regiae sci, Göttingen 7

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

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

внешняя ссылка

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