Двучленные сравнения — сравнения вида axⁿ≡b(mod m). (l)

Если (a,m)= 1, то сравнение (1) можно привести к еще более простому виду. Взяв с такое, что ас ≡ l(mod m), и умножив обе части сравнения (1) на с (оно взаимно просто с m), получим хⁿ≡bс(mod m). Будем рассматривать сравнения такого вида по простому модулю р, отличному от 2, то есть сравнения вида x² ≡ a(mod р). (2)

Теорема 1. Сравнение 2-ой степени ax²+bx+c≡0(mod p), где р — простое, р > 2, может быть сведено к двучленному сравнению (2).

Доказательство. Действительно, умножим обе части сравнения на 4a (взаимно простое с модулем). Имеем 4a²x² + 4abx +4ac≡0(mod p),

(2ax + b)² ≡-4ас + b²(mod р). Обозначив 2ax+b= у, b² -4aс = d, получим у² ≡ d(mod р).

Примеры. 1.

Решить сравнение Зх² + 7x+ 8 ≡0(mod 17).

36х² + 12*7х+ 12*8 ≡ 0(modl7), (6х + 7)² ≡49-96(mod 17), (6х + 7)² ≡ -47 + 5l(mod l7), (6х + 7)² ≡4(mod l7), (6x+7)≡±2(mod17).

6x≡-5 +17(mod 17), x≡ 2(mod 17) или 6x ≡ -9(mod17), 2x≡ -3 +17(mod 17), x ≡ 7(mod 17).

Ответ: x ≡ 2(mod 17), x ≡ 7(mod 17).

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

сравнений. Зх² +24x-9 ≡ 0(mod l7) (здесь вместо 7 взяли 24, а вместо 8 число -9), х² +.8х-3 ≡ 0(mod 17), (х + 4)² ≡ 19 +17(mod 17),

(Х + 4) ≡ ±6(mod 17).

2.Решить сравнение 4x² — 1 1х — 3 ≡ 0(mod 13).

4х² -24х + 36 ≡0(mod l3), х² -6х + 9 ≡ 0(mod 13), (х -З)² ≡ 0(mod 13), х-3 ≡0(mod 13), x≡3(mod 13).

Если в сравнении хⁿ ≡a(mod p) а делится на р, то и х делится на р и х ≡ 0(mod р) — единственное решение сравнения.

Пусть а не делится на р.

Определение. Число а называют n-степенным вычетом или n-степенным невычетом по модулю р в зависимости от того, имеет или нет решение сравнение хⁿ ≡ a(mod р), где (а, р) = 1.

В частности, число а называют квадратичным вычетом или квадратичным невычетом по модулю р в зависимости от того, имеет или

нет решение сравнение х² ≡ a(mod p), где (а, р) = 1. Если а — квадратичный вычет (невычет) по модулю р, то и любое число из класса а также является квадратичным вычетом (невычетом), поэтому квадратичным вычетом (невычетом) можно называть класс по модулю р.

Пример.

Выяснить, является ли квадратичным вычетом по модулю 5 число 3. Проверим, имеет ли решение сравнение х² ≡3(mod 5) .

Взяв приведённую систему вычетов по модулю 5: ±1, ±2, убеждаемся, что сравнение не имеет решений, то есть 3 — квадратичный невычет, а квадратичными вычетами будут 1 и 4.

Легко видно, что если сравнение (2) имеет решение х ≡x0(mod р), то оно также имеет решение х ≡-x0(mod р). При р >2 классы х0 и — х0 — разные классы. Действительно, если бы х0 ≡ -x0(mod р), то 2х0 ≡ 0(mod р), чего быть не может, так как ни 2, ни x0 не делятся на р. Сравнение (2) не может иметь более чем 2 решения, как сравнение 2-ой степени по простому модулю. Итак, нами доказана следующая теорема.

Теорема 2. Если (a,р) =1 , р — простое, р> 2, то сравнение х² ≡a(mod р) либо не имеет решений, либо имеет два решения.

Для нахождения решений сравнения х² ≡ a(mod р) можно взять приведённую систему вычетов, наименьших по абсолютной величине, по

модулю р: ± 1,±2,…,± . Более того, достаточно проверить лишь числа 1,2,…, (p-1)/2. При подстановке этих чисел в сравнение (2) в левой части сравнения получаются числа 1,2²,…,(p-1/2)². Если одно из них, например, k² сравнимо с а по модулю р, то получим решения сравнения (2): x≡±k(mod p). Мы видим, что сравнение (2) имеет решения лишь для тех чисел а, которые сравнимы с одним из чисел

1,22,…,(p-1/2)2 (3)

по модулю р, то есть в ряду (3) записаны представители всех классов квадратичных вычетов по модулю р. Причём числа (3) принадлежат разным классам по модулю р. Действительно, если для 1≤k<l≤(p-1)/2. k² ≡l² (mod р), то сравнение (2) имело бы 4 решения: ±k,±l, что невозможно. Итак, имеем (p-1)/2 классов квадратичных вычетов и столько же классов квадратичных невычетов (так как всего p-1 классов, взаимно простых с модулем). Нами доказана теорема.

Теорема 3. Число классов квадратичных вычетов по простому модулю р, р> 2, равно числу классов квадратичных невычетов, ровно (р-1)/2.

Пример.

Найдём наименьшие неотрицательные квадратичные вычеты по модулю 13. Их должно быть (p-1)/2=6. Ими являются числа: 1,2² =4,3² = 9, 4² ≡3(mod l3), 5² ≡12(mod 13), 6²≡10(mod 13), то есть 1,3,4, 9, 10, 12. Оставшиеся от приведённой системы вычетов числа: 2,5, 6, 7, 8,11 — квадратичные невычеты. Рассмотренный способ недостаточно эффективен для установления разрешимости сравнения (2). Рассмотрим другой способ.

Критерий Эйлера. Число а является квадратичным вычетом по простому модулю р (р > 2, (а,р)=1) тогда и только тогда, когда a^(p-1)/2≡1(mod p) и квадратичным невычетом тогда и только тогда, когда a^(p-1)/2≡-1(mod p).

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

По т. Ферма a^p-1≡1(mod p), то есть a^p-1-1 делится на р или (a^(p-1)/2-1)(a^(p-1)/2+1) делится на р. Оба сомножителя не могут делиться на р, иначе их разность, равняя 2, делилась бы на р, что невозможно. Если а — квадратичный вычет, то а ^(p-1)/2 -1 делится на р. Действительно, существует х0, (х0,р) = 1, что х0² ≡a(modр), Т0ГДа a^(p-1)/2≡(x0²)^(p-1)/2≡x0^p-1≡1(mod p). То есть a^(p-1)/2 ≡1(mod p)Итак, любой

квадратичный вычет удовлетворяет сравнению х^(p-1)/2 ≡ l(mod p) (4)

и вычетов (p-1)/2. Следовательно, это сравнение имеет не менее чем(p-1)/2 решений. Но и не более, так как сравнение по простому модулю имеет решений не больше, чем его степень. Поэтому квадратичные вычеты, и только они, удовлетворяют сравнению (4). Тогда для остальных а, (а,р)=1, то есть для квадратичных невычетов, и только для них, второй сомножитель делится на р, то есть a^(p-1)/2≡-1(mod p).

Пример.

Выяснить, сколько решений имеет сравнение х² ≡7(modl9). (p-1)/2=9. Проверим, будет ли 7⁹ сравнимо с 1 по модулю 19. 7² ≡-8(modl9), 7³ ≡l(modl9), 7⁹ ≡l(mod 19). Следовательно, 7 — квадратичный вычет и сравнение имеет 2 решения.

Legendre Symbol Calculator

Legendre Symbol is a mathematical theoretical function (a/p) with values equivalent to 1, -1 and 0 based on a quadratic character modulo ‘p’. Here, let ‘p’ be an odd prime and ‘a’ be an arbitrary integer. On a non zero quadratic residue mod ‘p’ , the value is 1. On a non quadratic residue it is -1 and on zero, it is 0. The symbol is used in law of quadratic reciprocity to simplify notation. Find the legendre symbol with numerator and denominator value.

Legendre Symbol is a mathematical theoretical function (a/p) with values equivalent to 1, -1 and 0 based on a quadratic character modulo ‘p’. Here, let ‘p’ be an odd prime and ‘a’ be an arbitrary integer. On a non zero quadratic residue mod ‘p’ , the value is 1.

Квадратичное сравнение

On a non quadratic residue it is -1 and on zero, it is 0. The symbol is used in law of quadratic reciprocity to simplify notation. Find the legendre symbol with numerator and denominator value.

Символ Лежандра. Символ Якоби.

Символом Лежандра называется символ (читается «символ Лежандра а по р»). а называется числителем, р – знаменателем символа Лежандра. Символ Лежандра отвечает на вопрос, является ли число а квадратичным вычетом по модулю р.

Вычислить символ Лежандра можно, пользуясь следующими свойствами.

Свойства символа Лежандра:

1. Критерий Эйлера:

2. a≡a₁(mod p)

3.

4.

5.

6.

7.

8. 3акон взаимности: если p, q – нечетные простые числа

 

Докажем некоторые из этих свойств.

Теорема (Критерий Эйлера)

Если (p, a)=1

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

По теореме Ферма, a^p—1≡1(mod p). В этом сравнении перенесем единицу в левую часть: a^p—1—1≡0(mod p).

Квадратичный вычет

Поскольку p – простое, а значит нечетное число, значит p—1 – число четное. Тогда можем разложить левую часть сравнения на множители: .

Из множителей в левой части один и только один делится на p, то есть либо

*, либо **

Если а – квадратичный вычет по модулю р, то а при некотором x удовлетворяет сравнению a≡x²(mod p) , тогда , а учитывая (по теореме Ферма), что x^p—1≡1(mod p), получаем сравнение (*).

При этом решения сравнения * исчерпываются квадратичными вычетами по модулю р. Следовательно, если а – квадратичный невычет по модулю р, то сравнение * не выполняется, а значит выполняется сравнение **.

□

Свойство 2:

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

□

Свойство 3:

Для любого p выполняется 1≡1²(mod p), а значит «1» является квадратичным вычетом для любого модуля p.

□

Свойство 4:

Доказательство следует из критерия Эйлера при a=—1.

□

Свойство 5:

По критерию Эйлера, .

□

Доказательства прочих свойств можно произвести самостоятельно или найти в [5].

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

Пример:

a)

10 – квадратичный вычет по модулю 13.

б)

.

1350 не является квадратичным вычетом по модулю 1381.

 

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

Свойства символа Якоби:

1. a≡a₁(mod n)

2.

3.

4.

5.

6. 3акон взаимности:

(n,m)=1, n, m>0, n, m — нечетные числа .

Эти свойства нетрудно доказать, воспользовавшись определением символа Якоби и свойствами символа Лежандра.

Очевидно, для символа Якоби выполняются те же свойства, что и для символа Лежандра, за исключением только критерия Эйлера. Критерий Эйлера для символа Якоби не выполняется.

Приведенные свойства символа Якоби позволяют составить алгоритм для вычисления символа Якоби и символа Лежандра:

1. Выделяем из числителя все степени двойки:

2. Пользуясь св-вом 4, понижаем степень k:

3. Если k mod 2=1, то вычисляем пользуясь св-вом 5.

4. Символ преобразуем, пользуясь законом взаимности, и затем приводим числитель m по модулю знаменателя n₁ и повторяя для получившегося символа Якоби шаги 1-4, пока в числителе не останется 1 или —1.

В более формализованном виде алгоритм выглядит следующим образом:

Алгоритм вычисления символа Якоби:

Вход: n — числитель, m – знаменатель символа Якоби. m – нечетное число,

n, m>0, s=1.

Ш.1: Если (n,m)≠1, то s:=0. Идти на Выход.

Ш.2: n:=n mod m. Ш.3.

Ш.3: Представить n как n=2^kn₁ . k:=k mod 2, n:=n₁.

Ш.4: Если k=1, то если m mod 8 = 3 или m mod 8 = 5, то s:=—s .

Ш.5: Если n=1, то идти на Выход.

Ш.6: Если n=m—1, и m mod 4 = 1, то идти на Выход.

Если n=m—1, и m mod 4 = 3, то s:=—s. Идти на Выход.

Ш.7: n↔m. s:=s·(—1) . Идти на Ш.2.

Выход. s – символ Якоби.

Пример:

.

Предыдущая9101112131415161718192021222324Следующая

ПОСМОТРЕТЬ ЕЩЕ:

Квадратичные вычеты

Если p — простое число, и a больше 0, но меньше p, то a представляет собой квадратичный вычет по модулю p, если

x² ? a (mod p), для некоторых x

Не все значения a соответствуют этому требованию. Чтобы a было квадратичным вычетом по n, оно должно быть квадратичным вычетом по модулю всех простых сомножителей n. Например, если p = 7, квадратичными вычетами являются числа 1, 2, и 4:

1² = 1 ? 1 (mod 7)

2² = 4 ? 4 (mod 7)

3² = 9 ? 2 (mod 7)

4² = 16 ? 2 (mod 7)

5² = 25 ? 4 (mod 7)

6² = 36 ? 1 (mod 7)

Заметьте, что каждый квадратичный вычет дважды появляется в этом списке. Значений x, удовлетворяющих любому из следующих уравнений, не существует:

x² ? 3 (mod 7)

x² ? 5 (mod 7)

x² ? 6 (mod 7)

Эти числа — 3, 5 и 6 — не являются квадратичными вычетами по модулю 7.

Хотя я этого и не делаю, несложно доказать, что когда p нечетно, существует в точности (p — 1)/2 квадратичных вычетов по модулю p, и столько же чисел, не являющихся квадратичными вычетами по модулю p. Кроме того, если a — это квадратичный вычет по модулю p, то у a в точности два квадратных корня, один между 0 и (p-1)/2, а второй — между (p — 1)/2 и (p — 1). Один из этих квадратных корней одновременно является квадратичным остатком по модулю p, он называется главным квадратным корнем.

Если n является произведением двух простых чисел, p и q, то существует ровно (p — l)(q — 1)/4 квадратичных вычетов по модулю n. Квадратичный вычет по модулю n является совершенным квадратом по модулю n, потому что для того, чтобы быть квадратом по модулю n, вычет должен быть квадратом по модулю p и квадратом по модулю q. Например, существует одиннадцать квадратичных остатков mod 35: 1, 4, 9, 11, 15, 16, 21, 25, 29 и 30. У каждого квадратичного вычета ровно четыре квадратных корня.