Критерий Эйлера

В теории чисел критерий Эйлера — это формула для определения того, является ли целое число квадратичным вычетом по модулю простого числа.

Пусть p — нечётное простое число, и a — целое число, взаимно простое с p. Тогда

Критерий Эйлера можно кратко записать, используя символ Лежандра:

Критерий датируется 1748 годом, когда была написана работа Леонарда Эйлера.

Доказательство Доказательство использует тот факт, что класс вычетов по модулю простого числа представляет собой поле.

Поскольку модуль является простым, применима теорема Лагранжа: многочлен степени может иметь не более корней (по модулю ). В частности, имеет 2 или меньше корней для каждого . Это сразу же подразумевает, что помимо 0 существует как минимум различных квадратичных вычетов по модулю : каждый из возможных остатков может составить пару с другим остатком.

А именно, Это потому что Итак, различные квадратичные вычеты суть:

Когда взаимно просто с , малая теорема Ферма гласит, что

что можно записать как

Поскольку целые числа по модулю образуют поле, для каждого один или другой множитель должен быть равен нулю. Поэтому,

или

Теперь, если — квадратичный вычет, то и

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

Применяя теорему Лагранжа, мы замечаем, что не может быть больше, чем значений , которые делают первый множитель нулевым. Но, как мы отметили в начале, есть по крайней мере различных квадратичных вычетов. Поэтому именно эти классы остатков обращают первый сомножитель в нуль. Другие классов остатков - невычеты, должны обнулять второй сомножитель, иначе они не удовлетворяют малой теореме Ферма. В результате критерий Эйлера доказан.

Альтернативное доказательство Это доказательство использует только тот факт, что любое сравнение имеет единственное (по модулю ) решение при условии, что не делит . (Это верно, потому что если пробегает все ненулевые остатки по модулю без повторений, то тоже: предположив , получим , следовательно , но и не совпадают по модулю .) Из этого факта следует, что все ненулевые остатки по модулю , квадрат которых не сравним с , могут быть сгруппированы в неупорядоченные пары в соответствии с правилом, согласно которому произведение членов каждой пары равно по модулю (т.к. поэтому для каждого мы можем однозначно найти такое значение , и наоборот, и они будут отличаться друг от друга, если не будет сравнимо с ). Если не квадратичный вычет, то это просто перегруппировка всех ненулевых остатков в пары, отсюда мы делаем вывод, что . Если - квадратичный остаток, то ровно два остатка не объединились в пары: и такие, что . Если мы соединим эти два отсутствующих остатка вместе, то их произведение будет равно , и это приведёт к итоговому произведению . Подводя итог, рассматривая эти два случая, мы продемонстрировали, что у нас есть . Остается подставить (что, очевидно, является квадратом) в эту формулу, чтобы получить сразу теорему Вильсона, критерий Эйлера и (возведя в квадрат обе части критерия Эйлера) малую теорему Ферма.

Примеры Пример 1: Нахождение простых чисел, для которых a является остатком

Пусть a = 17. Для каких простых чисел p является квадратичным вычетом 17?

Мы можем проверить простые числа p вручную, используя формулу выше.

В одном случае при проверке p = 3 имеем 17 (3 − 1)/2 = 17 1 ≡ 2 ≡ −1 (mod 3), поэтому 17 не является квадратичным вычетом по модулю 3.

В другом случае, проверяя p = 13, мы имеем 17 (13 − 1)/2 = 17 · 6 ≡ 1 (mod 13), поэтому 17 является квадратичным вычетом по модулю 13. В качестве подтверждения отметим, что 17 ≡ 4 (mod 13) и 2 · 2 = 4.

Мы можем выполнять эти вычисления быстрее, используя различные свойства модульной арифметики и символов Лежандра.

Если мы продолжим вычислять значения, то обнаружим:

(17/ p ) = +1 для p = {13, 19, ...} (17 — квадратичный вычет по модулю этих значений)

(17/ p ) = −1 для p = {3, 5, 7, 11, 23, ...} (17 не является квадратичным вычетом по модулю этих значений).

Пример 2: Нахождение остатков при заданном простом модуле p.

Какие числа являются квадратами по модулю 17 (квадратичные вычеты по модулю 17)?

Мы можем вычислить это вручную следующим образом:

1 2 = 1 2 2 = 4 3 2 = 9 4 2 = 16 5² = 25 ≡ 8 (mod 17) 6² = 36 ≡ 2 (mod 17) 7 2 = 49 ≡ 15 (mod 17) 8 2 = 64 ≡ 13 (mod 17).

Таким образом, множество квадратичных вычетов по модулю 17 — это {1,2,4,8,9,13,15,16}. Заметим, что нам не нужно было вычислять квадраты для значений от 9 до 16, поскольку все они являются отрицательными значениями ранее возведенных в квадрат (например, 9 ≡ −8 (mod 17), поэтому 9² ≡ (−8) ² = 64 ≡ 13 (mod 17)).

Мы можем найти квадратичные вычеты или проверить их, используя приведенную выше формулу. Чтобы проверить, является ли 2 квадратичным вычетом по модулю 17, мы вычисляем 2 (17 − 1)/2 = 2 8 ≡ 1 (mod 17), следовательно, это квадратичный вычет. Чтобы проверить, является ли 3 квадратичным вычетом по модулю 17, мы вычисляем 3 (17 − 1)/2 = 3 8 ≡ 16 ≡ −1 (mod 17), следовательно, это не квадратичный вычет.

Критерий Эйлера связан с законом квадратичной взаимности .

Приложения На практике эффективнее использовать расширенный вариант алгоритма Евклида для вычисления символа Якоби. . Если нечётное простое число, оно равно символу Лежандра и определяет, является ли квадратичным вычетом по модулю .

С другой стороны, поскольку эквивалентен символу Якоби для всех нечётных простых чисел, но не всегда для составных чисел; вычисление обоих показателей и их сравнение может использоваться в качестве теста на простоту, в частности, теста Соловея-Штрассена. Составные числа, для которых выполняется тесты совпадают для числа называются псевдопростыми числами Эйлера-Якоби по основанию .

Примечания

Литература Михелович М.Х. Теория чисел. 1967. §3.9. с. 107—109

«Disquisitiones Arithmeticae» переведено с цицероновской латыни Гаусса на английский и немецкий языки . Немецкое издание включает все его работы по теории чисел: все доказательства квадратичного закона взаимности, определение знака суммы Гаусса, исследования биквадратичного закона взаимности и неопубликованные заметки.

Внешние ссылки Архив Эйлера

Категория:Объекты, названные в честь Леонарда Эйлера Категория:Теоремы о простых числах Категория:Модульная арифметика Категория:Википедия:Страницы с непроверенными переводами