Мегаобучалка Главная | О нас | Обратная связь  


Метод преобразования коэффициентов




Теорема 1. Пусть дано сравнение:

 

(2.8)

 

НОД  и  Тогда класс вычетов  по модулю m является решением сравнения (2.8).

Доказательство. Так как НОД , то сравнение имеет одно решение. Кроме того, Возьмем целое число , , тогда , следовательно, получим сравнение: , которое является верным сравнением.

Поэтому целое число  удовлетворяет сравнению, а, значит, класс вычетов по модулю m является решением сравнения. Теорема 1 доказана.

Примеры.

1)

НОД , поэтому сравнение имеет единственное решение.

.

Найдем такое целое число k, чтобы  делилось на 5. Например, . Тогда получим: , .

Проверка. , 18 делится на 9, поэтому при подстановке в сравнение вместо переменной значения 4, получим верное сравнение, следовательно, число 4 удовлетворяет сравнению, поэтому класс целых чисел, содержащий число 4, является решением сравнения.

Ответ:

2)

НОД , следовательно, сравнение имеет одно решение.

 (при  будет )

,

Ответ: .

 


Метод Эйлера

 

Получим метод решения сравнения

 

(2.9)

 

с помощью функции Эйлера.

Теорема 1. Пусть дано сравнение (2.9), . Тогда класс вычетов



по модулю m является решением сравнения (2.9), где функция Эйлера.

Доказательство. Так как , то по теореме Эйлера имеет место сравнение  где  функция Эйлера

Выберем , тогда при подстановке его вместо  в сравнение (2.9) и, учитывая, что

получим сравнение

которое является верным в силу теоремы Эйлера. Следовательно,  удовлетворяет сравнению (2.9), а класс вычетов

по модулю m является решением сравнения, или, по-другому, решение сравнения (2.9). Теорема 1 доказана.

Примеры.

1)

, следовательно, сравнение имеет одно решение,

Преобразуем произведение .  простое число, то . Поэтому

,

Ответ: .

2) .

, поэтому сравнение имеет одно решение.

1-й способ – способ подбора. Полная система наименьших по абсолютной величине вычетов по модулю 34: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33}.

Проверим, какое из этих чисел  удовлетворяет сравнению, то есть . Это будет , так как . Следовательно, решение сравнения.

Ответ: .

2-й способ – способ преобразования коэффициентов.

, k

Найдем такое целое число , при котором . Например, , тогда .

, решение сравнения.

Ответ:

3-й способ – метод Эйлера (с помощью функции Эйлера).

Упростим произведение

решение сравнения.

Ответ:


Сравнения высших степеней

Основные понятия

Определение 1.Сравнением n-й степени с одной переменной называется сравнение вида

 

(3.1)

 

где многочлен с целыми коэффициентами:

 

(3.2)

 

причем, .

Целое число  удовлетворяет сравнению (3.1), если сравнение  является верным сравнением.

Теорема 1. Пусть дано сравнение (3.1) и целое число  удовлетворяет сравнению (3.1). Тогда весь класс  по mod m состоит из чисел, удовлетворяющих сравнению (3.1).

Доказательство. Число  удовлетворяет сравнению (3.1), следовательно, верное сравнение. Для любого  всегда . Но тогда по свойству сравнений , поэтому по транзитивности получим, что , отсюда следует, что число  удовлетворяет сравнению (3.1). А так как  произвольное из , то, следовательно, весь класс вычетов  по mod m состоит из чисел, удовлетворяющих сравнению (3.1). Теорема 1 доказана.

Определение 2.Решением сравнения (3.1) называется класс вычетов по модулю m, состоящий из чисел, удовлетворяющих сравнению (3.1).

Если класс  mod m является решением сравнения (3.1), то будем говорить, что класс  удовлетворяет сравнению (3.1). Числом решений сравнения (3.1) называется число классов вычетов по mod m, удовлетворяющих сравнению (3.1).

Задача нахождения чисел, удовлетворяющих сравнению (3.1), сводится к нахождению классов, удовлетворяющих уравнению

Действительно:

· так как  верно, то

· обратно, если , то , следовательно,

Чтобы решить сравнение , можно

1) взять любую полную систему вычетов по mod m:

2) вычислить

3) взять те числа , при которых сравнение  является верным, то есть  Соответствующие классы , дадут все решения сравнения.

Удобнее брать полную систему наименьших по абсолютной величине вычетов по mod . Если сравнение имеет несколько решений , то эти решения можно записывать в виде (то есть  принимает любые значения, сравнимые с одним из чисел ) вместо записи

Примеры.

1) (mod 11).

классы вычетов по mod 11.

2)

 Сравнение не имеет решения.

3)

Ответ:

Задача нахождения решения сравнения  проще, чем рассматриваемая в курсе алгебры задача нахождения решения уравнения . Так как решая уравнение в некотором бесконечном множестве (R, С) нельзя перебрать все числа . А решая сравнение , ищем решение в конечном кольце Zm классов вычетов по mod m. Следовательно, с помощью конечного числа операций можно найти все решения. Но надо заметить, что при больших m будут громоздкие вычисления, поэтому надо изучить способы, позволяющие определить число решений, а иногда и способы нахождения решения с помощью возможно меньшего числа операций.

3.2 Сравнения вида

 

Рассмотрим сравнение с одной переменной вида

 

(3.3)

 

где , , коэффициенты при старшем члене  и  не делятся на m.

Определение 1.Решением сравнения (3.3) называется класс вычетов по mod m, состоящий из чисел, удовлетворяющих этому сравнению.

Теорема 1.Пусть  и многочлены с целыми коэффициентами и целое число  удовлетворяет сравнению (3.3). Тогда весь класс вычетов (mod m ) состоит из чисел, удовлетворяющих этому сравнению.

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

1) Так как число  удовлетворяет сравнению (3.3), то оно удовлетворяет сравнению , где .

2) mod m будет , следовательно, , поэтому число  удовлетворяет сравнению то есть сравнению . Следовательно, число  удовлетворяет сравнению (3.3). Таким образом, класс вычетов  состоит из чисел, удовлетворяющих сравнению (3.3). Теорема 1 доказана.

Определение 2. Два сравнения

 

(3.4)

 

и

 

(3.5)

 

называются эквивалентными, если множество чисел, удовлетворяющих одному из них, совпадает с множеством чисел, удовлетворяющих другому сравнению.

Если и сравнения (3.4) и (3.5) имеют одни и те же решения, то получим два эквивалентных сравнения по .

Эквивалентные сравнения могут иметь разную степень.

Пример.

Решение первого сравнения: , решением второго сравнения тоже будет класс вычетов . Следовательно, они эквивалентны. Но степени их различны (степень первого сравнения равна 1, степень второго – 3).

 

Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Читайте также:



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (292)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.044 сек.)
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7