Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

4 Answers 4

up vote 5 down vote accepted
  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.

share|improve this answer
1  
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. –  Michael Lugo May 2 '11 at 0:14

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.

share|improve this answer
    
And what would you do if you couldn't factor the exponent? –  Gerry Myerson May 2 '11 at 0:11
2  
Precisely what I did with the exponent 7? –  dstt May 2 '11 at 0:16
1  
OK. Then why bother factoring? Does it actually make anything better? –  Gerry Myerson May 2 '11 at 0:24
1  
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. –  dstt May 2 '11 at 0:33

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.

share|improve this answer
    
I think the answer will be 7458 based on this method. –  IDS-master May 3 '11 at 1:21

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. :)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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