Решение сравнений и их приложения
жүктеу/скачать 131,78 Kb.
|
- Бұл бет үшін навигация:
- Теорема
- Доказательство.
- Определение .
| Определение 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 сравнений и f(с1) φ (с1) (mod m). Теорема доказана. Из доказанной теоремы вытекает, что если целое число с удовлетворяет сравнению f(x) 0 (mod m), то и все числа из содержащего с класса вычетов по модулю т удовлетворяют тому же сравнению. Поэтому задача о решении сравнений может быть поставлена иначе: Определение. Решить сравнение: f (х) φ (х) (mod m), где f(х) и φ(х) — многочлены с целыми коэффициентами— значит найти все классы вычетов по модулю m, любое число из которых удовлетворяет сравнению (1) (то есть при подстановке в (1) любого числа из этих классов вычетов получаются числа, сравнимые по модулю т). Из определения вытекает, что любое сравнение вида (1) можно решить, сделав т проб, а именно, подставив в f(х) и φ (х) вместо х по очереди все числа из полной системы вычетов по модулю т (например, числа 0, 1,…, т-1). После этого надо вычислить значения f(с) и φ(с) и отобрать те, для которых f (с) — φ (с) делится на т. жүктеу/скачать 131,78 Kb. Достарыңызбен бөлісу:
|