Побудова простих великих чисел (стр. 4 из 4)

Зазначимо, що переконатися, що задане число не є повним квадратом, можна, обчисливши символ Лежандра для декількох маленьких простих модулів. Якщо при деякому модулі число не буде квадратичним відрахуванням, то воно не буде й повним квадратом.

Нехай

– функція Ейлера.

Лема 4. Нехай

– просте число й . Позначимо через число елементів , порядок яких ділиться на . Тоді справедлива оцінка

,

причому рівність виконується в тому й у тільки в тому випадку, коли

Доведення. Використовуючи властивості функції Ейлера, отримуємо

причому рівність виконана в тому і тільки в тому випадку, коли