Квадратичные вычеты

Если сравнение не имеет решений относительно то и сравнение

не имеет решений относительно Ясно, что любой остаток по модулю представим, как для некоторого но тогда не существует такого остатка что но тогда квадратичный невычет по модулю

Второе число можно представить как

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

имело решения. Предположим противное, но тогда

С другой стороны, в силу того, что является квадратичным невычетом по модулю верно, что

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

Замечание. Разложение

можно получить, введя замену тогда

Осталось перейти к обратной замене и домножить содержимое каждой из скобок на