This is a continuation of article on number system. Here we will discuss few of the important concepts factors, multiples, applications of HCF and LCM in finding remainder, factorial etc. This will help you in solving aptitude problems related power, reminder etc very quickly. Also, we'll look at concepts and shortcuts in finding the unit digit (last digit) and last two digit of large exponent expression.
Objectives
- Factors and Multiples
- Prime factorization method
- Number of factors of a given number
- Number of ways to express a number as the product of two factors
- Sum of all the factors of a given number
- Number of ways to express a number as the product of two co-prime factors
- Euler's `\phi` function
- Sum of all co-prime factors of given number
- LCM and HCF application on Remainders
- Factorial and its properties
- Largest power of a factor in n!
- Unit digit of an exponential expression
- Last two digits of an exponential expression
Factors and Multiples
Factors and multiples are fully restricted in the set of natural numbers. That means any number other than a natural number can't be the factor or multiple of any number.
Factors
If y is a factor of x, where x and y are natural numbers, then; `x/y = k`, k should be natural number.
Multiple
If x is a multiple of y, where x and y are natural numbers, then; `x/y = k`, k should be natural number.
In general, if `a` and `b` are any two natural numbers and `a/b` is a natural number, then
`-> a` is a multiple of `b`
`-> b` is a factor of `a`
Divisibility
If `x` is divisible by `y`, where `x` and `y` are any two integers (either positive or negative) and `y != 0`, then; `x/y = k`, where `k` is any integer.
16 is divisible by both 4 and -4.
Note: 0 (zero) is divisible by all integers except '0'.
Important concepts on factors
Concept I: Factors of natural number
Let us consider a number 12. Factors of 12 are 1, 2, 3, 4, 6 and 12. There are 6 factors for 12.
Similarly factors of 30 are 1, 2, 3, 5, 6, 10, 15 and 30. There are 8 factors for 30.
Key points
- All perfect squares have an odd number of factors
- Perfect square of any prime number has exactly 3 factors
- All non-perfect squares have even number of factors
- Perfect numbers: If the sum of all factors (except that number itself) of a number is equal to the number itself is called a perfect number
Eg: Factors of 6 except 6 `->` 1, 2, 3
Sum of above factors = 1 + 2 + 3 = 6
28 and 496 are the other perfect numbers in the first 1000 natural numbers.
Concept II: Prime factorization
All natural numbers except 1 can be expressed in its prime factorization form. Simply a natural number greater than 1 is the suitable combination of its prime factors.
Eg: `10 = 2^1 xx 5^1`
`16 = 2^4`
`30 = 2^1 xx 3^1 xx 5^1`
`100 = 2^2 xx 5^2`
Concept III: Number of factors of a natural number
If 'N' a natural number and `N = a^p xx b^q xx c^r xx`..., where a, b, c... are the distinct prime factors of N and p, q, r... are natural numbers which are representing the occurrence of corresponding prime factors in N.
`30 = 2^1 xx 3^1 xx 5^1 -> "number of factors" = (1 +1) (1 + 1) (1 + 1) = 2 xx 2 xx 2 = 8`
`100 = 2^2 xx 5^2 -> "number of factors" = (2 + 1) (2 + 1) = 3 xx 3 = 9`
`1024 = 2^10 -> "number of factors" = (10 + 1) = 11`
Concept IV: Number of ways to express a number as the product of two factors
Let's take a look at few examples.
Let us consider the number 30, it can be expressed as the product of two factors in the following ways: `1 xx 30`, `2 xx 15`, `3 xx 10`, `5 xx 6`
i.e. 30 can be expressed as the product of two factors in 4 ways. This is half the total number of factors of 30. i.e. the total number of factors of 30 is 8.
Consider another number 36, it's factors are: 1, 2, 3, 4, 6, 9, 12, 18, 36 (Total 9 factors)
36 can be expressed as the product of two factors in the following ways: `1 xx 36`, `2 xx 18`, `3 xx 12`, `4 xx 9`, `6 xx 6`. Hence the number of ways to express 36 as the product of two factors is 5. And the number of ways to express 36 as the product of two DISTINCT factors in 4 ways (excluding `6 xx 6`)
Concept V: Sum of all factors
If 'N' a natural number and `N = a^p xx b^q xx c^r xx`..., where a, b, c... are the distinct prime factors of N and p, q, r... are natural numbers which are representing the occurrence of corresponding prime factors in N.
OR
`[(a^(p+1) - 1)/(a-1)][(b^(q+1) - 1)/(b-1)][(c^(r+1) - 1)/(c-1)]"..."`
Sum of all factors of 60 `= (2^0 + 2^1 + 2^2) (3^0 + 3^1) ( 5^0+ + 5^1)`
`= (1 + 2 + 4) ( 1 + 3) (1 + 5) = 168`
Concept VI: Number of ways to express a number as the product of two relatively prime factors
If 'N' a natural number and `N = a^p xx b^q xx c^r xx`..., where a, b, c... are the distinct prime factors of N and p, q, r.... are natural numbers which are representing the occurrence of corresponding prime factors in N.
`:.`Therefore the number of ways to express N as the product of two co-primes `= 2^(3-1) = 2^2 = 4`
And the required expressions are `1 xx 30`, `2 xx 15`, `3 xx 10`, `5 xx 6`. Note: 1 is relatively prime to all natural numbers except 1.
Euler's `\phi` function or relatively prime to N, which are less than N.
If 'N' a natural number and `N = a^p xx b^q xx c^r xx`..., where a, b, c... are the distinct prime factors of N and p, q, r.... are natural numbers which are representing the occurrence of corresponding prime factors in N.
`\phi(24) = 24[1 - 1/2][1 - 1/3] = 24 xx 1/2 xx 2/3 = 8`
Hence there are 8 possible values for p(1, 5, 7, 11, 13, 17, 19, 23).
Concept VIII: Sum of all relatively prime numbers to N, which are less than N.
This is the extension of the above result. Here we are finding the sum of all co-primes to N which are less than N.
