Results 1 to 2 of 2

Math Help - How to calculate nCr mod p where p is prime

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    11

    How to calculate nCr mod p where p is prime

    Hi,

    In n and r are quite large so that calculating their factorial is somewhat infeasible, how would one approach to find the solution to nCr mod p (nCr stands for n choose r) where p is a prime number ?

    simple example: n=17 , r= 7 p =3 answer =2;
    But what if n and r are of the order 2*10^9 and 10^9 respectively and p is a prime number say 103.

    Please provide some guidance.
    Thanks for your patience.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member Infophile's Avatar
    Joined
    May 2009
    Posts
    50
    Hello,

    You can use Lucas' theorem :

    If you write \left\{\begin{array}{l}n=n_dp^d+n_{d-1}p^{d-1}+...+n_1p+n_0\\k=k_dp^d+k_{d-1}p^{d-1}+...+k_1p+k_0\end{array}\right.

    Then \color{blue}\boxed{C_n^k\equiv C_{n_d}^{k_d}C_{n_{d-1}}^{k_{d-1}}...C_{n_1}^{k_1}C_{n_0}^{k_0}~\text{mod}~p}

    It is nice, isn't it ?

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  2. Replies: 1
    Last Post: June 19th 2011, 01:56 PM
  3. Replies: 3
    Last Post: February 17th 2011, 08:51 AM
  4. why is a prime squared + itself + 1 also a prime
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: November 19th 2010, 08:03 PM
  5. Replies: 6
    Last Post: August 28th 2010, 12:44 AM

Search Tags


/mathhelpforum @mathhelpforum