В теории чисел, которая занимается изучением целочисленных значений, есть еще одна задача, которую мы попытаемся решить.
если нам известны A,B,C то при каком значении x это равенство будет верным?
Как пример
Решение подобных задач, неразрывно связано с функцией Эйлера. Хотя конечно есть и альтернативный метод решения (по Евклиду), но мы его рассмаотривать не будем.
Как же решать подобные уравнения. Вспомним, что по формуле Ферма-Эйлера есть следующая зависимость. Если a и m - взаимно простые числа ( то есть не имеющие общих делителей), то
С учетом того, что функция Эйлера от простого числа m равна m-1, получаем знаменитую формулу для любого простого числа
где как уже сказано a должно быть взаимно простым с m.
Способ Эйлера, позволяющий решать подобные сравнения в формулах выглядит так
Тогда, решая уравнение
узнаем чему же равен x
Попробуем решить наш первый пример.
функция Эйлера для числа 47 равна 46
и окончательная формула равна
Если считать "влоб" получится огромное число, но нам надо узнать всего лишь
Как можете заметить, мы можем решать еще попутно аналогичную задачу, которая называется обратное значение по модулю для класса вычетов и которая выражается формулой