Блог пользователя noxwell

a^x mod m если a и m имеют общий делитель
Автор noxwell, история, 7 лет назад, По-русски

Известно, что по теореме Эйлера a^phi(m)=a^0=1 mod m для a, взаимнопростых с m. Т.е., степень можно брать по модулю phi(m). Может кто-нибудь объяснить, как ведёт себя степень не взаимнопростых чисел? Когда образуется цикл, какой он длины, или вообще степени в ноль уходят. Есть ли какое-нибудь обобщение теоремы Ферма, или другая теория, позволяющая хорошо описать поведение степеней по модулю. Я помню, что цикл, в котором будут степени, зависит от gcd(a, m), но не помню, как именно.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Научимся сначала решать случай, когда m = pk (простое число в некоторой степени). Если научимся, то для общего случая достаточно разложить m на простые множители и воспользоваться китайской теоремой об остатках.

Теперь пусть m = pk. Если (a, m) = 1, то просто пользуемся теоремой Эйлера. А иначе имеем, что a делится на p и значит ak при делении на m даёт остаток ноль — получаем период длины один и предпериод длины не более k.

В общем случае это означает, что у нас будет предпериод не больше (максимальная степень вхождения простого числа), а дальше — период, являющийся делителем φ(m), потому что функция Эйлера мультипликативна, а нам надо посчитать период по модулю вида "m, из которого выкинули несколько простых".

→ Ответить