-2
$\begingroup$

I am basically calculating $^nC_r\bmod p$ where $p$ is a prime..... For large values of $n$ and $r$... As we know $^nC_r$ $$ \frac{n!}{r!(n-r)!} $$ I did a little study of calculating it, but I always ended up in confusion... Using Fermat's Little Theorem, and then dividing by the number (say 'a'), we can get a -1 ... $$ (a^{p-2}\bmod p)\equiv a^{-1} \tag 1 $$ Now, we can write, $^nC_r\bmod p$, as - $$ (ab^{-1})\bmod p $$ Then we can apply the basic formula of Modular Multiplication,

(a * b) mod p = ((a mod p) * (b mod p)) mod p      ------> (2)

Combining Equations (1) and (2), we get,

(a / b) mod p = ((a mod p) * (((b(p - 2) mod p)) mod p)) mod p

Now how do I calculate b (p - 2) mod p ....? I am really confused how do I proceed for large values of 'p' and 'b'.... Or if smaller, how would I calculate something like (15 15 mod 17)...? And also keep in mind that 'a' and 'b' in my actual problem would be factorial of a large number.... So I would be using Modular Multiplication rules used above to calculate (a! mod p).... Please be very clear and specific in the answer, preferably with lots of references, images, examples... (I am a dunce in Maths....! :-P )..... Thanks in advance.....!!

$\endgroup$
1
$\begingroup$

Take your example:

$$15=-2\pmod{17}\implies 15^{15}=(-2)^{16}\cdot (-2)^{-1}\pmod{17}=(-2)^{-1}\pmod{17}$$

and since

$$2\cdot 9=1\pmod{17}\implies (-2)(-9)=1\pmod{17}\implies (-2)^{-1}=-9=8\pmod{17}$$

$\endgroup$
  • $\begingroup$ Thanks a lot for your reply... It clarified a few things.... But that (2 * 9) = 1 (mod 17) thing... How can one come up with such an idea...? I am trying to write the C code for it, and I am confused how I would do that... How would I follow the above method for.... 10240^(142857 - 2) mod 142857...? $\endgroup$ – Vamsi Sangam Oct 8 '14 at 19:57
  • $\begingroup$ @VamsiSangam, in this case is pretty easy to find out. If you wanted to know what is $\;27^{-1}\pmod{97}\;$ that's probably be tougher, though some tricks can be tried: $$27=-70\pmod{97}$$ and now $$97\cdot 3=291=10\cdot 29+1\implies 10\cdot 29=-1\pmod{97}\implies 10^{-1}=-29\pmod{97}$$ and something similar to find $\;7^{-1}\pmod{97}\;$ and then $\;70=7\cdot 10\;$ and etc. $\endgroup$ – Timbuc Oct 8 '14 at 22:39
1
$\begingroup$

You can use divide and conquer technique to calculate ((a^b)(modp)) recursively in O(logb) Time Complexity.

Here is Algorithm:

power(a,b,p): if b == 0: return 1 ret = power(a,b/2,p) ret = (ret * ret)%p if (b % 2) == 1 ret = (ret * a) %p return ret % p

Make function call power(a,p-2,p) to calculate the required result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.