2
$\begingroup$

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)$$

$\endgroup$
2
  • 4
    $\begingroup$ Chinese Remainder Theorem $\endgroup$
    – MafPrivate
    Jan 14 '20 at 8:43
  • $\begingroup$ 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. $\endgroup$
    – fleablood
    Jan 15 '20 at 7:27
1
$\begingroup$

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}$$

$\endgroup$
4
  • $\begingroup$ Where exactly does $5^{2003}$ come in here? $\endgroup$
    – John Zhau
    Jan 15 '20 at 4:03
  • $\begingroup$ @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. $\endgroup$ Jan 15 '20 at 7:11
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – fleablood
    Jan 15 '20 at 7:38
  • $\begingroup$ 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}$ $\endgroup$
    – fleablood
    Jan 15 '20 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.