Как решить уравнение дискретная математика?

Решение уравнений с вычетами
В теории чисел, криптографии и других областях науки часто возникает задача отыскания решений сравнения первой степени вида

ах = Ь(тодт).

Решение такого сравнения начинается с вычисления 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).