Euler Problem 97: Find last 10 digits of a big prime number

First, I'm glad that I've managed to solve 39 problems by now. Since the last problem, I don't find really interesting example to blog, but this problem 97 deserves a blog. Not really because Scala is good in answering this, but because the problem itself is interesting.


The problem is expressed in a little bit history of prime number, but finally the real problem is here: "What is the 10 last digits of the following prime number: 284332^7830457+ 1. Looks intimidating, right ? Try give a try calculating 28433 * (2: BigInt).pow(7830457) won't work, simply because its too large. Another thing is needed.

The other thing is the modular exponentiation, excellently explained here: http://en.wikipedia.org/wiki/Modular_exponentiation . Basically, the techniques are very useful to compute b^p mod m by observing that (a*b) mod m = ( (a mod m)  * (b mod m) ) mod m. 

Taking that into account,   b² mod m can be calculated as ( (b mod m) * (b mod m) )  mod m, and 

b³ mod m =( ( b mod m) * ( b² mod m) )mod m and so on. 

When this is translated to Scala it becomes:

 1 dev div(b: Long, exp: Long, m: BigInt): BigInt = {
 2   def div(b: Long, counter: Long, 
 3         m: BigInt, result: BigInt): BigInt = {
 4    if (counter == 0) 
 5       result
 6 
 7     else div(b, counter - 1, m, (result * b) % m)
 8   }
 9   div(b, exp, m, 1)
10 }

With this in our hand, we can then get the last 10 digit of 2^7830457 which nothing less than  2^7830457

mod 10000000000. Using div method above, we can get then the last 10 digits of the term. We can multiply the result with 28433 and then add 1 to get the answer to the problem.

OK. That was my 39th solved problem.