what is the significance of modulo 10^9+7 used in codechef and spoj problems?

Question

I was working on a problem which requires output as "For each line output the answer modulo 10^9+7". Why is modulo 10^9+7 included in the problem? What is its significance?

I'm not looking for a solution to the problem; only the significance of that particular constant.

Answer 1

Problems ask for results modulo primes because the alternatives, namely asking for a floating-point result giving the "high-order bits" and asking for the whole result, aren't always what the problem setter is looking for.

• These problems are often "find and implement a recurrence" problems. The low-order bits will often tell you whether the recurrence you found is right.
• There may be a special trick for the "high-order bits" problem, perhaps based on a clever analytic approximation.
• The reason people don't often ask for the whole result is that this requires the contestant to implement big-number arithmetic.
• Problem setters usually don't want unexpected tricks to crack their problems for "the wrong reasons."

10^9+7 winds up being a pretty good choice of prime. It is a "safe prime." What that means:

10^9+7 is a prime number. This means that the "Chinese remainder trick" doesn't apply; if you're trying to work something out modulo a product of two primes, say pq, then you can work it out modulo p and modulo q and use the extended Euclidean algorithm to put the pieces together.

More than that, 10^9+6, which is 10^9+7-1, is twice a prime. So the multiplicative group modulo 10^9+7 doesn't decompose into small things and hence no Chinese-remainder-like trick applies there.

Answer 2

In some problems the answers are very big numbers, but forcing you to implement long arighmetics is not the purpose of the problem authors. Therefore they ask you to calculate answer modulo some number, like 1000000007, so you don't have to implement long arithmetics, but the answer is still verifiable.