Решение сравнений методом подбора. Метод преобразования коэффициентов при решении линейных сравнений. 3 страница

4⁰.
Следствие. .
5⁰.
Следствие. Если то .Если то Поэтому
6⁰. (Закон взаимности) Если и нечётные простые числа, то, или Или

. (11)

Следствие. Если хотя бы одно из чисел или имеет форму , то показатель в правой части (11) чётный, и . Если и или имеет форму , то показатель в правой части (11) нечётный, и .

41 Символ Якоби и его свойства.
Определение. Пусть нечётное число , где - простые числа, среди которых могут быть одинаковые, .Символ Якоби определяется равенством , (12)
Где - символы Лежандра.Читается - «символ Якоби по отношению к ».
Замечание1. символ Лежандра является частным случаем символа Якоби.
Замечание2. символ Якоби обладает свойствами 1⁰-6⁰ символа Лежандра с той лишь разницей, что в случае символа Якоби речь идёт не о нечётных простых числах , а о нечётных числах .Из замечаний следует, что при вычислении символа Лежандра удобно рассматривать его как символ Якоби, тогда отпадает необходимость выделять из числителя его нечётные простые множители.По значению символа Якоби можно сказать следующее:
- если , то - квадратичный невычет по ;- если и - нечётное составное число, то о квадратичности вычета по ничего сказать нельзя.
Свойства
1⁰. Если то .
2⁰. , т.е. 1 – квадратичный вычет для любого нечётного простого , т.к. сравнение всегда разрешимо.
3⁰.
Следствие.
4⁰.
Следствие. .
5⁰.

42 Сравнения второй степени по составному модулю
Рассмотрим сравнение по составному модулю
. (13)
Если - чётное, то справедлива теорема
Теорема Пусть , где - различные нечётные простые числа, . Сравнение (13) имеет решения тогда и только тогда, когда
1. - квадратичный вычет по всем модулям 2. если , то , а если , то .
Число решений сравнения (13) (если они существуют) равно
при и ;
при ;
при .
Доказательство. Сравнение (13) равносильно системе

(14)

Если , то

1) при и первое сравнение (14) имеет одно решение, каждое последующее сравнение имеет по два решения. Тогда система (14) и сравнение (13) имеет решений;
2) при и каждое сравнение в (14) имеет по два решения. Тогда система (14) и сравнение (13) имеет решений;
3) при , первое сравнение имеет решения (доказать самостоятельно). Тогда система (14) и сравнение (13) имеет решений.
Во всех остальных случаях, т.е. если
1) хотя бы один из символов Лежандра ;
3) при ;
4) при ;
в систему (14) входят сравнение, которое не имеет решения, а следовательно, не имеет решений и сравнение (13).
В случае нечётного сравнение (13) можно исследовать с помощью символа Якоби . Однако, если ничего о числе решений мы сказать не можем.
Справедлива также теорема:
Теорема Сравнение (где ) имеет два решения, если и не имеет решений, если . (без доказательства).

43 Показатели и их основные свойства.
Сравнение вида называется показательным. Изучение таких сравнений сводится к изучению сравнений вид . (1)
Если то по теореме Эйлера следовательно сравнение (1) при всегда имеет решение.
Определение. Наименьшее положительное решение сравнения (1) называется показателем числа по модулю , или говорят, что число принадлежит показателю по модулю Записывают .
Определение. Числа, принадлежащие показателю называются первообразными корнями по модулю
Свойства показателей.
1. Числа одного класса вычетов принадлежат одному и тому же показателю.
Доказательство.
Пусть Т.к. и то следовательно Т.к. и то следовательно Отсюда
2. Если является решением сравнения (1) и то
Доказательство.
На основе теоремы о делении с остатком и Т.к. решение сравнения (1), то Тогда
Т.к. то поэтому Но, следовательно Таким образом, т. е.
Следствие. Если то
Доказательство.
По теореме Эйлера т.е. решение сравнения (1). Следовательно,
Замечание. Из сформулированного следствия получаем, что показатель числа по модулю надо искать среди делителей
3. Сравнение имеет место тогда и только тогда, когда где показатель числа по модулю
Доказательство.

1. Пусть и для определённости Т.к. то Сократим сравнение на Тогда по свойству следовательно,
2. Пусть и Тогда Получаем
4. Если по модулю то числа попарно не сравнимы по модулю
Доказательство. Согласно свойству тогда и только тогда, когда но среди показателей последовательности (2) нет сравнимых по модулю

44. Первообразные корни. Теорема о существовании первообразного корня по простому модулю.
Определение. Числа, принадлежащие показателю называются первообразными корнями по модулю
Лемма. По простому модулю делитель числа либо не является показателем какого-либо класса вычетов, либо является для таких классов ( доказательство самостоятельно).
По простому модулю каждый делитель числа является показателем для классов.
Теорема (Гаусса). По любому простому модулю существует классов первообразных корней.
Доказательство. Пусть все делители числа Распределяя вычеты приведённой системы вычетов по модулю т.е. числа в отдельные группы по принадлежности своему показателю, всего должны получить чисел.Если обозначить число чисел приведённой системы, принадлежащих показателю (3)
С другой стороны, сумма значений функций Эйлера, распространённая по всем делителям данного числа, равна этому числу, т.е.
(4) Приравнивая (3) и (4), получаем Согласно лемме Отсюда в равенстве (5) всегда т.к. если хотя бы одно то в правой части (5) останется лишний положительный член и равенство нарушается. Тогда получаем, что для делителя существует классов первообразных корней.
Замечание. Первообразные корни существуют только по модулям, где простое нечётное число,

45.Первообразные корни по модулям и . Теорема об отыскании первообразных корней
Пусть простое нечётное число и Первообразные корни по модулям и связаны следующим свойством:
Свойство. Пусть и первообразный корень по модулю Нечётное из чисел и будет первообразным корнем по модулю Первообразные корни по модулям и можно находить, пользуясь теоремой:
Теорема. Пусть и различные простые делители числа Для того, чтобы число взаимно простое с модулем было первообразным корнем по модулю необходимо и достаточно, чтобы это не удовлетворяло ни одному из сравнений .

46.Индексы и их свойства. Индексы по модулям и . Таблица индексов.
Пусть первообразный корень по простому модулю тогда числа представляют собой приведённую систему вычетов по модулю
Так как для любого простого существуют первообразные корни, то приведённую систему вычетов можно составить указанным способом. Таким образом, для любого числа взаимно простого с найдётся единственное число принадлежащее тому же классу по модулю что и т.е. где . Это позволяет ввести понятие индекса.
Определение. Пусть первообразный корень по модулю Если выполняется сравнение (7), то число называется индексом числа по модулю при основании и обозначается )))
Если величина основания не важна, то можно обозначать Таким образом, из (7) имеем
. (8)
Свойства индексов.
1. Пусть тогда тогда Перемножая сравнения, получаем:
Так как то сравнимо с одним из чисел ряда Разделим на т.е. . (9)

Тогда Отсюда Подставляем в равенство (9) значения получаем
2.
3.
4. первообразный корень.
5.
6. Если первообразный корень, то
Для примера докажем свойство 1
Доказательство.
Пусть тогда тогда Перемножая сравнения, получаем:
Так как то сравнимо с одним из чисел ряда Разделим на т.е. . (9)
Тогда Отсюда Подставляем в равенство (9) значения получаем
Замечание. По простому модулю для каждого числа существует бесконечное множество индексов, сравнимых по модулю Обычно из всех возможных значений индекса по данному основанию берут наименьшее. Индексы имеют большие приложения. Для удобства составляют таблицы индексов. Для составления таблицы индексов по модулю
1) находим первообразный корень по модулю
2) вычисляем все степени
3) составляем таблицу.
Замечание1. По таблице можно определить, для какого первообразного корня она составлена.
Замечание2. Для удобства составляют также таблицу антииндексов, определяющую по индексу I число.
Замечание3. Таблицы индексов для простых модулей p содержат индексы чисел от 1 до p-1. Для каждого такого числа и всех сравнимых с ним по модулю p в таблице указывается индекс, представляющий собой одно из чисел 0,1,…,р-2. В некоторых таблицах в качестве индекса единицы указывается не 0, а р-1.
Замечание4. Для составных модулей (p- простое нечётное число) существуют первообразные корни, и поэтому для любого числа, взаимно простого с таким модулем, существуют индексы.