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

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

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

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 ]}

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

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

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

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

Поскольку модуль простой, применима теорема Лагранжа : многочлен степени $k$ может иметь не более $k$ корней. В частности, $х 2 \equiv a (mod p)$ имеет не более 2 решений для каждого $a$ . Отсюда сразу следует, что кроме 0 существует по крайней мере $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ p - 1/2 . ⁠$ различные квадратичные вычеты по модулю $p$ : каждое из $p - 1$ возможных значений $x$ может сопровождаться только одним другим, чтобы дать один и тот же вычет

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

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

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

который можно записать как

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

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

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

или

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

Теперь, если $a$ — квадратичный вычет, $a \equiv x 2$ ,

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

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

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

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

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

Примеры

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

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

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

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

В другом случае, проверяя p = 13, мы имеем 17 ^{(13 − 1)/2} = 17 ⁶ ≡ 1 (по модулю 13), следовательно, 17 — квадратичный вычет по модулю 13. В качестве подтверждения отметим, что 17 ≡ 4 (по модулю 13), а 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 (по модулю 17), поэтому 9 ² ≡ (−8) ² = 64 ≡ 13 (по модулю 17)).

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

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

Приложения

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

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

Примечания

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

Ссылки

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

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

Гаусс, Карл Фридрих (1965), Исследования по высшей арифметике (Disquisitiones Arithemeticae и другие статьи по теории чисел) (второе издание) , перевод Мазера Х. (немецкий), Нью-Йорк: Челси, ISBN 0-8284-0191-8

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

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

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

Архив Эйлера

[1] Гаусс Д.А., Ст. 106

[2] Плотный, Джозеф Б.; Денс, Томас П. (1999). «Теорема 6.4, гл. 6. Вычеты» . Элементы теории чисел . Харкорт Академик Пресс. п. 197. ИСБН 9780122091308 .

[3] Леонард Юджин Диксон, «История теории чисел», том 1, стр. 205, Chelsea Publishing, 1952 г.

[4] Харди и Райт, thm. 83

[5] Леммермейер, с. 4 цитирует две статьи, E134 и E262, из Архива Эйлера.

[6] Л. Эйлер, Новые комментарии Императорской Петрополитанской академии наук, 8, 1760-1, 74; Опус Анал. 1, 1772, 121; Комм. Ариф, 1, 274, 487

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]