Friday, 1 August 2014

04. Aptitude Questions - Numbers - Theory Prime Factorization Related Concept

Numbers - Prime numbers and Applications

Prime Factor:
A prime number which exactly divides a number is the prime factor of that number.
Factors of 42 : 1,2,3,6,7,14,21,42
Prime factor of 42 : 2,3,7

Prime Factorization:
Fundamental Theorem of Arithmetic : It states that every natural number greater than 1 can be written as a unique product of prime numbers. This theorem is also called the unique factorization theorem or the unique-prime-factorization theorem.
How to write a  number as product of prime factors :
If the given number is prime, we need not the number as product of prime factors. Because it has no any other prime number as its factor.
 If the number is not a prime number,
      A.    Find a smallest prime number that exactly divides the given number.
      B. Divide the given number by the prime to obtain a quotient.
     C. Divide the quotient with the prime number and if the quotient is  not divisible by the prime  number taken, take next prime number which exactly divides it
     D. Repeat the process with the quotient until the quotient is itself a prime number 
     E.The prime factorization is given by the product of the primes used in the division process and the final prime quotient.
 Example :    180 = 2 x 2 x 3 x 3 x 5

Number of factors of a given number:  
How to find the number of factors of a number
Write the given number as product of prime factors.
Consider the number N=ap × bq × cr ×… where a, b, c are prime numbers and p, q, r are positive integers.
Then number of factors of ‘N’ is
          N= (p+1)(q+1)(r+1)…..
Factors of 18 : 1,2,3,6,9,18
Example :Find the number of factors of 18?
Solution : 18=21×32
Number of factors= (1+1) (2+1)
                       = (2×3) =6

Sum of the factors of a given number:  
Finding the sum of the factors of a number:
Write the given number as product of prime factors
Consider the number of N= ap × bq × cr ×… where a, b, c are prime numbers and p, q, r are positive integers.
Then sum of the factors= $ (\frac{a^{p+1}\text{–}1}{a-1})\times )(\frac{b^{q+1}\text{–}1}{b-1})\times(\frac{c^{r+1}\text{–}1}{c-1}) )$
Example : Find the sum of the factors of 120
Write 120 as product of prime factors =>  120=23 × 31  x 51
Sum of factors = $ (\frac{2^{3+1}\text{–}1}{2-1})\times )(\frac{3^{1+1}\text{–}1}{3-1})\times(\frac{5^{1+1}\text{–}1}{5-1} )$
               =  $ (\frac{2^{4}\text{–}1}{1})\times )(\frac{3^{2}\text{–}1}{2})\times(\frac{5^{2}\text{–}1}{4}) )$

                   =   ($\frac{15}{1}$ ) ×($ \frac{8}{2} $ )  x ($ \frac{24}{4}$ ) =15 x 4 x 6 = 360

Number of ways to express a number as product of 2 factors:  
To find the number of ways a number can be expressed as product of 2 factors:
Express given number into product of prime factors.
Consider N= ap × bq × cr ×… where a, b, c are primes and p, q, r are positive integers.
Number of factors = (p+1) (q+1) (r+1)….

Product of two factors = $\frac{Number\:of\:factors}{2}$

In how many ways you can express 24 as a product of two of its factors?
24 = 23 x 31
Number of factors of 24 = (3 + 1) (1 + 1)= 8
So, number of ways to express 24 as product of two factors = $\frac{8}{2}$ =4

Number of ways to express a number as a product of two co-primes :
First write down the give number as product prime factors.
Say N= ap × bq × cr ×… where a, b, c are primes and p, q, r are positive integers.
Then number of ways N can be written as product of two relatively primes = 2k-1 where k is the number of prime factors.
Example: In how many ways 180 can be written as product of two of its co-prime factors ?
Solution : Write 180 as product of prime factors
180 = 22 x 32 x 51 .
The total number of unique prime factors are 3.
Hence required number of ways = 23-1 = 4.

Number of co-primes that are less than given number:
To find the number of relative prime numbers that are less than the given number, express the given number as product of prime factors .
N= ap × bq × cr ×… where a, b, c are primes and p, q, r are positive integers
Then the number of co-primes less than N 
    = n (1- $\frac{1}{a}$ ) (1- $\frac{1}{b}$)(1-$\frac{1}{c})$

Example : Find the number of co-primes to 180 that are less than 180?
Solution : Expressing 180 as product of prime factors => 180 = 22 x 32 x 51
So number of coprimes that are less than 180 and co prime to 180
  = 180 x (1 – $\frac{1}{2}$) (1- $\frac{1}{3}$) (1 -$\frac{1}{5}$) =48.

Product of Factors of a number :
How to find the product of all the factors of a number :
To find the product of all divisors of the number N, write N as product of prime factors.
N= ap × bq × cr ×… where a, b, c are primes and p, q, r are positive integers
Find the number of factors of N  n(f) = (p+1)(q+1)(r+1)
Then, product of all the factors = N$\frac{n(f)}{2}$
Example: Find the product of all the factors of 120?
Solution : Write the 120 into product of prime factors
120 = 23 x 3 x 5
Number of factors of 120 n(f)= (3+1)(1+1)(1+1) = 4 x 2 x 2 =16

Product of factors of 120 = 120$\frac{16}{2}$ = 1208

Finding the Unit digit :
How to find the unit digit in a product or an expression
Unit digit rules:   In this there are four rules to find out the unit digit of a given number.
Rule (1):  The digits which are equal to the unit digit of power anything.
          The digits in this rule are 0, 1, 5, 6
01=0   11=1   51=5   61=6
02=0   12=1   52=20  62=36
03=0   13=1   53=125          63=216
------      ------        -------    --------
------      ------        -------    --------
Rule (2):  Odd power unit digits and even power unit digits.
          The digits in this rule are 4, 9.
è  Odd powers of 4, the unit digit is 4
41=4
43=64
……….
……….
è  Even powers of 4. The unit digit is 6
42=16
44=256
………..
è  Odd powers of 9. The unit digit is 9.
91=9
93=729
…………
è  Even powers of 9. The unit digit i.e 1
92=81
94=6561
………….
Rule (3):  This rule is in cyclic form of length ‘4’. The digits in this rule are 2, 3, 7, 8….
21=2   31=3   71=7            
22=4   32=9   72=49
23=8   33=27  73=343
24=16  34=81  74=2401
25=32  35=343          75=16807

          81=8
          82=64
          83=512
          84=4096
          85=32768

Find the last digit of 2343
Solution: Here power is 343.
So divide 343 by 4 we will get remainder 3 so unit digit is same as  that of 23 = 8.