Ответить на вопрос
Математика
1079вопросов
Другое
639вопросов
Русский язык
307вопросов
Литература
125вопросов
Черчение
48вопросов
Химия
39вопросов
Физика
34вопроса
Другие предметы
26вопросов
Информатика
22вопроса
История
21вопрос
Биология
20вопросов
Английский язык
18вопросов
Экономика
17вопросов
География
16вопросов
Право
11вопросов
Социология
10вопросов
Обществознание
7вопросов
Психология
5вопросов
Теория вероятностей
5вопросов
Физкультура
3вопроса
Музыка
3вопроса
Философия
2вопроса
Окружающий мир
2вопроса
Физкультура и спорт
2вопроса
Немецкий язык
1вопрос
Казахский язык
1вопрос
ОБЖ
1вопрос
Естествознание
0вопросов
Экология
0вопросов
Статистика
0вопросов
Украинский язык
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).