Tuesday, December 16, 2008

Exponent of prime number p in factorial of n (n!)

The exponent of prime number of 3 in 100! is 48.
It means 100! is divisible by 348

How do you find it?
Let p be a prime number and n be a positive integer. Then find the last integer in the sequence 1,2,…,n which is divisible by p.
Express this integer as [n/p]p.
[n/p] denotes the greatest integer less than or equal to n/p

In case of 3 (p) and 100 (n); [n/p] is 33 and n/p is 33 and 1/3.

Let Ep(n) denote the exponent of the prime p in the positive integer n. Then,

Ep(n!) = Ep(1.2.3…(n-1).n)

This will be equal to Ep(p.2p.3p…[n/p]p)
= [n/p]+ Ep(1.2.3...[n/p])

This process continues and we get the answer

Ep(n!) = [n/p] + [n/p²]+…+[n/ps]
Where s is the largest positive integer such that ps≤n≤ps+1

Hence applying the formula to find exponent of prime 3 in 100!

E3(100!) = [100/3] + [100/3²] + [100/3³] + [100/34]
= 33+11+3+1 = 48

Note: remember the meaning of notation [100/3] or [n/p]

No comments: