Highest Power of a Prime Number P in N!

Factorial of a number is the adjacent multiplication of the integers that are less than n, which is the given number. To find the highest power of any prime number in n! a formula is adopted. This formula is used to find the exponent of prime in a given factorial. This article covers the formula which is used and the explanation of the formula broken down into single terms. To understand the concept better, examples of solved problems are given.

The exponent of prime number in a factorial

For any given factorial their prime factors and their powers can be found. Assume n! and its prime factors 2,3,5,7…

   n! = 2e1.3e2.5e3…

e1 is the highest power of the prime number 2,

e2 is the highest power of the prime number 3, and so on…

For n of smaller values, the powers can be found but for larger values, it is humanly impossible to find them by the regular method. Here to find the power, the exponent of prime in a factorial is applied. This formula helps to find the power in fewer steps and time. Let us look at the derivation of the formula and how it is applied.

Formula to find the highest power of a prime number in N!

Let us assume n as a positive integer and its factorial can be defined as,

  n! = p1e1.p2e2.p3e3….

The exponent of any prime in a factorial is given by,

 e1 = [n/p1] + [n/p12] + [n/p13] …

Here, [.] is the greatest integer function.

The exponent of p2 is,

e2 = [n/p2] + [n/p22] + [n/p23] …

Here, [.] is the greatest integer function.

The above formula can be used to find the power of any prime number of a given factorial.

The general equation to find the power of any prime number in factorial is given as,

       E = [n/p] + [n/p2] + [n/p3] …

Let us try to get a clear picture of this formula,

•   The first term in the formula is to find the total number of terms that are multiplies of p and this contributes one p.
•   The Second term counts the total terms that are multiples of p2 and that are less than N and adds them.
•   This process is repeated with every power of p.

Examples

Let us look at some solved problems to understand the exponent of prime in factorial.

1. Find the exponent of 5 in 100!

The exponent of any prime in a factorial is given by,

 e1 = [n/p1] + [n/p12] + [n/p13] …

 Here n = 100 and p1 = 5

 e1 = [100/5] + [100/25] + [100/125] …

 e1 = 20 + 4 + 0

 e1 = 24

The power of 5 in 100! is 24.

2. Find the exponent of 2 in 64!

  The exponent of any prime in a factorial is given by,

e1 = [n/p1] + [n/p12] + [n/p13] …

 Here n = 64 and p1 = 2

 e1 = [64/2] + [64/4] + [64/8] + [64/16] + [64/32] + [64/64] …

 e1 = 32 + 16 + 8 + 4 + 2 + 1 + 0

 e1 = 63

The power of 2 in 64! is 63.

3. What is the highest power of 5 that can divide 2000! without remainder?

  The exponent of any prime in a factorial is given by,

  e1 = [n/p1] + [n/p12] + [n/p13] …

 Here n = 2000 and p1 = 5

 e1 = [2000/5] + [2000/25] + [2000/125] + [2000/625] …

 e1 = 400 + 80 + 16 + 3

e1 = 499

The highest power of 5 in 2000! is 499.

4. Find the maximum value of n such that 7n divides 1000!

 The exponent of any prime in a factorial is given by,

e1 = [n/p1] + [n/p12] + [n/p13] …

 Here n = 1000 and p1 = 7

 e1 = [1000/7] + [1000/49] + [1000/343] …

 e1 = 142 + 20 + 2 + 0

 e1 = 164

The highest power of 7 in 1000! is 164. So, the value of n is 164.

5. Find the exponent of 11 in 11011!

The exponent of any prime in a factorial is given by,

e1 = [n/p1] + [n/p12] + [n/p13] …

 Here n = 11011 and p1 = 11

 e1 = [11011/11] + [11011/121] + [11011/1331] …

 e1 = 1001 + 91 + 8 + 0

 e1 = 1100

The power of 11 in 11011! is 1100.

Conclusion

We learned about how to find the highest power of a prime number in n! using Legendre’s formula. This method comes in handy when the factorial number is large. It takes lesser time to find the power of a particular prime number this method, so it is widely used. Understanding how this formula works can boost the problems solving skills in further fields of mathematics.