Number Theory-1

slide1

Factorial is an important topic in various competitive exams based quantitative aptitude.Factorial topic finds its application in Permutation and Combinations , Probability , Number theory ,etc…

Factorial number or n! is the product of n consecutive natural numbers starting from 1 to n.

The notation of factorial  was introduced by Christian Kramp in 1808.

 

  For example : 7 ! =7 x 6 x 5 x 4 x 3 x 2 x 1 = 5040 

Here are some factorial values of some values.It is good if you can remember (because they come handy in fast calculation) .Try to keep in mind these values similar to multiplication table you did in your schools.

1! = 1

2! = 2

3! = 6

4!= 24

5!=120

6!= 720

7! = 5040

8! = 40320

 

Some of the commonly asked questions based  on the concept of factorials and number of trailing zeros  in the various exams :

 

1.Highest power of a number in a factorial or in a product

 2. Number of zeros in the end of a factorial or a product

 3.Number of factors of any factorial

 4. Highest power of a number in a factorial or in a product.

 

” Highest power of a prime number in a factorial or in a product “

Let us first understand what do we mean by ” Highest Power ” ?

Consider a number N= p^2 k^ 1.

Here the highest power of “p” in N will be 2 and the highest power of “k” in N will be 1.

To find the highest Power of factor in the given factorial can be obtained by continuously dividing the number by whose highest power of factor  is to be found & we will be approximating the quotients obtained after each division and adding up ! This result after the adding all quotients , we will be obtaining the highest power of a number in the given factorial.

slide1slide2slide3

Lets look at some examples..

Q. 1 ) Find the highest power of 5 in 30!

Solution:  30/5= 6 ; 6/5=1;

Adding the quotients, its 6+1=7

So highest power of 5 in 30! = 7

 

Q. 2 ) Find the highest power of 2 in 50 !

Solution:  50/2= 25 ; 25/2=12; 12/2 =6 ; 6/2 = 3 ; 3/2 = 1

Adding the quotients, its 25+12+6+3 +1= 47

So highest power of 2 in 50! = 47

 

Q.3)  What is the highest power of 5 such that the number divided 125! ?

Solution :    [125/5] + [125/25] + [125/125] = 25+5+1 = 31

                       Highest power of 5 in 125! = 31

                       Hence 5^31 divided 125!

Q.4)  Find the highest power of 3 in 100!

Solution :

       = [100/3] + [100/32] + [100/33] + [100/34] + [100/35] + …

       = 33 + 11 + 3 + 1 + 0 (from here on greatest integer function evaluates to zero)

       = 48.

Q.5) Find the highest power of  2 in 100!

Solution :-   =  [100/2]+[100/2^2]+[100/2^3]+[100/2^4]+[100/2^5]+[100/2^6]

                        = 50+25+12+6+3+1

                       =97.

 

” Highest number of a composite number in the given factorial value”

Finding the highest power of composite number in the given factorial value is as follows.

       Step 1  :   Factorize the composite  number into prime factorization ( or canonical form) .

      Step 2  :  Find the highest power of all the prime numbers in that factorial using the previous method.

    Step 3 :  Take the least power.

Q.1 ) What is  the highest power of 10 in 100!

Solution:   Lets first factorize  10 as 5 x 2.

   Step 1 :Highest power of 5 in 100! =24

   Step 2 : Highest power of 2 in 100! =97 ( as already  obtained ) .

   Step 3 :   Therefore, the answer will be 24, because to get a 10, you need a pair of 2 and 5, and only 24 such pairs are available. So take the lesser value i.e. 24 is the answer.

 

 

Q.2 ) What is  the highest power of 12 in 100!

Solution:   Lets first factorize  12 as 2^2 x 3.

   Step 1 :Highest power of 2 in 100! = 97 ( for method look at above examples)

So , the highest power of 4 ( i.e 2^2 ) is 97 /2 = 48

   Step 2 : Highest power of 3  in 100! = 48 ( as already  obtained ) .

   Step 3 :   Therefore, the answer will be 48, because to get a 10, you need a pair of 2 and 5, and only 48 such pairs are available. So take the lesser value i.e. 48 is the answer.

 

 

Q.3 ) What is  the highest power of 12 in 30!

Solution:   Lets first factorize  12 as 3 x 2^2 .

   Step 1 :Highest power of 3  in 30! 

(30/3) + ( 30/9) + ( 30/27) +……

   = 14

 

   Step 2 : Highest power of 2 in 30! = ( as already  obtained ) .

=  [30/2] + [30/4] + [30/8] + [30/16]

= 26

Therefore , the highest power of ( 2^2) i.e 4 is 13

   Step 3 :   Therefore, the answer will be 13, because to get a 10, you need a pair of 2 and 5, and only 13 such pairs are available. So take the lesser value i.e. 13 is the answer.

 

 

Q.4) What is  the highest power of 72 in 100!

Solution:   Lets first factorize  72 as 3^2 x 2^3 .

   Step 1 :Highest power of 3  in 100! 

(100/3) + ( 100/9) + ( 100/27) +……

 = 48

But , here the power of 3 is 2 . Therefore highest power of 3^2 (i.e 9) is 48/2 = 24.

   Step 2 : Highest power of 2 in 30! = ( as already  obtained ) .

=  [100/2] + [100/4] + [100/8] + [100/16]+…..

=97

Therefore , the highest power of ( 2^3) i.e 8 is 97/3 = 32.

   Step 3 :   Therefore, the answer will be 24, because to get a 10, you need a pair of 2 and 5, and only 24 such pairs are available. So take the lesser value i.e. 24 is the answer.

 

 

             ” Number of zeros in the end of a factorial value or a product”

Find the number of trailing zeros ( zeros at the end ) of the factorial value is simple as discussed earlier. We can say it as special case of the above problems.

 Number of zeros in the end depends on the number of 10s(  i.e. effectively, on the number of 5s).

In this method , we need to find the highest power of 5 in the factorial value by successive divison.

 

Q.1) Find the number of zeros in 30! .

          Solution : [30/5] + [30/25]

                             = 6+1 = 7

 

Q.2) Find the number of zeros in 100! .

          Solution : [100/5] + [100/25] + …

                            = 20 + 4 + 0 + … = 24.

Q.3) Find the number of zeros in 250! .

          Solution :  [ 250 / 5 ] + [ 250 / 5^2 ] + [ 250 / 5^3 ]

                            = 50 + 10 + 2

                           = 62.

Q.4) Find the number of zeros in 15! .

          Solution : [15/5] + [15/25] + …

                            = 3  + … 

                            =3

 

Above questions were related to the base 10 system , i,e they need 5 and 2 to get 10.

Now , what if it is other than base 10 . Like base 7 , base 13 ,etc….

Lets take base N as general one and learn the concept

In base N system, number of zeroes in the end is nothing but the highest power of N in that product.

 

Q.1) Find the highest power of 7 in 100!.

Solution:    [100/7] + [100/49] + … = 14 + 2 = 16.

                      There will be 16 zeros at the end of 100! in base 7

 

Q.2)  Find the trailing zeros in 13! as in base 10 .

Solution:    [13/5] + [13/25] + … = 2 +..  = 2

                      There will be 2 zeros at the end of 13! in base 10

Q.3) Find the number of zeros in the end of 15! as in the base 12.

Solution:    Highest power of 2 in 15!

= 15/2=7

7/2=3

3/2=1

Total =11.

Highest power of 22 (i.e 4) = 11/2=5

Highest power of 3 in 15!= 5

Thus, the highest power of 12 in 15! = 5

 

Some more examples :-

 

Q.1)  Find the total no of divisors of 17!

Solution :-   Prime factors are 2,3,5,7,11,13,17.

Highest power of 2 =[17/2] + [ 17/2^2] + [ 17/2^3] + [17/2^4]

8+4+2+1 = 17.

Highest power of 3 = [17/3] + [17/3^2]

5+1 = 6.

Highest power of 5 = [17/5] + [17/5^2] = 3.

Highest power of 7 = [17/7] + [17/7^2] = 2.

Highest power of 11 = [17/11] = 1.

Highest power of 13 = [17/13] = 1.

Highest power of 17 = [17/17] = 1.

17! = 2^17 x 3^6 x 5^3 x 7^2 x 11 x 13 x 17

Factors = (17+1)(6+1)(3+1)(2+1)(1+1)(1+1)(1+1)

= 18 x 7 x 4 x 3 x 2 x 2 x 2

= 126 x 96

= 12096

 

Q.2)  Find the least number which has highest power of 6 as 23.

Solution : 

23 = ( n/6) +(n/ 6^2) +…

23 = (n/6) +( n/36) 

By trail and error or  by solving the above equation , we get  121 as the answer.

 

Wilson’s theorem

For every prime number p,  (p-1)! + 1 is divisible by p

Consider for example: -p =7

According to  Wilson’s theorem,  7 is prime only if (6!) + 1 is divisible by 7 .

some useful results derived from Wilson’s theorem

Remainder [ (p-1)!/p] = p – 1 ( where p is a prime number )

Remainder [ 6!/7 ] = 7; Remainder [100!/101] = 100 and so on…

Remainder [ (p-2)!/p] = 1 ( where p is a prime number )

Remainder [ 5!/7 ] = 1; Remainder [99!/101] = 1

 

“To find the non zero digit from right “

If we have to find first non zero digit from right in any number n!

First of all divide  n by 5 and represent in the form shown below and follow next steps..     

          n = 5 x p + k.

 Rightmost Digit in ‘n! ‘ is given as    2^p x p! x k! .

 

Now , let’s look into examples to understand the concept.

Q.1) Find the rightmost digit in 6!

   Solution :

  6 = 5 x 1 +1 

      Here ,  n = 6 , p = 1 , k =1

   Right most digit = 2^p x p! x k !

                                     = 2^1 x (1!) x( 1!) 

                                     =2

 

Q.2) Find the rightmost digit in 11!

   Solution :

  11 = 5 x 2 +1 

      Here ,  n = 11, p = 2 , k =1

   Right most digit = 2^p x p! x k !

                                     = 2^2 x (2!) x( 1!) 

                                     =8

Q.3) Find the rightmost digit in 9 !

   Solution :

  9 = 5 x 1 +4 

      Here ,  n = 9 , p = 1 , k =4

   Right most digit = 2^p x p! x k !

                                     = 2^1 x (1!) x( 4!) 

                                     =8

Q.4) Find the rightmost digit in 24 !

   Solution :

  24= 5 x 4 +4 

      Here ,  n = 24 , p = 4, k =4

   Right most digit = 2^p x p! x k !

                                     = 2^4 x (4!) x( 4!) 

                                     = 16 x 24 x24

 = xxx6 ( Check on Wolfram Alpha)

 ( Don’t waste your time in finding the whole answer, you will not be rewarded for the value of it).

 

 

 

 

Advertisements

About Praveenkumar P Kalikeri

ABOUT US Hey,Thanks for dropping by .First I would like to Appreciate for your love towards the Mathematics Subject. My name is Praveenkumar Kalikeri. I'm an Engineering Student from Karnataka , India. My Passion for Mathematics , encouraged me to start this blog . I Started loving the Mathematics subject from my schooling days.I was greatly motivated by teachers, parents who always helped me .        Numbers have Beauty !! They fascinated me .. As we all know best method to try out something new is to study old theories , concepts , its drawbacks, etc. I ,myself Started learning Vedic Mathematics at age of 15. Here , I will share vedic maths tricks learned and modified by me in simple manner which will be useful in various competitive exams. "If You Believe , You Can Do".
This entry was posted in Aptitude Concepts & Questions, Mathematics and tagged , , , , , , , . Bookmark the permalink.