Сравнения первой степени.Теория чисел

Параметры сравнения 1 рода (через пробел)

Заданное равенство

Будет верным, если x=

В теории чисел, которая занимается изучением целочисленных значений, есть еще одна задача, которую мы попытаемся решить.

$(A*x)mod(B)=C$

если нам известны A,B,C то при каком значении x это равенство будет верным?

Как пример

$(A*x)mod(B)=C$

Решение подобных задач, неразрывно связано с функцией Эйлера. Хотя конечно есть и альтернативный метод решения (по Евклиду), но мы его рассмаотривать не будем.

Как же решать подобные уравнения. Вспомним, что по формуле Ферма-Эйлера есть следующая зависимость. Если a и m - взаимно простые числа ( то есть не имеющие общих делителей), то

$a^{\phi(m)}mod(m)=1$

С учетом того, что функция Эйлера от простого числа m равна m-1, получаем знаменитую формулу для любого простого числа

$a^{\phi(m)}mod(m)=1$

где как уже сказано a должно быть взаимно простым с m.

Способ Эйлера, позволяющий решать подобные сравнения в формулах выглядит так

$a^{\phi(m)}mod(m)=1 =>a*a^{\phi(m)-1}mod(m)=1$

$a(a^{\phi(m)-1}b)mod(m)=b$

Тогда, решая уравнение $(a*x)mod(m)=b$

узнаем чему же равен x

$x=ba^{\phi(m)-1}$

Попробуем решить наш первый пример.

$(A*x)mod(B)=C$

$x=4758^{\phi(m)-1}$

функция Эйлера для числа 47 равна 46

и окончательная формула равна $x=4758^{56-1}$

Если считать "влоб" получится огромное число, но нам надо узнать всего лишь $xmod(m)=>xmod(87)$

Для решения подобной задачи мы воспользуемся материалом Остаток числа в степени по модулю и узнаем что наше решение

равно $x=47*58mod(87)=29$

проверим подставив полученное значение

$(A*x)mod(B)=C$

делится нацело, а значит наше решение верное.

Как можете заметить, мы можем решать еще попутно аналогичную задачу, которая называется обратное значение по модулю для класса вычетов и которая выражается формулой

$(A*x)mod(B)=1$

Удачных расчетов!