admin / 16.06.2018

Квадратичный вычет по модулю

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

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

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

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

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

Примеры. 1.

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

36х2 + 12*7х+ 12*8 ≡ 0(modl7), (6х + 7)2 ≡49-96(mod 17), (6х + 7)2 ≡ -47 + 5l(mod l7), (6х + 7)2 ≡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).

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

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

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

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

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

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

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

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

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

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

Пример.

Выяснить, является ли квадратичным вычетом по модулю 5 число 3. Проверим, имеет ли решение сравнение х2 ≡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, то сравнение х2 ≡a(mod р) либо не имеет решений, либо имеет два решения.

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

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

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

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

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

Пример.

Найдём наименьшие неотрицательные квадратичные вычеты по модулю 13. Их должно быть (p-1)/2=6. Ими являются числа: 1,22 =4,32 = 9, 42 ≡3(mod l3), 52 ≡12(mod 13), 62≡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).

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

По т. Ферма ap-1≡1(mod p), то есть ap-1-1 делится на р или (a(p-1)/2-1)(a(p-1)/2+1) делится на р. Оба сомножителя не могут делиться на р, иначе их разность, равняя 2, делилась бы на р, что невозможно. Если а — квадратичный вычет, то а (p-1)/2 -1 делится на р. Действительно, существует х0, (х0,р) = 1, что х02 ≡a(modр), Т0ГДа a(p-1)/2≡(x02)(p-1)/2≡x0p-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).

Пример.

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


⇐ Предыдущая891011121314151617Следующая ⇒


Дата публикования: 2014-12-08; Прочитано: 1504 | Нарушение авторского права страницы



studopedia.org — Студопедия.Орг — 2014-2018 год.(0.001 с)…

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.

Example:

If the numerator is 30 and denominator is 23,

30 / 23

= 7 / 23 (i.e., 30 mod 23)
= -2 / 7 (i.e., both odd reciprocol multiply with -1 and take mod)
= -1 / 7
= -1

Rules To Find Legendre Symbol

  1. (a/n) = (b/n) if a = b mod n.
  2. (1/n) = 1 and (0/n) = 0.
  3. (2m/n) = (m/n) if n = ±1 mod 8. Otherwise (2m/n) = -(m/n).
  4. (Quadratic reciprocity) If m and n are both odd, then (m/n) = (n/m) unless both m and n are congruent to 3 mod 4, in which case (m/n) = -(n/m).

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

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

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

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

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

2. a≡a1(mod p)

3.

4.

5.

6.

7.

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

 

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

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

Если (p, a)=1

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

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

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

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

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

*, либо **

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

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

Свойство 2:

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

Свойство 3:

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

Свойство 4:

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

Свойство 5:

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

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

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

Пример:

a)

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

б)

.

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

 

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

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

1. aa1(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 по модулю знаменателя n1 и повторяя для получившегося символа Якоби шаги 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=2kn1 . k:=k mod 2, n:=n1.

Ш.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Следующая


Дата добавления: 2015-11-28; просмотров: 2389;


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

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

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

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

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

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

12 = 1 ? 1 (mod 7)

22 = 4 ? 4 (mod 7)

32 = 9 ? 2 (mod 7)

42 = 16 ? 2 (mod 7)

52 = 25 ? 4 (mod 7)

62 = 36 ? 1 (mod 7)

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

x2 ? 3 (mod 7)

x2 ? 5 (mod 7)

x2 ? 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. У каждого квадратичного вычета ровно четыре квадратных корня.

FILED UNDER : IT

Submit a Comment

Must be required * marked fields.

:*
:*