Divisors of a Number – Sum and Product of Divisors
January 31, 2014
Highest Common Factor
April 8, 2014In this post, we will have a look at the tips and techniques to calculate the Highest Power of a Number in a Factorial. We will start by understanding an important concept called Greatest Integer Function which is required to calculate the maximum power in a factorial. Post this we will look into the technique on how to calculate the highest power of a number N in a factorial based on whether the number N is a prime or composite.
At the end of this post, we have a quiz based on this topic. Take this quiz to test your understanding.
Also, after you complete this post, please do let us know if you found this post helpful with your comment. Thanks in advance.
Video:
What is a Factorial?
Factorial of a number n is given by
$n! = n$ x $(n-1)$ x $(n-2)$ x $(n-3)…2$ x $1$.
For example, factorial of 4 is given by 4! = 4 x 3 x 2 x 1 = 24
Now, Given a number x, how do we find the highest power of x in n! ? In order to solve this, we must first understand the concept of Greatest Integer Function.
Greatest Integer Function:
If x is an integer, then the greatest integer function of x is the greatest integer that is less than or equal to x. It is represented by [x]
Example:
1. Greatest Integer less than or equal to 2.1 => [2.1] = 2
2. [1.9] = 1
3. [-2.1] = -3 (Since -3 is the greatest integer that is less than or equal to -2.1)
Calculating Highest power of a number in a factorial.
If $p$ is prime number, then the highest power of $p$ in a factorial $n$ is given by
$[\frac{n}{p}] + [\frac{n}{p^2}] + [\frac{n}{p^3}] + …$
Highest Power of prime number in factorial
Calculation of the maximum power of a prime number in a factorial simply involves using the formula described above.
Example 1: Highest power of 3 in 15!
Highest power of 3 in 15! is given by,
=> $[\frac{15}{3}] + [\frac{15}{3^2}] + [\frac{15}{3^3}] + …$
=> 5 + 1 + 0
=> 6
Example 2: Maximum power of 2 in 48!
This is given by,
=> $[\frac{48}{2}] + [\frac{48}{2^2}] + [\frac{48}{2^3}] + [\frac{48}{2^4}] + [\frac{48}{2^5}] + [\frac{48}{2^6}] + …$
=> $[\frac{48}{2}] + [\frac{48}{4}] + [\frac{48}{8}] + [\frac{48}{16}] + [\frac{48}{32}] + [\frac{48}{64}] + …$
=> 24 + 12 + 6 + 3 + 1 + 0
=> 46
Example 3: Maximum power of 3 in 50!
=> $[\frac{50}{3}] + [\frac{50}{3^2}] + [\frac{50}{3^3}] +[\frac{50}{3^4}] + …$
=> $[\frac{50}{3}] + [\frac{50}{9}] + [\frac{50}{27}] +[\frac{50}{81}] + …$
=> 16 + 5 + 1 + 0
=> 22
Highest Power of composite number in a factorial
To calculate the highest power of composite number in a factorial, we first express the composite number as a product of primes. Among these prime factors, the highest power of the largest prime factor will be equal to the highest power of that composite number. Lets look into this with the help of following examples.
[toggles type=”multiple”][toggle title=”Example 4: Highest power of 15 in 24!”]
Step 1: Express 15 in terms of its prime factors
15 = 3 x 5
Step 2 : Among the two prime factors, the maximum of larger prime number will always be less than the maximum of of lower prime factor. Accordingly, among the prime factors 3 and 5, highest power of 5 in 24! will be less than the highest power of 3 in 24!.
Hence the highest power of 15 in 24! will be equal to the highest power of 5 in 24!
Highest power of 5 in 24! = [$\frac{24}{5}$] + [$\frac{24}{5^2}$]
= 4 + 0 = 4
Hence the highest power of 15 in 24! = 4
Example 5: Find the maximum power of 6 which can divide 120! without leaving a remainder!
Step 1: Express 6 in terms of its prime factors
6 = 2 x 3
Step 2 : Among the prime factors 2 and 3, highest power of 3 in 120! will be less than the highest power of 2 in 120!. Hence the highest power of 6 in 120! will be equal to the highest power of 3 in 120!
Maximum power of 6 in 120! is given by Highest power of 3 in 120!
=> [$\frac{120}{3}$] + [$\frac{120}{3^2}$] + [$\frac{120}{3^3}$] + [$\frac{120}{3^4}$] + [$\frac{120}{3^5}$]
=> [$\frac{120}{3}$] + [$\frac{120}{9}$] + [$\frac{120}{27}$] + [$\frac{120}{81}$] + [$\frac{120}{243}$]
=> 40 + 13 + 4 + 1 + 0
=> 58
Hence the maximum power of 6 which can divide 120! without leaving a remainder is 58.
Example 6: Find the maximum power of 15 in 75!
Step 1: Express 15 in terms of its prime factors
15 = 3 x 5
Step 2 : Among the prime factors 3 and 5, highest power of 5 in 75! will be less than the highest power of 5 in 75!.
Therefore, the highest power of 15 in 75! will be equal to the highest power of 5 in 75!
=> [$\frac{75}{5}$] + [$\frac{75}{5^2}$] + [$\frac{75}{5^3}$]
=> 15 + 3 + 0 = 18
Hence the highest power of 15 in 75! = 18
Note: If $p$ is a prime number, highest power of $p^a$ present in a factorial n is given by
[$\frac{\text{Highest power of p in n!}}{a}$]
Example 7: Maximum power of 9 in 32!
9 in terms of its prime factors is expressed as $3^2$
Highest power of 3$^2$ in 32! => [$\frac{\text{Highest power of 3 in 32!}}{2}$]
=> [$\frac{\frac{32}{3} + \frac{32}{3^2} + \frac{32}{3^3}}{2}$]
=> [$\frac{10 + 3 + 1}{2}$] => 7
Example 8: Find the maximum power of 8 in 100!
8 in terms of its prime factors is expressed as $2^3$
Maximum power of 2$^3$ in 100!
=> [$\frac{\text{Maximum power of 2 in 100!}}{3}$]
=> [$\frac{\frac{100}{2} + \frac{100}{2^2} + \frac{100}{2^3} + \frac{100}{2^4} + \frac{100}{2^5} + \frac{100}{2^6} + \frac{100}{2^7}}{3}$]
=> [$\frac{50 + 25 + 12 + 6 + 3 + 1 + 0}{3}$]
=> [$\frac{97}{3}$] => 32
Example 9: What is the highest power of 12 that divides 54!
12 in terms of its prime factors is expressed as $2^2$ x 3
Maximum power of 2$^2$ in 54! => [$\frac{\text{Maximum power of 2 in 54!}}{2}$]
=> [$\frac{\frac{54}{2} + \frac{54}{2^2} + \frac{54}{2^3} + \frac{54}{2^4} + \frac{54}{2^5} + \frac{54}{2^6}}{2}$]
=> [$\frac{27 + 13 + 6 + 3 + 1 + 0}{2}$]
=> [$\frac{50}{2}$] => 25
Maximum power of 3 in 54!
=> [$\frac{54}{3}$] + [$\frac{54}{3^2}$] + [$\frac{54}{3^3} + \frac{54}{3^4}$]
=> 18 + 6 + 2 + 0
=> 26
Since the maximum power of 2$^2$ is less than the maximum power of 3, the maximum power of 12 in 54! will be equal to the maximum power of 2$^2$ in 54! which is 25.
Example 10: Find the maximum power of 40 in 120!
40 in terms of its prime factors is expressed as $2^3$ x 5
Maximum power of 2$^3$ in 120! => [$\frac{\text{Maximum power of 2 in 120!}}{3}$]
=> [$\frac{\frac{120}{2} + \frac{120}{2^2} + \frac{120}{2^3} + \frac{120}{2^4} + \frac{120}{2^5} + \frac{120}{2^6} + \frac{120}{2^7}}{3}$]
=> [$\frac{60 + 30 + 15 + 7 + 3 + 1 + 0}{3}$]
=> [$\frac{160}{3}$] => 38
Maximum power of 5 in 120!
=> [$\frac{120}{5}$] + [$\frac{120}{5^2}$] + [$\frac{120}{5^3}$]
=> 24 + 4 + 0
=> 28
Since the maximum power of 5 is less than the maximum power of 2$^3$, the maximum power of 40 in 120! will be equal to the maximum power of 5 in 120! which is 28.
Quiz : Test your Understanding
What Next?
Please do try our android app – Math Tricks Workout. The app is developed to improve mental arithmetic using a series of left to right fast math workouts.
Scan the QR code below or click on it for more details.
2 Comments
suppose if we have to find the highest power if 2 in 17!,
then it would take
[17/2]+[17/2^2]+…..+[17/2^5]
=>8+4+2+1+0
=>15
In my opinion i think we should proceed and find till when the GIF becomes zero .
IS IT RIGHT???
This is also right but kind of take much more calculation .. instead use
17/2=8
8/2= 4
4/2= 2
2/2= 1
Then add all the values like 8+4+2+1= 15.