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'm trying to solve some problems on interviewstreet. For some problems they mention As the answers can be very big, output them modulo 1000000007. How can I compute a*b mod N where N is a large number like 1000000007.

I thought of using

(a mod N) * (b mod N) = (a*b mod N)

but I reckon performing this wouldn't work. Example :

a=4, b=5 and N=10
(4 mod 10) * (5 mod 10) = 20
whereas (4*5 mod 10) = 2

Can somebody guide me in the right direction.

share|improve this question
1  
(1) You need (a mod N)*(b mod N) mod N. (2) $20\equiv2\bmod 10$ is incorrect. –  anon Jun 1 '12 at 20:25
2  
How is $4\times 5\pmod{10}=2$? –  Asaf Karagila Jun 1 '12 at 20:28
    
I mean the remainder by mod. –  nikhil Jun 1 '12 at 20:37
    
@nikhil If you divide 20 by 10 the remainder is 0 though! –  rschwieb Jun 1 '12 at 20:47
    
oopsie my bad! You're right I got a bit confused. –  nikhil Jun 1 '12 at 20:49

1 Answer 1

up vote 3 down vote accepted

You can do the mod any time you like, before multiplication or after.

For another thing $4*5\equiv 0\pmod{10}$, not 2.

For example $16*12\equiv 192\equiv 2\pmod{10}$ and also

$16*12\equiv (10+6)*(10+2)\equiv 6*2\equiv 12\equiv 2\pmod{10}$

It's always advisable to mod before you multiply, as it will keep the numbers as small as possible.

share|improve this answer
    
But note that, as in the example, you may have to mod again after you multiply, because the product of two numbers less than N can still be greater than N. You can't really avoid the divide - and in the case of multiplying mod 1000000007 , this means that your intermediate won't necessarily fit in 32 bits so you may need to use 64-bit integers for intermediate results. –  Steven Stadnicki Jun 1 '12 at 21:01
    
To add onto StevenStadnicki's observation: From the mathematician's point of view, there's no problem with $12\pmod{10}$, it's just that $12$ and $2$ are identical, so you can interchange them. I suppose for computer science there would be a strong impetus to reduce in order to save memory. –  rschwieb Jun 1 '12 at 21:08

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.