Решение сравнений и их приложения



бет13/14
Дата09.06.2022
өлшемі131,78 Kb.
#36581
түріРешение
1   ...   6   7   8   9   10   11   12   13   14
Байланысты:
reshenie sravnenii i ih prilozheniya 0

Определение 1. Пусть f(х) = а0хп + ... + ап , φ(х)=bоХк + ... + bk — многочлены с целыми коэффициентами а0,…,ап , bо,…,bk . Решить сравнение f (х) φ(x) (mod m) — значит найти все целые числа х, при подстановке которых в мно­гочлены f(х) и φ(х) получаются целые числа, разность которых делится на m. Если f(с)(с) (mod m), то говорят, что целое число с удовлетворяет сравнению f (х) φ(x) (mod m), или, ина­че, является корнем этого сравнения.
Теорема 1.
Если число с удовлетворяет сравнению
f (х) φ (х) (mod m), (1)
mo и любое число с1 такое, что с с1 (mod m), удовлетворяет тому же сравнению.
Доказательство.
Так как с удовлетворяет сравнению (1), то f(с) φ (с) (mod m), то есть f(с) — φ (с) 0 (mod m). Но так как с с1 (mod m), то по свойству 11 сравнений и f1) φ 1) (mod m). Теорема доказана.
Из доказанной теоремы вытекает, что если целое число с удов­летворяет сравнению f(x) 0 (mod m), то и все числа из содержа­щего с класса вычетов по модулю т удовлетворяют тому же срав­нению. Поэтому задача о решении сравнений может быть поставле­на иначе:
Определение. Решить сравнение:
f (х) φ (х) (mod m),
где f(х) и φ(х) многочлены с целыми коэффициентами— значит найти все классы вычетов по модулю m, любое число из которых удовлетворяет сравнению (1) (то есть при подстановке в (1) любого числа из этих классов вычетов получаются числа, сравнимые по модулю т).
Из определения вытекает, что любое сравнение вида (1) мож­но решить, сделав т проб, а именно, подставив в f(х) и φ (х) вместо х по очереди все числа из полной системы вычетов по модулю т (например, числа
0, 1,…, т-1). После этого надо вычислить значения f(с) и φ(с) и отобрать те, для которых f (с) — φ (с) де­лится на т.


Достарыңызбен бөлісу:
1   ...   6   7   8   9   10   11   12   13   14




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет