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

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

 

если нам известны 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

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