>>222
オイラーの定理、aがmと互いに素な時a^φ(m)≡1 (mod m)使えばできるな。