I am being asked to solve for x in the following: x^1477 = 2673 mod 3977. Additionally, I'm being asked to show what my p, q, and φ(3977) is that I used to solve.
φ(3977) = 40 * 96 = 3840. Normally my first step would be to use Euler's theorem to reduce the large power (in this case 1477), but I'm always at a loss of what to do when the φ of the modulus is larger than the exponent. Any help is appreciated.