288

ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ

что невозможно, так как ни один из множителей левой части не

может делиться на р.

Это важное предложение, весьма сближающее теорию алгебра.

ических сравнений по простому модулю с теорией алгебраических

уравнений, теряет силу в случае составного модуля: мы уже видели,

что сравнение первой степени по составному модулю может иметь

более одного решения.

Теорема Ферма даёт нам очень ценный пример такого типа

сравнений, число решений которых всегда равно показателю сте-

пени. В самом деле, согласно этой теореме сравнению

0 (mod р)

при любом простом р удовлетворяют все числа, не делящиеся на р;

но эти числа по модулю р образуют р — 1 классов, так что срав-

нение (14) действительно при любом простом р имеет р— 1 реше-

нии. Как мы уже знаем, отсюда следует, что тождественно выпол-

няется сравнение

хР¯1 — 1 (х— 1 ) (х— 2) ...

(х— р -1- 1) (modp).

Полагая в этом сравнении мы находим:

1 = 1 у- 1 (р— 1)! (mod р);

если р то (— 1, и следовательно,

(р — О (mod р);

но при р сравнение (15) получает вид

(mod 2)

(15)

и, следовательно, также имеет место. Таким образом, сравнение

(15) выполняется для любого простого р; это составляет содержание

известной теоремы Вильсон а, дающей своеобразный критерии

для простых чисел. Дело в том, что ни для одного составного

числа сравнение (15) не может иметь места, так как при состав-

ном р, как легко убедиться, (р — 1)! —1— 1 никогда не может делиться

на р 1). Правда, этот критерии Вильсона до сих пор не удалосй

использовать ни для каких теоретических выводов; тем не менее

сам по себе он представляет значительный интерес.

Однако теорема Ферма приводит в этом круге идей и к другим:

более общим и важным выводам. Умножая обе части сравнения

хР-1 1 (mod р)

(выполняющегося согласно теореме Ферма для всех х, не

1) В самом деле, если р имеет такой делитель d, что 1 то,

очевидно, (р— 1)! делится на d; но тогда (р— -1- 1 не может делиться

на d» а тем более на р.