п равно 1. Мы должны доказать, что результат верен для любого натурального числа п; в силу принципа индукции можно предполагать, что предложение уже доказано для всех натуральных чисел, меньших п. Пусть, в частности, нам уже известно, что сумма первых п-1 нечетных чисел равна (п - 1). Сумма первых п нечетных чисел получится из нее добавлением п-го нечетного числа, равного 2п - 1. Таким образом, сумма первых п нечетных чисел есть

(п- 1)2 + 2п- 1,

что равно п. Этим требуемое утверждение доказано.

Доказательства с помош;ью индукции иногда озадачивают неискушенных: «вы предсказываете, какое предложение следует доказывать». Предложения рассматриваемого типа состоят из бесконечного числа частных случаев, каждый из которых соответствует определенному натуральному числу 1, 2, 3, принцип индукции лишь дает возможность предполагать при доказательстве одного из этих случаев, что предшествуюш;ие случаи уже рассмотрены.

Изложение доказательства по индукции в безупречной форме требует некоторого внимания. В приведенном примере доказывалось, что сумма первых п нечетных чисел равна тг. Здесь п - любое натуральное число, и, конечно, утверждение не изменится, если всюду, где встречается п, употреблять какой-нибудь другой символ. Когда мы приступаем к доказательству, п есть вполне определенное число и имеется опасность употребить один и тот же символ в разных смыслах или даже высказать бессмыслицу типа «предложение верно при п, равном п - 1». Чтобы избежать этого, нужно использовать в случае необходимости разные символы.

С обгцелогической точки зрения нет ничего более очевидного, чем законность доказательства по индукции. Тем не менее можно спорить, является ли этот принцип по своей природе определением или аксиомой или это логический принцип. Но, так или иначе, ясно, что принцип индукции служит для того, чтобы расположить натуральные числа в определенном порядке: установив, что вначале идут числа 1, 2, п - 1, мы объявляем следуюш;им числом число п. Таким образом, этот

принцип объясняет, что означают на самом деле слова «и так далее», встречающиеся при попытке перечислить все натуральные числа.

3. Простые числа. Очевидно, что каждое натуральное число а делится на 1 (отношение равно а) и на а (отношение равно 1). Множитель а, отличный от 1 или а, называется собственным множителем. Известно, что существуют числа, не имеющие собственных множителей; они называются простыми числами или простыми. Первые несколько простых таковы:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

Считать ли простым числом 1 - вопрос соглашения, но удобнее (как мы увидим позднее) 1 не считать простым.

Число, не являющееся простым и не равное 1, называется составным; такое число можно представить в виде произведения двух чисел, каждое из которых больше 1. Хорошо известно, что любое составное число можно представить в виде произведения простых; при этом, конечно, некоторые простые могут встретиться по нескольку раз. Возьмем, например, число 666; ясно, что оно делится на 2, и мы получаем 666 = 2 • 333. Далее, 333 имеет очевидный множитель 3, откуда 333 = 3-111. Множитель 111 снова делится на 3, так что 111 = 3 • 37. Следовательно,

666 = 2 . 3 • 3 • 37,

и мы получили представление составного числа 666 в виде произведения простых. Имеется общая теорема о том, что каждое число представимо в виде произведения простых, или, что то же самое, любое число, большее 1, является простым либо разлагается в произведение простых.

Для доказательства этого общего утверждения воспользуемся методом индукции. Докажем утверждение для числа п, считая, что оно уже доказано для любого числа, меньшего п. Если п простое, доказывать нечего. Если п составное, то его можно представить в виде произведения а6, где а и b больше 1 и меньше п. Мы уже знаем, что числа а я b или являются простыми, или разлагаются в произведение простых; подставив их разложения в равенство п = а6, получаем разложение п на простые множители. Это доказательство столь просто, что может

показаться читателю совершенно излишним. Другая обш;ая теорема о разложении на простые будет доказываться уже не так просто.

Ряд простых 2, 3, 5, 7, ... издавна интересовал людей. В дальнейшем мы сформулируем некоторые из полученных в этом направлении результатов. В настояш;ий момент мы ограничимся доказательством того, что ряд простых бесконечен. Это доказательство Евклида (книга IX, предложение 20) может служить образцом изяш;ества и простоты. Пусть 2, 3, 5, ...,Р - ряд простых до некоторого простого Р. Рассмотрим произведение всех этих простых, добавим к нему 1 и положим

7V = 2.3-5... Р + 1.

Это число не может делиться на 2, так как если бы оно делилось на 2, то и 2.3.5 ... Р, а потому и разность 7V-2.3.5 ... Р делились бы на 2. Но разность этих чисел равна 1 и на 2 не делится. Аналогично убеждаемся в том, что N не может делиться на 3, на 5 и вообгце ни на какое другое простое вплоть до Р. С другой стороны, N должно делиться на какое-нибудь простое (на само себя, если N простое, или на любой простой делитель 7V, если N составное). Следовательно, суш;ествует простое число, отличное от любого из простых 2, 3, 5, ..., Р и потому большее Р. Таким образом, ряд простых оборваться не может.

4. Основная теорема арифметики. В предыдуш;ем пункте было доказано, что любое составное число представимо в виде произведения простых. В качестве примера мы разложили на множители число 666: 666 = 2 . 3 . 3 . 37. Обратимся теперь к другому вопросу, также имеюгцему первостепенное значение. Можно ли осугцествить разложение на простые более чем одним способом? (Понятно, конечно, что два представления, отличаю-ш;иеся только порядком множителей, должны рассматриваться как одно, например разложение 3 . 2 . 37 . 3 отождествляется с разложением 2.3.3. 37.) Может ли, например, число 666 иметь какое-нибудь другое представление в виде произведения простых? Читатель, не знаюш;ий теории чисел, вероятно, будет все же уверен, что другого такого представления нет, однако найти слишком простое обш,ее доказательство ему не удастся.