19. Разложение простого числа на сумму двух квадратов

Пусть теперь обозначает простое число вида Принимая во внимание четность числа найдем, что число

при делении на дает, очевидно, такой же остаток, как число

Но последнее число, если его сомножители записать в обратном порядке, можно представить в виде

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

Теорема 16. Если есть простое число вида то число делится на

Для вывода следствия из этой теоремы нам понадобится следующая

Лемма. Если простое число и — целое число, не делящееся на то существуют натуральные числа такие, что при соответствующем знаке или — число делится на

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

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

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

Теорема 17 (Ферма). Каждое простое число вида есть сумма двух квадратов натуральных чисел.

Так, например,

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

Теорема 18. Пусть а и данные натуральные числа, тогда ни одно простое число нельзя представить двумя различными способами в форме где х и у — натуральные числа, если в случае не обращать внимания на порядок слагаемых.

Доказательство. Предположим, что простое число допускает два разложения:

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

Но Таким образом, по крайней мере один из сомножителей левой части должен делиться на простое число

Если Ьууи то из первого выражения для следует, что должно быть следовательно, Ьууи откуда а значит,

Если же ухи то из второго выражения для следует, что

причем последнее, если учесть, что числа являются натуральными, возможно только, тогда, когда Поэтому имеем что дает нам равенство откуда следовательно (принимая во внимание, что Таким образом, наши разложения отличаются одно от другого только порядком слагаемых. Теорема 18 доказана.

Из теоремы 18 тотчас же следует, что если натуральное число можно представить хотя бы двумя способами в виде суммы двух квадратов натуральных чисел (при условии, что два разложения, отличающиеся только порядком слагаемых, не считаются различными), то не является простым числом. Поэтому, например, из того что мы заключаем, что число 2501 не является простым.

Пусть — натуральные числа. Имеем

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

Если тип — натуральные числа, из которых по крайней мере одно отлично от единицы, то число является составным.

В частности (для отсюда следует, что все числа вида где натуральное число являются составными.

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

В частности, совершенно элементарно можно получить следующее разложение на множители

Заметим, однако, что если натуральное число допускает только одно разложение на сумму двух квадратов натуральных чисел, то отсюда еще не следует, что оно должно быть простым числом. Например, как легко убедиться, числа 10, 18, 45 дают каждое только одно разложение:

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

причем в этом разложении слагаемые не имеют общего делителя

О числах для известно, что они являются составными. В 1956 г. П. Эрдеш поставил вопрос, все ли числа для натуральных составные. Ответ на этот вопрос, как мы видим, отрицателен.

Числа являются составными для ибо они, как это было подтверждено, делятся соответственно на 3, 5, 3, 107, 3, 5, 3, 11, 3, 61, 3. Таким образом, среди чисел для натуральных где имеется только одно простое (для

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

Мы не знаем, существует ли бесконечное множество натуральных чисел для которых число является простым.

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

Число 2 имеет, очевидно, только одно представление в виде суммы двух квадратов натуральных чисел: Таким образом, остается еще исследовать простые числа вида (где . Легко доказать, что ни одно натуральное число этого вида не может быть представлено в виде суммы двух квадратов целых чисел. Действительно, поскольку это число нечетное, то в случае целые числа х и у не могли бы быть оба четными или же нечетными. Таким образом, одно из них должно быть четным, а другое нечетным. Но квадрат четного числа при делении на 4 дает в остатке нуль, квадрат же нечетного — единицу. Следовательно, сумма при делении на 4 дала бы в остатке 1, в то время как число дает в остатке 3. Формула таким образом, оказывается невозможной при целых х и у.

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

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

Исследован также вопрос, сколько данное натуральное число дает разложений на суммы двух квадратов натуральных чисел. Оказывается, это зависит от разложения числа на простые сомножители. Можно доказать, что существуют натуральные числа, дающие произвольно много разложений на суммы двух квадратов натуральных чисел. Число 65 дает два разложения на суммы двух квадратов:

число 1105 дает четыре таких разложения: