Factorial - Kamal Lohia


  • Faculty and Content Developer at Tathagat | Delhi College of Engineering


    Factorials

    How to find power of a prime number contained in a factorial

    No theory. Direct result.

    Find the highest power of 2 contained in 200!

    Just divide 200 by 2 and add the quotient thus obtained divided by 2 and so on. See how.

    200! Contains 100 + 50 + 25 + 12 + 6 + 3 + 1 = 197 powers of 2.

    One more: Find the number of zeroes at the end of the number 200!

    This time we need to find the powers of 5, so we need to divide 200 and subsequent quotients by 5 and add them to get the answer as 40 + 8 + 1 = 49.

    So 200! ends in exactly 49 zeroes at the end.

    How to find power of a composite number contained in a factorial

    No difference. You just need to find the powers contained for all the prime factors and group the accordingly.

    For example: Find the highest power of 200 that divides 200! completely.

    200 = 23 × 52

    We have already calculated the powers of 2 and 5 contained in 200!

    So number of 23 available = [197/3] = 65 and number of 52 available = [49/2] = 24.

    That means we can form exactly 24 pairs of 23 and 52 in 200! Or 24 is the highest power of 200 which divides 200! completely.

    How to find remainders of factorial numbers

    Wilson Theorem states: (p - 1)! + 1 = 0 mod p where p is a prime number.

    For example 30! + 1 = 0 mod 31 or in other words we can say 30! + 1 is divisible by 31.

    We can further work on it to get that

    (p - 1)! = -1 mod p

    (p - 1)! = (p - 1) mod p

    (p - 2)! = 1 mod p

    -2(p - 3)! = 1 mod p

    2(p - 3)! = -1 mod p

    2(p - 3)! + 1 = 0 mod p and many more. :)


Log in to reply
 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.