# Given $a^b \pmod {c}$, $a^b \pmod {d}$, $a^b \pmod {e}$, how can $a^b mod (c*d*e)$ be deduced?

This question covered large exponents on the $$b$$ side. What about the $$m$$ side?

Given:

$$a^b \pmod m$$

where $$m$$ is a large compound number.

For example:

Given

$$5^{2003} \pmod {7} \equiv 3$$ $$5^{2003} \pmod {11} \equiv 4$$ $$5^{2003} \pmod {13} \equiv 8$$

how can one quickly deduce:

$$5^{2003} mod (7*11*13)$$

• Chinese Remainder Theorem Jan 14 '20 at 8:43
• as well as chinese remainder theorem you may need: if $a\equiv b\pmod n$ then $\frac a{\gcd(a,n)}\equiv \frac b{\gcd(a,n)}\pmod {\frac n{\gcd(a,n)}}$ if the moduli are not relatively prime. Jan 15 '20 at 7:27

Let the number be $$x$$.

Then we get from the Chinese Remainder Theorem: $$5^{2003}\pmod{7\cdot 11\cdot 13}\equiv x\iff\begin{cases}x\pmod 7\equiv 3\\x\pmod{11}\equiv 4\\ x\pmod{13}\equiv 8\end{cases}$$

The following is one method to apply the Chinese Remainder Theorem.

From the 3rd equation: $$x=13k+8\tag 4$$

Combine with the 1st equation: $$13k+8\equiv -k+1\equiv 3\pmod 7\implies k=7l-2$$ Substitute in (4): $$x=13(7l-2)+8=13\cdot7l-18\tag 5$$ Combine with 2nd equation: $$13\cdot7l-18\equiv 3l+4\equiv 4\pmod{11} \implies l=11m$$ Substitute in (5): $$x=13\cdot7\cdot 11m -18 \equiv -18\pmod{7\cdot 11\cdot 13}$$

• Where exactly does $5^{2003}$ come in here? Jan 15 '20 at 4:03
• @JohnZhau, the 3 given equations are derived from it. E.g. $5^{2003}\pmod 7\equiv (5^{333})^6\cdot 5^5\equiv 1\cdot (-2)^5\equiv 3$. Since you already have those equations, we don't see it anymore. Jan 15 '20 at 7:11
• The chinese remainder theorem says there is only one such value $x$ that is congruent to those values and mods. So as $5^{2003}$ is congruent to those values, it must be that $5^{2003} \equiv x \pmod {7*11*13}$. So solve for $x$ and that will solve for $5^{2003}$. Jan 15 '20 at 7:38
• tl;dr.... Let $x = 5^{2003}$. Solve for $x$. $x\equiv -18\pmod{7*11*13}$ therefore..... $5^{2003} \equiv -18\pmod{7*11*13}$ Jan 15 '20 at 7:39