Теорема (Критерий Эйлера)
Если (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. a≡a1(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 – символ Якоби. Пример: .
Популярное: Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1399)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |