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