остающемся верным лишь при условии, что сокращаемый множитель отличен от нуля:

если ах - ау, то х = у при а 0. Таким образом, целые числа (положительные, отрицательные и нуль) удовлетворяют тем же арифметическим законам, что и натуральные числа, но теперь вычитание уже всегда выполнимо; кроме того, закон порядка и второй закон сокращения должны быть изменены только что указанным способом. Натуральные числа можно теперь описать как целые положительные числа.

Вернемся к натуральным числам. Как мы уже знаем, в системе натуральных чисел деление выполнимо не всегда. Если натуральное число b можно разделить на натуральное число а в системе натуральных чисел, то говорят, что а является множителем или делителем b или что b является кратным а. В качестве иллюстрации к этому определению отметим, что 1 является множителем каждого числа и что а является множителем а (отношение равно 1). В качестве другого примера заметим, что числа, делящиеся на 2, называются четными: 2, 4, 6, ..., а числа, не делящиеся на 2, - нечетными: 1, 3, 5, ... .

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

L Если а делит Ь, то а b (т. е. а или меньше, или равно 6). Действительно, если b = ах то 6 - а = а{х - 1), где х - 1 либо равно О, либо является натуральным числом.

П. Если а делит bub делит с, то а делит с. В самом деле, при b - ах VL с - by имеем с = а{ху) где х я у - натуральные числа.

1П. Если каждое из чисел b и с делится на а, то b + с и b - с (если с < Ь) также делятся на а. Действительно, при b = ах и с = ау будет Ь + с = а{х + у) и b - с = а{х - у).

Ограничение b > с при рассмотрении Ь-св последнем утверждении становится излишним, если очевидным образом распространить отношение делимости на все целые числа: целое число

b делится на натуральное а, если отношение является целым числом. Таким образом, отрицательное число -Ь делится на а тогда и только тогда, когда b делится на а. Заметим, что О делится на любое натуральное число (отношением служит целое число 0).

IV. Если целые числа b и с делятся на натуральное число

то и каждое число, представимое в виде иЬ + vc, где и и V - целые числа, делится на а. При Ь = ах и с = ау получим иЬ + vc= {их + vy)a. Это свойство включает результаты, сформулированные в III как частные случаи: полагая и и v равными 1, получаем Ь + с = ub + vc; полагая и равным 1, а г; равным -1, получаем иЬ + vc = b - с.

Так же как с введением О и отрицательных чисел оказывается всегда возможным вычитание, расширение системы натуральных чисел путем введения положительных дробей, т. е. всевозможных дробей вида а/6, где а и b - натуральные числа, делает возможным деление на любое число. Комбинируя эти методы, получим систему рациональных чисел которая состоит из всех целых чисел и всех дробей, как положительных, так и отрицательных. В этой числовой системе выполнимы все четыре арифметических действия - сложение, умножение, вычитание и деление, за исключением деления на нуль.

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

2. Доказательство по индукции. Большинство предложений теории чисел являются утверждениями о произвольном натуральном числе; например, теорема Лагранжа говорит о том, что каждое натуральное число есть сумма не более четырех квадратов. Как же доказать, что некоторое утверждение истинно для любого натурального числа? Конечно, некоторые утверждения непосредственно вытекают из законов арифметики; таковы, например, алгебраические тождества типа

(n + l) = n + 2n + l.

Но более интересные и более арифметические по своей природе утверждения не столь просты.

Ясно, что мы никогда не докажем общего предложения, последовательно убеждаясь в его истинности для 1, 2, 3 и так далее, ибо нельзя перебрать бесконечного числа возможностей. Установив, что утверждение верно для любого числа, меньшего миллиона или миллиона миллионов, мы не приблизимся к доказательству того, что оно верно всегда. (Иногда, правда, бывает, что некоторые предложения теории чисел, установленные путем вычислений для большого числа частных случаев, оказываются верными в довольно широкой области.)

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

Если это доказано, то из истинности нашего предложения для числа 1 следует, что оно верно для числа 2, из того, что оно верно для 1 и 2, вытекает, что оно верно для 3, и так далее до бесконечности. Это предложение будет поэтому верным для любого числа, если оно верно для числа 1.

В этом и состоит принцип доказательства по индукции, который относится к предложениям о том, что что-то верно для любого натурального числа. Чтобы применить этот принцип, необходимо доказать две вещи: во-первых, нужно доказать, что предложение верно для 1, а во-вторых, что если предложение верно для каждого из чисел 1, 2, п - 1, меньших п, то оно верно и для числа п. Установив эти факты, мы заключаем, что доказываемое предложение верно для любого натурального числа.

Простой пример проиллюстрирует этот принцип. Будем изучать отрезки ряда 1 + 3 + 5 + ... последовательных нечетных чисел. Легко заметить, что

1 = 1 1 + 3 = 2 1 + 3 + 5 = 3 1+ 3 + 5 + 7 = 4 и т. д.

Этим подсказывается общее утверждение: при любом натуральном п сумма первых п нечетных чисел равна т?. Докажем это общее предложение по индукции. Оно, конечно, верно, если