Есть число n, случайное число. Нужно найти квадратичные вычеты по модулю n

Если n нечетное и a является кратным n, то a не имеет квадратичных вычетов по модулю n.

Если n нечетное и a не кратно n, то сначала нужно определить символ Якоби (a/n):

Если символ Якоби равен 0, то a не является квадратичным вычетом по модулю n.

Если символ Якоби равен 1, то a является квадратичным вычетом по модулю n.

Если символ Якоби равен -1, то a является квадратичным невычетом по модулю n.

Для любого четного модуля n, любое целое число a имеет квадратичные вычеты по модулю n.

Пример:

Пусть n = 13 и a = 7. Тогда символ Якоби (7/13) равен 1, что означает, что 7 является квадратичным вычетом по модулю 13.

Если бы n было четным, то любое целое число a имело бы квадратичные вычеты по модулю n.