Chinese Remainder Theorem on large exponents

[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 ?

 

[mighty2000]

1. To solve this using the Chinese Remainder Theorem, you will need to find the inverse of a modulo both 2^8 and 5^8. This can be done using the extended Euclidean algorithm. Once you have the inverses, you can use the Chinese Remainder Theorem to combine the solutions for each modulus and find the final solution for x.

2. Yes, x is technically equivalent to a^27,654,321 modulo 100,000,000. This is because the Chinese Remainder Theorem states that if two numbers are coprime, then there exists a unique solution modulo their product. In this case, 2^8 and 5^8 are coprime, so the solution for x will be unique modulo 2^8 * 5^8, which is equivalent to 100,000,000.