×

# Modulo 10^9 +7

 2 1 Why are we ask to take modulo 10^9 + 7 (1000000007) in many problems? What is the arithmetic logic behind it can anyone clear it out? Thanks! asked 08 May '14, 19:15 2★tech_boy 1.2k●4●19●31 accept rate: 7%

 5 Quoting Anton Lunyov, " It is the first 10-digital prime number. In some of such problems to compute the result modular inverses are needed and it helps very much that this number is prime. Also this number should be large enough since otherwise modular inverses technique may fail in some situations. In fact any prime number less then 2^30 will be fine in order to prevent possible overflows. But this one can be easily written as 10^9+7. This reasoning almost uniquely determined this number :) " Source: What's significant about the number choice 1000000007? answered 08 May '14, 19:52 3.4k●19●43●75 accept rate: 16%
 1 The above operation guarentees that the result after operation fits in integer data type i.e it makes sure that there is no over flow in result answered 08 May '14, 19:28 3★winux 16●1●4 accept rate: 0%
 0 you can get more varied results in modulo operation by taking modulo with large numbers and even more varied if the number is prime. so 10^9 + 7 fits well in this category and this allows tester to be sure to get large range of outputs which is less likely if number is not prime. answered 10 May '14, 02:24 787●9●15●28 accept rate: 6%
 0 can someone give more particular example please ? like for 7500 what should I display? answered 22 Mar '15, 23:45 1 accept rate: 0%
 0 answered 11 Aug '16, 22:14 0★spr493 1 accept rate: 0%
 0 As it is the first ten digit prime number and can be suitable to store in 32 bits so it is easy to perform multiplications when the variable is less than 32 bits. link This answer is marked "community wiki". answered 10 Nov '17, 22:19 0 accept rate: 0%
 0 ^Give it a look :) answered 14 Nov '17, 17:32 3★ricksr 16●1 accept rate: 6%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×323

question asked: 08 May '14, 19:15

question was seen: 16,412 times

last updated: 14 Nov '17, 17:32