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

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

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

После перестановки множителей получается то же разложение, что и выше, но будет ли так всегда? Многие не понимают, почему это не очевидно и надо доказывать. Лучший способ понять, что этот факт не очевиден, — показать примеры, когда он… неверен! Как это? Оказывается, существуют числовые (и не только) системы, в которых нет единственности разложения. По-видимому, исторически первые примеры связаны с попытками доказать Великую проблему Ферма: уравнение x^n+y^n=z^n неразрешимо в натуральных числах ни для какого натурального $n\geq 3$ . Так, при n=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$ ).
Простое число в — это число p>1» src=«https://habrastorage.org/getpro/habr/upload_files/dc9/740/e94/dc9740e94c6ba3bbd664e1347878540a.svg» />со свойством: если<img alt= не делятся на, то не делится на .

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

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

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

Задача 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.$

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

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

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

Доказательство леммы в $\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) называется соотношением Безу .
Из этой теоремы уже легко следует наша лемма.

Доказательство леммы. Так как не делит , то (a,p)=1 . По теореме au+pv=1 для некоторых $u,v\in \mathbb Z$ . Умножим на : abu+bpv=b . Так как не делится на , bpv делится на , то abu не делится на . Тем более, не делится на .

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

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

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