Number Theory February

An Editorial on Hackerrank gave a really nice review of certain number theory concepts:-

Namely

1. Lucas' Theorem to determinemodulo p where p is prime.
2. Chineese remainder theoram to find x modulo (a1.a2)  where x modulo(a1) and x modulo(a2) are given.
3. Extended Euclidean algorithm to find pair of integers c1,c2 such that. 

So remaining posts will be about these concepts only.

 Lucas' theorem

                                        

Where

                            

                               

Images taken from :- Lucas Theorem Wikipedia

But these images don't provide much of an explaination as such, (at least when I read them)

The approach of Lucas' thoram can be summarized by a simple procedure In the following manner. To find the  modulp p where p is a prime

1. Express m in the base p 
2. Express n in the base p
3. Incase the expansion of n contains less number of digits than m, pad leading zeroes to the left of the expansion of n
4. Take digitwise combination of each pair of digits.
5. Multiply the obtained terms to find the value of desired combination and take modulo p.

As usual the proof is still not touched because haven't been able to prove it using my own arguements do look at the wikipedia article for the proof incase needed.

Now will be building our number theory library so hence I will be posting the codes for the above mentioned theorams:-

Python :-

1. from math import factorial  
2. f=factorial  
3. def ncr(a,b):  
4.     if b>a:  
5.         return 0  
6.     return f(a)/(f(a-b)*f(b))  
7. def conv(a,b):  
8.     s=[]  
9.     while a:  
10.         s.append(a%b)  
11.         a=a//b  
12.     return s[::-1]  
13. def main():  
14.     n,m,p=map(int,raw_input().split()) #input m , n and the prime  
15.     k1=conv(n,p) #convert to base p  
16.     k2=conv(m,p)  
17.     if len(k2) < len(k1):  
18.         k2= [0]*(len(k1)-len(k2))+k2 #pad in leading zeroes  
19.     l=[]  
20.     for i in xrange(len(k1)):  
21.         l.append(ncr(k1[i],k2[i])) #take digitwise ncr  
22.     prod=1  
23.     for i in l:  
24.         prod*=i  
25.         prod%=p  
26.     print prod  
27. main()