1. Пусть — ненулевой остаток по модулю . Обозначим через следующий остаток по модулю : Тогда по малой теореме Ферма Поэтому Таким образом сравним либо с либо с по модулю . То есть либо 2. Пусть является квадратичным вычетом по модулю . Тогда существует такое число , что Поэтому (по малой теореме Ферма). 3. Рассмотрим многочлен Поэтому, если является квадратичным невычетом по модулю , то .
1. Пусть — ненулевой остаток по модулю . Обозначим через следующий остаток по модулю : Тогда по малой теореме Ферма Поэтому Таким образом сравним либо с либо с по модулю . То есть либо 2. Пусть является квадратичным вычетом по модулю . Тогда существует такое число , что Поэтому (по малой теореме Ферма). 3. Рассмотрим многочлен Как доказано выше, любой квадратичный вычет является его корнем. Так как число — простое, то остатки по модулю образуют поле, поэтому многочлен не может иметь по модулю больше корней чем его степень. Так как число квадратичных вычетов равно , то они и только они являются корнями многочлена Поэтому, если является квадратичным невычетом по модулю , то .