Not at the moment as I'm traveling. Sorry. You could start with
http://en.wikipedia.org/wiki/Modular_arithmetic . The references
might be helpful.
I'll illustrate what Im talking about. Let M=7. Then here is a
table of inverses and checks:
All mod 7 arithmetic
Inverse Check
1 ^ 5 = 1
It's a fact from number theory that
x * (x^(M-2)) = 1 (mod M)
if M is prime. So x^(M-2) is the multiplicative inverse of x (mod
M). It follows by identities of modulo arithmetic that
n!/(r!(n-r)!) = n! * inv(r!) * inv( (n-r)! ) (mod M)
This is what the code is computing. A basic number
could you refer a number theory book..?
On Tue, Mar 6, 2012 at 7:01 AM, Gene gene.ress...@gmail.com wrote:
It's a fact from number theory that
x * (x^(M-2)) = 1 (mod M)
if M is prime. So x^(M-2) is the multiplicative inverse of x (mod
M). It follows by identities of modulo arithmetic
