# Calculating powers of large number using Chinese Remainder Theorem

Supposed we want to calculate the power of: $2^{99999999999999} + 6^{567563535463455555}$
and we have a set of prime numbers $\{x : x \in\mathbb{Z}, \text{ isPrime}(x)\}$

Now its obvious that trying to calculate the power of the above expression is near impossible on computers since there aren't enough bits and memory to represent such a number so we use CRT
I know we have to set up equation in congruence classes and solve the system to retrieve the final value.
For example in the following system
$x ≡ 6\mod 7$
$x ≡ 5\mod 11$
we know that $x$ is $66 \in \dfrac{\mathbb{Z}}{77\mathbb{Z}}$
I'm confused how to apply the problem stated above using the CRT. Can you help me?

Note: CRT refers to Chinese Remainder Theorem.

• It is not clear what you are asking. It seems instead of power in the first line you mean value. Next you are hoping to calculate $2^{99999999999999} + 6^{567563535463455555} \pmod p$ for a set of primes. This is achievable using Fermat's little theorem If you use enough primes, you will get an unambiguous answer, but I don't think that is any easier than just calculating. – Ross Millikan Feb 25 '14 at 5:35
• 66 is incorrect. It should be 27. – steven gregory Aug 29 '16 at 13:25

Given a set of primes, $\{p_i \mid i\in[1,k]\}$, compute a basis: A set of integers $b_i$ such that $b_i \cong 1 \mod p_i$ and $b_i \cong 0 \mod p_j$ for $j \neq i$. Since they're primes, they are coprime, so there is a linear combination of them that produces one, and this is what you need to find your basis.
Suppose then that some number, $n$, is simultaneously congruent to $a_i \mod p_i$ for the set of primes. Then $n \cong \left( \sum a_i b_i \right) \mod \prod_{i=1}^k p_i$.