Congruence with a Prime-power Modulus

Question

How would I go about computing: 5^11469 mod 1911?

What I know:

1911 is not prime because it is divisible by 3. The same goes for the exponent 11469. Since both numbers are divisible by 3, can I reduce the problem to 5^3823 mod 637? From here, 637 is not prime as well. On the other hand, the exponent is prime.

Will I have to reduce it in a way to be able to use Fermat's Little Theorem?

Please advise.

Thanks!

Answer 1

You would go about it, noting that:

• 1911 has 1008 numbers that don't share a factor with it
• 11469 has remainder 381 on division by 1008
• use repeated exponent rules to power up to that point

Equivalently you could note:

• it has remainder of 2 on division by 3 ( aka of form $3x+2$)
• it has remainder of 27 on division by 49 (aka of form $49y+27$)
• it has remainder of 5 on division by 13 ( aka of form $13z+5$)

Equating the three above, we can solve for forms of $x$,$y$, and $z$ ($y$ is 3 mod 13 and 2 mod 3 leading to it being 29 mod 39 for example) solving for a unique remainder on division by 1911 ( we get 1448 mod 1911)