ГЛАВА I. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ЧИСЕЛ

В этой главе излагаются в конспективном виде основные понятия классической теории чисел.

§ 1. Разложение чисел на простые множители; алгорифм Евклида.

Если даны два целых числа и отношение число целое, то говорят, что а делится на или а кратно или что делитель а. Число называется простым, если оно не имеет других делителей, кроме очевидных Как составляются все целые числа из простых чисел, указывает следующая основная теорема:

Теорема 1. Каждое целое число представляется и притом единственным способом в виде произведения равных или неравных простых множителей.

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

в которых целые числа, причем

Равенства (1) представляют не что иное, как разложение -у в обыкновенную непрерывную дробь:

Из них выводим: 1) что делит а и 2) что всякий общий делитель делит Следовательно, исключая из и пользуясь свойствами непрерывных дробей, получаем где суть числитель и знаменатель предпоследней подходящей к дроби 2). Таким образом приходим к классическому решению уравнения в целых числах при помощи непрерывных дробей.

При числа называются взаимно простыми. В этом случае из уравнения видно, что при делимости на цйюе число с должно делиться на что и приводит к теореме 1.

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

Относительно распределения простых чисел в ряду натуральных чисел не известно никаких точных законов. Отметим лишь важное предложение, доказанное еще в "Началах" Евклида (кн. IX, 20) (см. А. А. Васильев 85, стр. 27—44):

Теорема 2. Число простых чисел бесконечно.

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