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

В теории чисел, касающихся простых чисел

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

Пусть p — нечетное простое число, а a — целое число, взаимно простое с p . Тогда ^{[1] [2] [3]}

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&{\text{ if there is an integer }}x{\text{ such that }}x^{2}\equiv a{\pmod {p}},\\-1{\pmod {p}}&{\text{ if there is no such integer.}}\end{cases}}}$

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

${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.}$

Критерий восходит к статье Леонарда Эйлера 1748 года . ^{[5] [6]}

Доказательство

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

Поскольку модуль является простым числом, применима теорема Лагранжа : многочлен степени k может иметь не более k корней. В частности, x ² ≡ a (mod p ) имеет не более 2 решений для каждого a . Это немедленно подразумевает, что помимо 0 существует по крайней мере ⁠п − 1/2⁠ различные квадратичные вычеты по модулю p : каждое из p − 1 возможных значений x может сопровождаться только одним другим, чтобы дать тот же самый вычет.

На самом деле, это происходит потому , что различные квадратичные вычеты таковы: ${\displaystyle (p-x)^{2}\equiv x^{2}{\pmod {p}}.}$ ${\displaystyle (p-x)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}.}$ ${\displaystyle {\tfrac {p-1}{2}}}$ ${\displaystyle 1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}.}$

Так как a взаимно просто с p , малая теорема Ферма гласит, что

${\displaystyle a^{p-1}\equiv 1{\pmod {p}},}$

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

${\displaystyle \left(a^{\tfrac {p-1}{2}}-1\right)\left(a^{\tfrac {p-1}{2}}+1\right)\equiv 0{\pmod {p}}.}$

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

${\displaystyle a^{\tfrac {p-1}{2}}\equiv 1{\pmod {p}}}$или

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {-1}{\pmod {p}}.}$

Теперь, если a — квадратичный вычет, a ≡ x ² ,

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {(x^{2})}^{\tfrac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}.}$

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

Применяя теорему Лагранжа еще раз, замечаем, что не может быть больше ⁠п − 1/2⁠ значения a , которые делают первый фактор равным нулю. Но как мы отметили в начале, есть по крайней мере ⁠п − 1/2⁠ различных квадратичных вычетов (mod p ) (кроме 0). Следовательно, они являются именно теми классами вычетов, которые делают первый множитель нулевым. Другой ⁠п − 1/2⁠ классы вычетов, невычеты, должны сделать второй множитель нулевым, иначе они не удовлетворят малой теореме Ферма. Это критерий Эйлера.

Альтернативное доказательство

Это доказательство использует только тот факт, что любое сравнение имеет единственное (по модулю ) решение при условии, что не делит . (Это верно, потому что пробегает все ненулевые остатки по модулю без повторений, так же как и : если у нас есть , то , следовательно , ​​но и не сравнимы по модулю .) Из этого факта следует, что все ненулевые остатки по модулю , квадрат которых не сравним, можно сгруппировать в неупорядоченные пары в соответствии с правилом, что произведение членов каждой пары сравнимо по модулю (так как по этому факту для каждого мы можем найти такое , однозначно, и наоборот, и они будут отличаться друг от друга, если не сравнимо ). Если не является квадратичным вычетом, то это просто перегруппировка всех ненулевых остатков в пары, отсюда мы заключаем, что . Если является квадратичным вычетом, ровно два остатка не были среди парных, и таких, что . Если мы спарим эти два отсутствующих остатка вместе, их произведение будет скорее, чем , откуда в этом случае . Подводя итог, рассмотрев эти два случая, мы продемонстрировали, что для имеем . Остается подставить (что, очевидно, является квадратом) в эту формулу, чтобы получить сразу теорему Вильсона , критерий Эйлера и (возводя в квадрат обе части критерия Эйлера) малую теорему Ферма . ${\displaystyle kx\equiv l\!\!\!{\pmod {p}}}$ ${\displaystyle p}$ ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle kx}$ ${\displaystyle kx_{1}\equiv kx_{2}{\pmod {p}}}$ ${\displaystyle p\mid k(x_{1}-x_{2})}$ ${\displaystyle p\mid (x_{1}-x_{2})}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle (x,y)}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y^{2}}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle p-1}$ ${\displaystyle (p-1)/2}$ ${\displaystyle 1\cdot 2\cdot ...\cdot (p-1)\equiv a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}}$ ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle -r}$ ${\displaystyle r^{2}\equiv a\!\!\!{\pmod {p}}}$ ${\displaystyle -a}$ ${\displaystyle a}$ ${\displaystyle 1\cdot 2\cdot ...\cdot (p-1)\equiv -a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}}$ ${\displaystyle a\not \equiv 0\!\!\!{\pmod {p}}}$ ${\displaystyle 1\cdot 2\cdot ...\cdot (p-1)\equiv -\left({\frac {a}{p}}\right)a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}}$ ${\displaystyle a=1}$

Примеры

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

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

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

В одном случае, проверяя p = 3, мы имеем 17 ^{(3 − 1)/2} = 17 ¹ ≡ 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 ² = 1

2 ² = 4

3 ² = 9

4 ² = 16

5 ² = 25 ≡ 8 (мод 17)

6 ² = 36 ≡ 2 (мод 17)

7 ² = 49 ≡ 15 (мод 17)

8 ² = 64 ≡ 13 (мод 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 ⁸ ≡ 1 (mod 17), поэтому это квадратичный вычет. Чтобы проверить, является ли 3 квадратичным вычетом по модулю 17, мы вычисляем 3 ^{(17 − 1)/2} = 3 ⁸ ≡ 16 ≡ −1 (mod 17), поэтому это не квадратичный вычет.

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

Приложения

На практике эффективнее использовать расширенный вариант алгоритма Евклида для вычисления символа Якоби . Если — нечетное простое число, то оно равно символу Лежандра и определяет, является ли оно квадратичным вычетом по модулю . ${\displaystyle \left({\frac {a}{n}}\right)}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$

С другой стороны, поскольку эквивалентность символу Якоби справедлива для всех нечетных простых чисел, но не обязательно для составных чисел, вычисление обоих и их сравнение можно использовать в качестве теста на простоту, в частности, теста на простоту Соловея–Штрассена . Составные числа, для которых сравнение справедливо для заданного числа , называются псевдопростыми числами Эйлера–Якоби по основанию . ${\displaystyle a^{\frac {n-1}{2}}}$ ${\displaystyle a}$ ${\displaystyle a}$

Примечания

1. Гаусс , DA, Статья 106
2. Денс, Джозеф Б.; Денс, Томас П. (1999). "Теорема 6.4, Глава 6. Вычеты". Элементы теории чисел . Harcourt Academic Press. стр. 197. ISBN 9780122091308.
3. Леонард Юджин Диксон, «История теории чисел», т. 1, стр. 205, Chelsea Publishing, 1952 г.
4. Харди и Райт, том 83
5. Леммермейер, стр. 4 цитирует две статьи, E134 и E262 в архиве Эйлера.
6. Л. Эйлер, Новые комментарии Academiae Scientiarum Imperialis Petropolitanae, 8, 1760-1, 74; Опусский анал. 1, 1772, 121; Комм. Ариф, 1, 274, 487

Ссылки

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

• Гаусс, Карл Фридрих (1986), Disquisitiones Arithemeticae (второе, исправленное издание) , перевод Кларка, Артура А. (на английском языке), Нью-Йорк: Springer , ISBN 0-387-96254-9

• Гаусс, Карл Фридрих (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithemeticae и другие статьи по теории чисел) (второе издание) , перевод Мазера Х. (немецкий), Нью-Йорк: Челси, ISBN 0-8284-0191-8

• Харди, Г. Х.; Райт , Э. М. (1980), Введение в теорию чисел (пятое издание) , Оксфорд: Oxford University Press , ISBN 978-0-19-853171-5

• Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Берлин: Springer , ISBN 3-540-66957-4

Внешние ссылки

• Архив Эйлера