Поделиться
Математика
1036вопросов
Другое
665вопросов
Русский язык
322вопроса
Литература
156вопросов
Черчение
93вопроса
Информатика
75вопросов
Химия
73вопроса
Физика
68вопросов
Биология
61вопрос
Английский язык
58вопросов
Экономика
56вопросов
История
55вопросов
География
54вопроса
Другие предметы
54вопроса
Социология
50вопросов
Обществознание
47вопросов
Музыка
47вопросов
Окружающий мир
45вопросов
Украинский язык
45вопросов
Физкультура
44вопроса
Психология
42вопроса
Теория вероятностей
40вопросов
Право
40вопросов
Немецкий язык
39вопросов
Физкультура и спорт
38вопросов
Астрономия
33вопроса
Философия
30вопросов
ОБЖ
27вопросов
Казахский язык
26вопросов
Естествознание
1вопрос
Статистика
0вопросов
Экология
0вопросов
Украинская литература
0вопросов
МХК
0вопросов
Белорусский язык
0вопросов
Решение уравнений с вычетами
В теории чисел, криптографии и других областях науки часто возникает задача отыскания решений сравнения первой степени вида
ах = Ь(тодт).
Решение такого сравнения начинается с вычисления NOD(a, т) = = с1. При этом возможны два случая:
• если b не кратно d, то у сравнения нет решений;
• если b кратно d, то у сравнения существует единственное решение по модулю т / d или, что то же самое, d решений по модулю т. В этом случае в результате сокращения исходного сравнения на d получается сравнение
а{х = ^(mod/Wj),
где al = a/d,b^=b/dnml = m/ dявляются целыми числами, причем ах и /77[ взаимно просты. Поэтому число а{ можно обратить по модулю /г? J, т.е. найти такое число с, что с ? а] = Ктос^) (другими словами, с = af^mod/Tij)). Теперь решение находится умножением полученного сравнения на с:
х = са{х = cb] = fl|_lZ/|(mod/771).
Практическое вычисление значения с можно осуществить разными способами: с помощью теоремы Эйлера, алгоритма Евклида, теории цепных дробей (см. алгоритм) и др. В частности, теорема Эйлера позволяет записать значение с в виде
с = ф”1 = a1)_1(mod/77|).
Для сравнения 4х = 26(mod22) имеем d = 2, поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все три числа на 2:
2х = 2(modl 1).
Поскольку 2 взаимно просто с модулем 11, то его можно обратить
по модулю 11 и найти 2_| = 6(mod 11). Умножая сравнение на 6, получаем решение по модулю 11: х = l(mod 11), эквивалентное совокупности двух решений по модулю 22: х = l(mod 22) и х = 12(mod 22).