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

Примеры. Решим сравнение: f (х) = х3 — 3 0 (mod 6). (2)

жүктеу/скачать 131,78 Kb. бет 14/14 Дата 09.06.2022 өлшемі 131,78 Kb. #36581 түрі Решение

Примеры. Решим сравнение: f (х) = х3 — 3 0 (mod 6). (2) Надо подставить вместо х числа 0, 1, 2, 3, 4, 5,6. f (0) =-3, f (1) = -2, f (2) = 5, f(3) = 24, f(4) = 61, f(5) = 122. Только f(3) = 24 делится на 6. Значит, решением сравнения (2) является класс вычетов = {... -9, -3, 3, 9 ...}. Разумеется, вместо чисел 0, 1,2, 3, 4, 5 можно было подставить числа, образующие иную полную систему вычетов по модулю 6, например числа -2, -1,0, 1,2, 3. Существуют сравнения, совсем не имеющие решений. Решим сравнение: х4 + 2х — 1 0 (mod 7). Составим полную систему абсолютно наименьших вычетов 0, 1, 2, 3, -3, -2, -1 по модулю 7. Ни один из вычетов данной системы не удовлетворяет данному сравнению. Следовательно, сравнение решений не имеет. С теоретической точки зрения задача решения сравнений вида / (х) г= 0 (mod т) очень проста: мы просто ищем решения в конеч­ном множестве классов (т классов) по модулю т, что достигается, как мы уже установили, путем конечного числа испытаний выче­тов некоторой полной системы вычетов по модулю т. Однако на практике указанный прием испытания вычетов при больших мо­дулях оказывается затруднительнымдак как приводит к большому количеству испытаний. Например, для решения сравнения 19х8+ + 13х2 — 2х + 17 Е55 0 (mod 625), следуя указанному приему ре­шения сравнений, надо проверить 625 вычетов. Естественно возникает вопрос: нельзя ли упростить работу и свести ее к выполнению меньшего числа операции? Оказывается, можно. Существуют способы, позволяющие найти число решений сравнения, а в ряде случаев и найти все решения значительно быстрее. жүктеу/скачать 131,78 Kb. Достарыңызбен бөлісу: