Boring Factorials in python

Question

I am trying to understand and solve the following problem :

Sameer and Arpit want to overcome their fear of Maths and so they have been recently practicing Maths problems a lot. Aman, their friend has been helping them out. But as it goes, Sameer and Arpit have got bored of problems involving factorials. Reason being, the factorials are too easy to calculate in problems as they only require the residue modulo some prime and that is easy to calculate in linear time. So to make things interesting for them, Aman - The Mathemagician, gives them an interesting task. He gives them a prime number P and an integer N close to P, and asks them to find N! modulo P. He asks T such queries.

Input :

First line contains an integer T, the number of queries asked.

Next T lines contains T queries of the form “N P”. (quotes for clarity)

Output:

Output exactly T lines, containing N! modulo P.

Example
Input:
3

2 5

5 11

21 71

Output:
2

10

6



Constraints:

1 <= T <= 1000

1 < P <= 2*10^9

1 <= N <= 2*10^9


Abs(N-P) <= 1000

now to this I wrote a solution :

def factorial(c):
n1=1
n2=2
num=1
while num!=c:
    n1=(n1)*(n2)
    n2+=1
    num+=1
return n1


for i in range(int(raw_input())):
    n,p=map(int,raw_input().split())
    print factorial(n)%p

but as you can see this is inefficient solution so I started searching for a better solution than I came to know that this can be solved using wilson's and fermet's theorem.But I am unable to understand what the author is trying to say He says:

**In number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if

Now from this we can write:

(p-1)!   ≡  -1 (mod p)

1*2*3*.........*(n-1)*(n)*..............*(p-1)  ≡   -1 (mod p)

n!*(n+1)*...........*(p-1)   ≡   -1 (mod p)

n!  ≡    -1*[(n+1)*...............(p-2)*(p-1)]^-1 (mod p)

let a=[(n+1)*...............(p-2)*(p-1)]

so

n!≡-1*a^-1(mod p)


From Fermat's Theorem:


a^(p-1) ≡ 1(mod p)

multiply both side by a^-1

a^(p-2)  ≡ a^-1(mod p)

now simply we have to find a^(p-2) mod p

**

so I implemented this:

def factorial1(n,p):            # to calculate  a=[(n+1)*...............(p-2)*(p-1)]
n0=n+1
n1=n0+1
while n1<=(p-1):
    n0=n1*n0
    n1+=1
return n0
# print nf(2,5)

for i in range(10):
    n,p=map(int,raw_input().split())
    if n>p:
        print 0
    elif n==p-1:
        print p-1
    else:
        print (factorial1(n,p)**(p-2))%p   #a^(p-2) mod p

But from the output which I am getting I think I misunderstood what he wrote .Can someone tell me what is he telling me to calculate and how do I write the code for what he is saying.

Answer 1

This is not a straight-forward application of the Wilson's theorem. Along with it use the following facts:

• if n >= p then n! = 0 (mod p)
• if n < p then n! = (p-1)!/[(n+1)(n+2)..(p-1)]. Now use the fact that (p-1)! = -1 (mod p). All that is left for you to find is the modular multiplicative inverse (using extended Euclidean algorithm for example) of the numbers n+1, n+2, ... , p-1 which number is at most 1000 from the fact that abs(n-p) <= 1000. Multiply (p-1)! = -1 (mod p) with all modular multiplicative inverse of the numbers n+1, n+2, ... , p-1 and you get the answer. (as John Coleman pointed out you could also do a inverse of the the product and not product of the inverse as an optimization)

In your case n=2, p=5 (just to see how it works)

n! = 2! = 4!/(3*4) = (-1)*2*4 = 2 (mod 5)

# 2 is modular inverse of 3 since 2*3 = 1 (mod 5)
# 4 is modular inverse of 4 since 4*4 = 1 (mod 5)