There is no "trick", you just need to be systematic.
Originally Posted by lali
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:
code the function
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
then call it three times:
Since a division is involved you will need to calculate the modular inverse of
' ((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 )
(denominator_a * denominator_b ) mod p
All of the intermediate values will not exceed p*p