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

^{2 }mod m can be calculated as ( (b mod m) * (b mod m) ) mod m, andb

^{3 }mod m =( ( b mod m) * ( b^{2 }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

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.^{7830457 }which nothing less than*2*^{7830457}OK. That was my 39th solved problem.

## No comments:

Post a Comment