Так ли очевидна основная теорема арифметики? И всегда ли она верна?. / forpes.ru

Главная
Так ли очевидна основная теорема арифметики? И всегда ли она верна?.

Так ли очевидна основная теорема арифметики? И всегда ли она верна?. +9

04.07.2023 10:08

alexlyk314 29 4700 Источник

Каждое натуральное число раскладывается в произведение простых множителей, и притом однозначно с точностью до их перестановки. Это известное со школы и, казалось бы, очевидное утверждение гордо называется основной теоремой арифметики. В стандартной школьной программе она не доказывается - даётся только алгоритм разложения на простые (ищем наименьший простой делитель числа, делим на него, с частным проделываем ту же процедуру). Пример:

$120=2\cdot 60 =2\cdot 2\cdot 30=2\cdot 2\cdot 2\cdot 15=2^3\cdot 3\cdot 5.$

Таким образом можно разложить любое натуральное число. Однако встаёт вопрос о единственности. Что, если раскладывать на множители по-другому? Например,

$120=12\cdot 10=(3\cdot 4)\cdot (2\cdot 5)=(3\cdot 2\cdot 2)\cdot (2\cdot 5).$

После перестановки множителей получается то же разложение, что и выше, но будет ли так всегда? Многие не понимают, почему это не очевидно и надо доказывать. Лучший способ понять, что этот факт не очевиден, - показать примеры, когда он... неверен! Как это? Оказывается, существуют числовые (и не только) системы, в которых нет единственности разложения. По-видимому, исторически первые примеры связаны с попытками доказать Великую проблему Ферма: уравнение неразрешимо в натуральных числах ни для какого натурального $n\geq 3$ . Так, при Эйлер вышел в комплексную плоскость и обращался с числами $a+b\sqrt{-3}$ , где $a,b\in \mathbb Z$ , впоследствии названных эйлеровыми. Он молчаливо предполагал, что для них тоже верна основная теорема арифметики. Позже обнаружили, что это не так:

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

Можно показать, что это действительно два разных разложения на простые эйлеровы числа. Приведём более простые примеры, не требующие знания комплексных чисел. Прежде всего заметим, что говорить о делимости осмысленно в любых системах, где есть умножение. Ограничимся пока натуральными числами.

Подмножество $M\subseteq \mathbb N$ назовём мультипликативной системой, если $1\in M$ и $ab\in M$ для всех $a,b\in M$ . Вот несколько примеров, помимо двух тривиальных - $\mathbb N$ и $\{1\}$ :

$\begin{align*} &M_1=\{2k+1\mid k\in \mathbb N_0\}=\{1,3,5,7,\ldots\} \text{ --- нечётные числа,}\\ &M_2=\{4k+1\mid k\in \mathbb N_0\}=\{1,5,9,13,\ldots\} \text{ --- числа, дающие остаток 1 при делении на 4,}\\ &M_3=\{2^k\mid k\in \mathbb N_0\}=\{1,2,4,8,\ldots\} \text{ --- степени двойки,}\\ &M_4=\{2^k\mid 1\ne k\in \mathbb N_0\}=\{1,4,8,16,\ldots\} \text{ --- степени двойки, кроме двойки.} \end{align*}$

Пусть - мультипликативная система в $\mathbb N$ и $a,b\in M$ . Скажем, чтоделит( $a\mid b$ ) в , если $b/a\in M$ . Число $p\in M$ назовём простым в , если имеет ровно два делителя в , и (в частности, $p\ne 1$ ).

Простое число в - это число со свойством: если $a,b\in M$ не делятся на, то не делится на .

Пример. В системе 8 не делится на 4, а потому и - простые числа. Отсюда получаем пример неоднозначного разложения на простые:

$4\cdot 4\cdot 4=8\cdot 8.$

Задача 1. Докажите, что в системе разложение на простые тоже не однозначно.

Задача 2. Опишите простые числа в системе

$M_5={1}\cup 2\mathbb N={1,2,4,6,8,\ldots}$

чётных чисел с единицей. Исследуйте, однозначно ли разложение на простые в этой системе.

Итак, существуют мультипликативные системы, состоящие из натуральных чисел, в которых основная теорема арифметики неверна, точнее, нет единственности разложения на простые. Почему в натуральном ряду единственность всё же имеет место? Это вытекает из следующего важного свойства простых чисел.

Лемма. Если простоене делит числа $a,b\in \mathbb N$ , тоне делит и их произведение.

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

$N=p_1\ldots p_m=q_1\ldots q_n.$

Мы можем считать, что - наименьшее число, имеющее два разложения. Так как делит $q_1(q_2\ldots q_n)$ , то по лемме делит или $q_2\ldots q_n$ . Продолжая, получим, что делит одно из , что возможно, только если . Сократив на этот множитель, мы получим два разных разложения числа , что противоречит минимальности .

Отметим, что лемма очевидно вытекает из основной теоремы арифметики: если не делит и , то не входит в разложения этих чисел на простые, а значит, не входит и в разложение их произведения. Таким образом, в мультипликативной системе $M\subseteq \mathbb N$ верна основная теорема арифметики в точности тогда, когда в ней верна лемма. Чтобы лучше это понять, решите следующую задачу.

Задача 3. Покажите на примерах, что в системах существуют простые числа, для которых лемма нарушается.

Доказательство леммы в $\mathbb N$ основано на алгоритме Евклида нахождения наибольшего общего делителя (НОД) путём последовательного деления с остатком. С помощью обратного хода алгоритма Евклида найденный НОД выражается линейной комбинацией исходных чисел с целыми коэффициентами. Начнём с примера.

Пример. Применим алгоритм Евклида к числам и .

Алгоритм Евклида: Обратный ход алгоритма Евклида:

$\begin{aligned} 39&=16\cdot 2+7\\ 16&=7\cdot 2+2\\ 7&=3\cdot 2+1. \end{aligned}$ $\begin{aligned} 1 &= 7 - 2 \cdot 3 = 7 - (16 - 7 \cdot 2) \cdot 3=\\ &=7\cdot 7-16\cdot 3= (39-16\cdot 2)\cdot 7-16\cdot 3=\\&=39\cdot 7-16\cdot 17.\end{aligned}$

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

Теорема. Для любых $x,y\in \mathbb N$ найдутся такие $u,v\in \mathbb Z$ , что

$(x,y)=xu+yv. \;\;\;\;\;\;\; (1)$

Равенство (1) называется соотношением Безу .

Из этой теоремы уже легко следует наша лемма.

Доказательство леммы. Так как не делит , то . По теореме для некоторых $u,v\in \mathbb Z$ . Умножим на : . Так как не делится на , делится на , то не делится на . Тем более, не делится на .

В заключение отметим, что исследование разложения на простые множители (далеко не только в числовых системах) привело к важнейшему в алгебре понятию идеала и в целом развитию теории колец. Заинтересованный читатель может почитать об этом в "Курсе алгебры" Э. Б. Винберга, "Избранных главах алгебры" И. Р. Шафаревича, "Введении в коммутативную алгебру" М. Атьи и М. Макдональда (список далеко не полон).

В разложении числа 1 нуль сомножителей, а в разложении каждого простого числа - один множитель.
Доказанную Э.Уайлсом в 1994 году.
В честь Этьена Безу. Впервые этот факт был опубликован для взаимно простых целых чисел французским математиком Мезириаком в 1624 году.

Автор: Андрей Канунников, к. ф.-м. н., мехмат МГУ, преподаватель ШАД Хелпер

Комментарии (29)

alexEtse
04.07.2023 10:23
#25715912
+6
Многие не понимают, почему это не очевидно и надо доказывать.

Вроде ж всё просто - доказывать надо всё, что не аксиома и не определение :)

А слово "очевидно" - оно опасное, ведущее к соблазнам ~~тёмной стороны~~ скрыть в рассуждении сложное доказательство или вообще недоказуемость.
1. rdp
  04.07.2023 10:23
  #25716010
  пример неоднозначного
  
  2x2=?
  1. alexEtse
    04.07.2023 10:23
    #25716122
    А в чём подвох?.. Умножение есть на множестве неотрицательных целых чисел, а вот для любого его подмножества эту операцию никто не обещал.
    
    rdp
    04.07.2023 10:23
    #25716450
    Нет подвоха. Мне показалось упражнение забавным. Ограничим себя в чём-нибудь и удивимся этому.
    
    alexEtse
    04.07.2023 10:23
    #25716694
    А :) Ну это да.
    
    А то ж без подготовки будет не столь понятна история о том, что надо таки сделать, чтобы можно стало делить на ноль...
    
    CaptainFlint
    04.07.2023 10:23
    #25717566
    Поэтому математики научились себя ограничивать так, чтобы удивляться поменьше. :-)
    Обычно рассматриваются такие системы, в которых результат операции над двумя элементами множества находится в самом этом множестве. Впрочем, и это необязательно, изучаются и такие функции, которые по двум элементам множества возвращают элемент какого-то совсем другого множества.

Polaris99
04.07.2023 10:23
#25716128
А $\sqrt{-3}$ - это еще простое число или уже нет? Я вот привык к тому, что простые числа - натуральные.
1. bigcrush
  04.07.2023 10:23
  #25716208
  Простое - не представимо в виде произведения меньших него(не считая единицы).
  1. sepuka
    04.07.2023 10:23
    #25716254
    В определении простого числа присутвует упоминание натуральных чисел, не?
    
    bigcrush
    04.07.2023 10:23
    #25716294
    Так и есть, натуральные числа не при чём. Понятие "простое" годится для любых числовых систем, для любого алгебраического кольца.
    
    sepuka
    04.07.2023 10:23
    #25716982
    -1
    Вы там и математику импортозаместить решили? У простого числа есть одно конкретное определение: это натуральное число и далее по тексту.
    
    alexejisma
    04.07.2023 10:23
    #25722314
    Ну тут имеется в виду немного другое. В алгебре вводят понятия кольца и евклидова кольца (кольцо с определенной на нем нормой, удовлетворяющей паре свойств) и уже в рамках евклидова кольца доказывают существование и единственность разложения на простые с точностью до умножения на обратимые элементы поля (например, x^2 = (x) * (x) = (x / 2) * (2 x) = ... в кольце многочленов). Но перед этим дается определение простого элемента:
    
    Необратимый ненулевой элемент p целостного кольца называется простым, если он не может быть представлен в виде p = ab, где a и b –– необратимые элементы
    
    Поэтому в кольце целых чисел простыми являются числа вида ±p. Так что не обязательно простое число является натуральным. Тут просто дело в том, что в школах обычно существенно упрощают, убирая из рассмотрения отрицательные числа, так как это только запутать может.
1. Milliard
  04.07.2023 10:23
  #25717514
  +1
  С $1±\sqrt{-3}$ не самый удачный пример, т.к. мнимая часть не целая. Так можно и не выходя на комплексную плоскость привести примеры разложения, например или $9=\sqrt{3}⋅\sqrt{3}⋅\sqrt{3}⋅\sqrt{3}$ .
  
  Но среди комплексных чисел куча примеров разложений и с целыми компонентами. или .
  1. mk2
    04.07.2023 10:23
    #25717792
    В таком случае 3 не является простым числом, потому что $3=\sqrt[]{3}*\sqrt[]{3}$ .
    
    С действительными или алгебраическими числами проблема в другом, непонятно где остановиться. Например $\sqrt{3}=\sqrt[4]{3}*\sqrt[4]{3}$ и следовательно само не является простым.
    
    Благодаря @i-netay у нас есть свойство "обратимость" и уточнённое определение единственности разложения. Понятно, что обратимыми в этих множествах являются примерно все, кроме 0 - соответственно под уточнённое определение мы гарантированно не попадаем.
    
    P.S. Отдельная благодарность Хабру за то, что в старой версии сайта TeX формулы в Markdown не работают.
1. i-netay
  04.07.2023 10:23
  #25718832
  Смотря в каком кольце. Если в $\{a+b\sqrt{-3}, a, b \in \mathbb{Z}\}$ , то да. В этом кольце есть норма $||a+b\sqrt{-3}|| = a^2 + 3b^2$ , она мультипликативна (то есть $||ab||=||a||\cdot||b||$ ), всегда принимает целое значение и для $\sqrt{-3}$ равна , а если норма с такими свойствами числа простое целое, то само число простое в кольце с нормой.
  
  Если, например, в $\mathbb{C}$ , то нет, потому что там нет простых чисел: в полях нет необратимых элементов, кроме .

DzenO
04.07.2023 10:23
#25716682

Таким образом можно разложить любое натуральное число. Однако встаёт вопрос о единственности. Что, если раскладывать на множители по-другому? Например,

Ну сколько помню правило про умножение гласит что от перестановки множителей произведение не меняется, так же как при сложении от перестановки слагаемых.
1. CaptainFlint
  04.07.2023 10:23
  #25717538
  Для обычных чисел — да. Для других математических объектов — уже не всегда. Скажем, умножение матриц некоммутативно, и A•B может быть не равно B•A.
  1. nin-jin
    04.07.2023 10:23
    #25718312
    +1
    Произведение Адамара вполне себе коммутативно. Уместно ли вообще называть умножением некоммутативную операцию - хороший вопрос.
    
    Refridgerator
    04.07.2023 10:23
    #25718346
    Почему под умножением матриц по умолчанию понимается именно матричное произведение, а не Адамара, хотя оно по смыслу намного ближе — тоже интересный вопрос.
    
    Gay_Lussak
    04.07.2023 10:23
    #25722306
    Адамарово произведение имеет куда меньшее применение, может быть поэтому. Не в каждом учебнике можно найти упоминание про Адамара.
    
    i-netay
    04.07.2023 10:23
    #25718866
    Уместность -- исключительно вопрос традиции. Говорить "операция" в неизвестной ситуации не любят. А если операция одна и отсутствует контекст, то заведомо коммутативную нередко называют сложением, а заведомо некоммутативную обычно умножением. Но появление контекста может внести изменения. Например, когда речь про моноид мономов в кольце многочленов, он обычно коммутативен, но их всё-таки перемножают.
    
    nin-jin
    04.07.2023 10:23
    #25718940
    Нет, это вопрос порядка в мозгах. Выводить сложение и умножение через коммутативность - это сильно, конечно.

antiquar
04.07.2023 10:23
#25716718
Есть обобщение основной теоремы арифметики на более экзотические кольца, теорема Ласкера (Ласкер тот самый, шахматист). Почитать можно в книжечке Атья, Макдональд.

i-netay
04.07.2023 10:23
#25717750
+1
Тут прямо просится дополнение.

В тексте говорится о системах, замкнутых относительно умножения -- о полугруппах (есть множество, ассоциативная операция, в общем-то всё, мультипликативная система, если операцию мы назвали умножением), к которым, конечно, относятся степени двойки и "наоборот" -- нечётные числа. Наоборот в том смысле, что они пересекаются по единице и вместе порождают натуральные числа. Однако полугруппы рассматриваются в другом контексте, чем более "повседневная" структура -- кольцо, где есть сложение и умножение, часто связываемая с видом чисел не "внутри" (как чётные в целых), а в целом -- целые, рациональные...

Основная теорема арифметики нередко формулируется для целых, а не натуральных. Но как быть с тем, что $6=2\cdot3=(-2)\cdot(-3)$ Это два разложения. А что с множителями? Ведь тоже простое, как и . Этот вопрос решается в алгебре понятием идеала (подмножество, где можно умножать и складывать), где мы можем выбрать образующую -- чиселку, умножением на которую получаются все. Мы можем выбрать и и С этим хорошо, выкрутились :) Хотя научно это называется не "выкрутились", а "формализовали и дали строгое определение", хотя разница не очень большая.

С представлением в виде произведения меньших его чисел в определении тоже есть момент с целыми и знаками. Ведь же произведение и так что же, не простое? Они ж меньше! И вот тут алгебра "выкручивается" введением обратимости: число обратимо, если имеет обратное. Обратимых целых всего два -- $\pm1$ Если представлять число как произведение необратимых, то всё ок. Разложение единственно, если оно единственно на меньшие или равные необратимые с точностью до домножения их на любые обратимые элементы и перестановок. И вот так оно работает без других оговорок полностью (в кольцах главных идеалов).

Зачем появляются вот эти все слова: идеал, обратимость, образующая? Они нужны, чтобы понятия имели однозначные определения без разных трактовок. Они и были придуманы, чтобы не было разных определений и многих случаев, чтобы всё подчинялось общему правилу. Так нам (алгебраистам) проще работать. Если начать копаться, то это упрощение, а не усложнение, и всё становится на свои места, ради чего и городится огород.

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

Свойство кольца иметь деление с остатком (и потому алгоритм Евклида) называется евклидовостью, а единственность разложения на простые множители -- факториальностью (не потому что "факториал", а потому что "фактор" -- делитель). И аналогично лемме выше любое евклидово кольцо факториально. Если можете делить с остатком, то можете раскладывать на простые множители. Однако обратное неверно, но это существенно сложнее этого материала, так что за этим лучше обращаться в специальную литературу (по алгебраической геометрии или алгебраической теории чисел).

В моей памяти курсов мехмата и не только эйлеровыми называются целые с $\sqrt{-1}$ , а там история несколько другая, чем $\sqrt{-3}$ .

У меня как-то была история с простыми числами: в ларьке ночью при продаже пива меня продавщица спросила, не могу ли я разложить несколько чисел на простые множители. Она не пыталась взламывать RSA (алгоритм шифрования, основанный на основной теореме арифметики: разложить большое число на простые множители не так-то просто, а сложность задачи может подтвердить, что знающий правильный ответ не смог его подобрать на ходу), а хотела помочь дочери в школе. И ей удалось быстро разобраться, как это делать, чтобы дальше делать самой и объяснить дочери))

Refridgerator
04.07.2023 10:23
#25718332
C комплексными числами можно было придумать пример и поинтереснее. Например: (1+6i)*(1-6i) = 37 (простое число).

klimkinMD
04.07.2023 10:23
#25719504
+1
В сухом остатке:

Так ли очевидна основная теорема арифметики? И всегда ли она верна?
1. Нет, не очевидна, поэтому и теорема (иначе была бы аксиомой:-)).
2. Да, всегда верна. Теорема доказана.
1. MasterMentor
  04.07.2023 10:23
  #25723758
  А что неочевидного?
  
  Определения (аксиомы):
  
  а) "натуральное число" === "целые положительные числа" (далее - "множество N", либо, что тоже самое, вместе с операциями +* и "нулевым элементом" - "поле N")
  
  б) "деление" - бинарная операция обратная "умножению", либо, что то же самое, отношение, ставящее в соответствие подмножеству пар из декартового квадрата NxN число N (далее - "отношение Div").
  
  Отметим, что результат "деления" "закольцован" т.е. полученное "делением" число лежит в N.
  
  в) "простое число" === "натуральное число, котрое отлично от 1 и делится без остатка только на 1 и на само себя" (далее - "множество Np").
  
  То есть "деление" с "условиями" "делится без остатка только на 1 и на само себя" выступает "характеристической функцией", множества Np.
  
  То есть мы имеем набор(ы) "троек" из N, лежащих в подмножестве отношения Div.
  
  Доказательство
  
  По аксиомам задачи N разбито 2 подмножества:
  
  элементы первого лежат в Np
  
  элементы второго не лежат в Np
  
  Для случая 1) теорема доказана.
  
  Путь, применяя операцию "деление" к произвольному числу, мы всегда получаем число, лежащее в 2), и составим ряд из этих чисел. Отметим, что полученный ряд упорядочен и сходится либо к числу "1" либо к числу "2", что есть случай 1).
  
  Для случая 2) теорема доказана.
  
  Конец доказательства. Оно тривиально. :)
  
  PS Конечно, чтобы считать это "математикой" следовало переписать доказательство полностью через отношения т.е. "комбинаторно".

MasterMentor
04.07.2023 10:23
#25722886
>>Эйлер вышел в комплексную плоскость... Он молчаливо предполагал, что для них тоже верна основная теорема арифметики.

Предлагаю не домысливать за "Эйлера". Что Эйлер "предполагал" и посчитал нужным нам сообщить, он изложил в своих работах (книгах).

PS Обоснованно полагаю, что Эйлер был не настолько глуп, чтобы без проверок и доказательств распространять правило, применимое к математически объектам из поля натуральных чисел, к математическим объектам совершенно иной природы - т.н. многокомпонентным конструкциям, которые никакого отношения - ни по своей конструкции - ни по операциями над ними - к натуральным числам не имеют (либо имеют весьма опосредованное отношение).

А то слишком далеко можно пойти: сначала "молчаливо предположить", что все правила для натуральных чисел справедливы для многокомпонентных конструкций (комплексные, гиперкомплексные "числа"). А затем "молчаливо" распространить эти правила на "числа" вроде матриц и тензоров. Почему нет?! :)

VAE
04.07.2023 10:23
#25723312
+1
>>Эйлер вышел в комплексную плоскость и обращался с числами $a+b\sqrt{-3}$ , где $a,b\in \mathbb Z$ , впоследствии названных эйлеровыми

Эти числа не Эйлеровы, а числа Гаусса. Эйлеровы совсем другие числа.