3
$\begingroup$

I need to calculate $3781^{23947} \pmod{31847}$. Does anyone know how to do it? I can't do it with regular calculators since the numbers are too big. Is there any other easy solutions?

Thanks

$\endgroup$
0

4 Answers 4

6
$\begingroup$
  1. You can always compute $a^n$ by repeated squaring and multiplication, e.g., to get $a^{13}$, you square $a$, multiply the result by $a$, square twice, and multiply again by $a$. The exact sequence of operations is visible in the binary expansion of $n$.

  2. You can always prevent the numbers from getting too big by reducing, using the modulus, whenever the numbers exceed the modulus.

$\endgroup$
1
  • 2
    $\begingroup$ I'd just like to point out that repeated squaring is not necessarily the fastest way to do this. The more general "addition-chain exponentiation" (en.wikipedia.org/wiki/Addition-chain_exponentiation) can sometimes require less multiplications. However, it's a lot harder to figure out which multiplications to do. $\endgroup$ May 2, 2011 at 0:14
5
$\begingroup$

23947=7*11*311. Then $$3781^{23947} = (3781^7)^{11\times 311}$$ Then reduce $3781^7$ modulo 31847 and keep going. Since $3781^7$ is probably too big, you might have to compute it as $$3781\times 3781^6=3781\times (3781^2)^3$$ where again you reduce mod 31847 wherever possible.

$\endgroup$
4
  • $\begingroup$ And what would you do if you couldn't factor the exponent? $\endgroup$ May 2, 2011 at 0:11
  • 2
    $\begingroup$ Precisely what I did with the exponent 7? $\endgroup$
    – dstt
    May 2, 2011 at 0:16
  • 1
    $\begingroup$ OK. Then why bother factoring? Does it actually make anything better? $\endgroup$ May 2, 2011 at 0:24
  • 1
    $\begingroup$ If you have a small factor and your calculator can handle it, then it usually makes things faster. It might also happen, that $3781^7$ is small mod 31847, so that your calculator can still handle that to the power 11... I usually start by factoring for these reasons. $\endgroup$
    – dstt
    May 2, 2011 at 0:33
1
$\begingroup$

I'm not sure if there is a good trick to use. I think the best way to go about it would be to compute it is to write $23947 = 2^{14} + 2^{12} + 2^{11} + 2^{10} + 2^8 + 2^7 + 2^3 + 2 + 1$ and compute $3781^{2^n} \mod 31847$ by repeatedly squaring and taking the modulus. We can then multiply these values $\mod 31847$ to compute the desired value. WolframAlpha says the answer is 6479.

$\endgroup$
1
  • $\begingroup$ I think the answer will be 7458 based on this method. $\endgroup$
    – IDS-master
    May 3, 2011 at 1:21
0
$\begingroup$

Check out Chapter 1 of Dasgupta, Papadimitriou, Vazarani which describes this and other basic arithmetic on large integers. The version linked above is a preprint of the current edition, but it's free. :)

$\endgroup$

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.