Математика
1122вопроса
Другое
688вопросов
Русский язык
346вопросов
Литература
176вопросов
Черчение
93вопроса
Информатика
75вопросов
Химия
73вопроса
Физика
67вопросов
Биология
62вопроса
История
62вопроса
Английский язык
60вопросов
Экономика
58вопросов
Другие предметы
57вопросов
География
55вопросов
Социология
50вопросов
Физкультура
47вопросов
Украинский язык
47вопросов
Музыка
47вопросов
Обществознание
46вопросов
Окружающий мир
45вопросов
Право
42вопроса
Психология
42вопроса
Теория вероятностей
41вопрос
Немецкий язык
40вопросов
Физкультура и спорт
38вопросов
Астрономия
33вопроса
Философия
30вопросов
ОБЖ
29вопросов
Казахский язык
28вопросов
Статистика
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).