# Homework Help: Chinese Remainder Theorem on large exponents

1. Nov 2, 2011

### SeventhSigma

Say I have a^27,654,321 modulo 100,000,000 (where Euler's Theorem no longer helps because totient(100,000,000) = 40,000,000 which is larger than my exponent). How do I use the Chinese Remainder Theorem here to shrink down my massive a^b term I have here?

It seems like I need to first split up my modulus into coprime elements, so 2^8 *5^8. But from here I'm just not sure what I need to be doing other than trying to solve:

x = a^27,654,321 modulo 2^8
x = a^27,654,321 modulo 5^8

1. How do I correctly solve this?
2. Is x technically equivalent to a^27,654,321 modulo 100,000,000 ?