Calculating (a / b) mod p

Question

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 ¹⁵ 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.....!!

Answer 1

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}$$

Answer 2

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.