Results 1 to 3 of 3

Math Help - How to calculate ((a+b)!/a!b!) mod p

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    11

    How to calculate ((a+b)!/a!b!) mod p

    Hi

    I am looking for an efficient way to calculate ((a+b)!/a!b!) mod p. p is prime.

    for example if a=10 and b=7 and p=3 then we need to find (17!/10!.7!) mod 3
    answer =2

    The above can be reduced to (17.16.15.14.13.12.11/7.6.5.4.3.2.1) mod 3

    The problem i am facing is a and b can have a very high value i.e 1<=a<=1000000000 and 1<=b<=1000000000 and value of p is say 531169.
    So how would i programmatically calculate the value, since intermediary calculations might overflow an int variable.
    Since (a/b)mod p != ((a%p)/(b%p)) mod p. Right ?

    Is there a trick involved ?

    Thanks for your patience
    Regards
    lali
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by lali View Post
    Hi
    I am looking for an efficient way to calculate ((a+b)!/a!b!) mod p. p is prime.
    ...
    So how would i programmatically calculate the value, since intermediary calculations might overflow an int variable.
    Since (a/b)mod p != ((a%p)/(b%p)) mod p. Right ?

    Is there a trick involved ?
    There is no "trick", you just need to be systematic.
    You can reduce the magnitude of the numbers by taking the residue of the number mod your prime value.

    If you are going to write a program to arrive at a solution, then getting the answer appears to be more important than efficiency.
    However, if you are doing this by chalk & chalkboard, efficiency is extremely critical.

    My theory is that computer time is cheaper than my time.
    It's a theory because my teachers say my time is worth nothing.

    This may not be efficient but it should be easy to understand:
    suppose:
    Code:
    a=57
    p=3711
     
    'function Factorial_Mod_p(a,p)
    r=1  ''<-- the residue of a number mod p
    for i = 2 to a    'you already have 1 as the first residue
    r = (r * i) mod p
    next i
    return (r)
    code the function
    then call it three times:

    Code:
    ' ((a+b)!/a!b!) mod p
    'supply the real values for a, b, & p
     
    numerator     = Factorial_Mod_p( a+b, P )
    denominator_a = Factorial_Mod_p( a, p )
    denominator_b = Factorial_Mod_p( b, p )
    Since a division is involved you will need to calculate the modular inverse of
    (denominator_a * denominator_b ) mod p

    All of the intermediate values will not exceed p*p
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2009
    Posts
    11
    'function Factorial_Mod_p(a,p)
    r=1 ''<-- the residue of a number mod p
    for i = 2 to a 'you already have 1 as the first residue
    r = (r * i) mod p
    next i
    return (r)
    [/code]code the function
    then call it three times:

    Code:
    ' ((a+b)!/a!b!) mod p
    'supply the real values for a, b, & p
     
    numerator     = Factorial_Mod_p( a+b, P )
    denominator_a = Factorial_Mod_p( a, p )
    denominator_b = Factorial_Mod_p( b, p )
    Since a division is involved you will need to calculate the modular inverse of
    (denominator_a * denominator_b ) mod p

    All of the intermediate values will not exceed p*p
    Suppose a=10 b =7 and p=3( p is always prime in my case)

    So by the above approach i get numberator as 0 and both the denominators as 0.

    However the correct answer is 2. If i use extended euclidean method to solve above problem i get answers i.e 0,1 and 2. However if you do the calculation by hand, the correct answer comes out to be 2.


    By the way, what is the method used to calculate (a/b) mod p ???
    Is extended euclidean method used to calculate (a/b) mod p ????

    Regards
    lali
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is it possible to calculate x and y....
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 29th 2010, 01:16 PM
  2. calculate
    Posted in the Algebra Forum
    Replies: 5
    Last Post: April 27th 2010, 09:35 AM
  3. Calculate
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 14th 2010, 02:11 AM
  4. Calculate M4
    Posted in the Calculus Forum
    Replies: 5
    Last Post: March 29th 2010, 08:44 PM
  5. Calculate this sum
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 28th 2009, 11:50 PM

Search Tags


/mathhelpforum @mathhelpforum