Глава 3. Разложение на множители

Стратегия «разделяй и властвуй» очень популярна в науке. Например, любое вещество разложимо на составляющие, на атомы. Более того, если свойства атомов хорошо известны, они многое говорят и о свойствах самого вещества.

Нечто похожее происходит и в целых числах. В этом случае роль атомов играют простые числа, а любое целое число раскладывается в произведение простых. Разложение служит главным инструментом в доказательстве многих свойств простых чисел. Найти разложение данного числа, однако, не всегда легко. Если число очень велико, то процедура его разложения может потребовать длительного времени, и она предъявляет большие требования к мощности компьютера.

§ 3.1. Теорема о разложении

Начнем со строгого определения главных героев. Целое число называется простым, если и единственными его делителями являются числа и Так, числа 2,3,5 и —7 простые, а число нет. Почти всюду в книге мы будем использовать определение в несколько более узком смысле, называя простым положительное простое число. Целое

число, отличное от ±1 и не простое, называется составным, или разложимым. Для составного числа существуют такие целые числа a и b, что Значит, число 45 составное.

Заметим, что числа ±1 не являются ни составными, ни простыми. Они относятся к третьей группе — это единственные целые числа, у которых есть целые обратные. В конце этого параграфа мы сможем более убедительно объяснить, почему их не следует считать простыми.

Теорема о разложении на множители. Всякое целое число единственным образом записывается в виде

где простые числа, натуральные числа.

Эта теорема настолько важна, что ее иногда называют основной теоремой арифметики. Впервые в таком виде она сформулирована Гауссом в § 16 его «Арифметических исследований», что не мешало, однако, его предшественникам неявно использовать ее. Как пишут Харди (Hardy) и Райт (Wright) в своей книге по теории чисел, «Гаусс первым превратил арифметику в систематическую науку», см. [23].

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

Теорема содержит два различных утверждения. Во-первых, всякое целое число можно представить в виде произведения степеней простых чисел. Во-вторых, простые сомножители и их степени в разложении определены однозначно. Значит, нам нужно доказать две вещи: разложение существует, и оно единственно. Мы докажем их по отдельности. Как мы увидим,

существование разложения доказать несложно, а вот его единственность — гораздо более тонкий факт.

После того, как теорема о разложении сформулирована, нам легче объяснить, почему ±1 не следует считать простыми. Если включить их в число простых, то разложение на простые сомножители потеряет свойство единственности. Действительно, если число 1 простое, то два различных разложения числа 2 на простые сомножители. Тот же самый трюк с привлечением различных степеней числа 1 (или —1) дает бесконечно много разложений для любого целого числа. С целью избежать этих псевдоразложений (множество которых бесконечно и бессмысленно), мы и исключаем ±1 из определения простого числа.