3
$\begingroup$

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.

  • 1
    (1) You need `(a mod N)*(b mod N) mod N`. (2) $20\equiv2\bmod 10$ is incorrect.2012-06-01
  • 2
    How is $4\times 5\pmod{10}=2$?2012-06-01
  • 0
    I mean the remainder by mod.2012-06-01
  • 0
    @nikhil If you divide 20 by 10 the remainder is 0 though!2012-06-01
  • 0
    oopsie my bad! You're right I got a bit confused.2012-06-01
  • 0
    @nikhil You can edit the question to correct the confusion.2012-06-01

1 Answers 1

4

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.

  • 0
    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.2012-06-01
  • 0
    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.2012-06-01