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

**DISTINCT**factors = `("number of factors " - 1)/2`

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.

## Remainders - LCM & HCF application

The basic concept of LCM & HCF is clubbed with the concept of remainders is required for solving certain types of questions.

## LCM + Remainders

### Type I : Common remainder

Any number which when divided by `x`, `y` or `z`, leaving the same remainder `r` in each of the divisions, is of the form `k( "LCM of x, y and z") + r`, where `k` is any whole number. When `k = 0`, we will get the least such value but this is the remainder itself and is less than the divisor.

if `k = 0; 35k + 4 = 4 -> "not prime"`

if `k = 1; 35 k + 4 = 39 -> "not prime"`

if `k = 2; 35 k + 4 = 74 -> "not prime"`

if `k = 3; 35k + 4 = 109 -> "prime"`

Therefore the required least prime = 109.

Largest three digit multiple of 99 is 990.`:. N = 990 + r`

Largest possible value for `r = 8`, because the least divisor is 9 and the remainder should be lesser than divisor.

`:. N = 990 + 8 = 998`

### Type II: Common Negative Remainders

When a number `N` divided by `x`, `y`, or `z`, it leaves the same negative remainder '-r', then the general form of such number `N = k ("LCM of x, y and z") - r`, where `k` is any natural number.

Divisors (d) | Positive remainders (r) | Negative remainders (r - d) |
---|---|---|

8 | 6 | `6 - 8 = -2` |

10 | 8 | `8 - 19 = -2` |

Required number `N = k("LCM of 25 and 30") - 5 = 150k - 5`

When `k = 6 -> N = 900 - 5 = 895`

`:.`The largest such three digit number = 895.

### Type III: Distinct remainders for different divisors.

Therefore `N = 7a + 2`, where 'a' is the quotient and 'a' is a natural number.

`"Rem" (N/11) = 7`

Therefore `N = 11b + 7`, where 'b' is the quotient and 'b' is a natural number.

`7a + 2 = 11b + 7`

`7a = 11b + 7 - 2`

`7a = 11b + 5`

LHS of the equation is a multiple of 7 for any natural number value for 'a'. so the RHS also should be a multiple of 7 for some suitable natural number values for 'b'.

When `b = 4 -> "RHS" = 11b + 5 = 11(4) + 5 = 49` , it is multiple of 7.

Hence 4 is the first such suitable value for 'b'.

So `N = 11b + 7 = 11(4) + 7 = 51`

The required least number = 51

## HCF + Remainders

### Type I: Distinct remainder for different dividends

The largest divisor 'd' with which the numbers `X`, `Y` and `Z` are divided leaves remainders `a`, `b` and `c` respectively is the HCF of `(X -a)`, `(Y - b)` and `(Z - c)`.

`= "HCF" [115, 161, 184]` = 23.

### Type II: Common remainder

The largest divisor which is giving the same remainder when it divides X, Y and Z is; `"HCF"[(X - Y),(Y - Z),(Z - X)]` OR `"HCF"[(X - Y),(Y - Z)]`

## Factorial (!)

Factorial is a well defined operator, which is defined as the *"the product of a certain number of natural numbers starting from 1"* The operator factorial is denoted by the symbol '!' (Exclamatory sign).

Examples: `4! = 1 xx 2 xx 3 xx 4 = 24`

`5! = 1 xx 2 xx 3 xx 4 xx 5 = 120`

`n! = 1 xx 2 xx 3 xx "...." xx (n - 2) xx (n - 1) xx n`

`1! = 1`

`n! = n xx (n - 1)! = n xx (n - 1) xx (n - 2)!` , and so on.

### Concept I: Largest power of a prime in N!

Let's look at these kind of problems with help of couple of examples.

`:.`the largest power of 2 in 5! is 3.

If the question ask about a largest factorial value, then the above method is not easy to apply. So we have to think about an alternate method.

**Long division method:**

Largest power of 3 in 100! = sum of all quotient in all steps

`-> 33 + 11 + 3 + 1 = 48`.

The largest possible value for `n = 15 + 3 = 18`

### Concept II: Largest power of a composite number in N!

For finding the largest power of 6 in 15!, it is enough to find the largest power of 3 in 15!

Largest power of `n = 5 + 1 = 6`

So the largest power of 6 in 15! is 6

### Concept 3: Number of zeros at the end of N!

In the product of first 'n' natural numbers, a 'zero' will get generated as per the combination of 2 and 5. Therefore finding the number of zeros at the end of N!, find the number of 5's in N!.

i.e. There are 5 + 1 = 6 zeros at the end of 25!

## How to find unit digit of an exponential expression

The unit digit of the powers of natural numbers follows some interesting patterns. An understanding of the occurrence of unit digit will help you to score some points in your exams. This awareness is not only for using the typical questions from unit digit but also can use as the verification tool for basic arithmetic operations.

Unit digit of the different exponents of all numerals follows a certain cyclic order. It is possible to tabulate the cyclic pattern of unit digits in the following manner.

`"Base"^n` | Unit Digit | General Form of Exponent |
---|---|---|

`0^n` | 0 | Any natural number |

`1^n` | 1 | Any natural number |

`2^1` | 2 | 4k + 1 |

`2^2` | 4 | 4k + 2 |

`2^3` | 8 | 4k + 3 |

`2^4` | 6 | 4k + 0 |

`3^1` | 3 | 4k + 1 |

`3^2` | 9 | 4k + 2 |

`3^3` | 7 | 4k + 3 |

`3^4` | 1 | 4k + 0 |

`4^1` | 4 | Odd |

`4^2` | 6 | Even |

`5^n` | 5 | Any natural number |

`6^n` | 6 | Any natural number |

`7^1` | 7 | 4k + 1 |

`7^2` | 9 | 4k + 2 |

`7^3` | 3 | 4k + 3 |

`7^4` | 1 | 4k + 0 |

`8^1` | 8 | 4k + 1 |

`8^2` | 4 | 4k + 2 |

`8^3` | 2 | 4k + 3 |

`8^4` | 6 | 4k + 0 |

`9^1` | 9 | Odd |

`9^2` | 1 | Even |

Let's look at how to use this table with the help of few examples.

Therefore the unit digit of `1020^34` is 0.

`"Rem"[345/4] = 1`, i.e 345 is of the form `4k + 1`

From the pattern of 2 in the table, if the exponent in the form `4k + 1` then unit digit is 2.

Therefore the unit digit of `3689^3475` is 9.

## How to find last two digits of `a^b`

If 'a' and 'b' are two natural numbers, then it is possible to find out the last two digits of the expression `a^b`. We can classify the situations as per the unit digit of the base value 'a'.

### Last two digits of exponents of a number which ends in '0'

Example: `20^n`

If `n = 1 ->` last two digits are the last two digits of the base itself, i.e. 20

If `n > 1 ->` last two digits are always '00'.

### Last two digits of exponents of a number which ends in '1'

- Unit digit of `a^b` is always 1.
- Tens digit of `a^b = "unit digit of"[ "tens digit of 'a'" xx "unit digit of 'b'"]`

Tens digit = `2 xx 4 = 8`

Therefore the last two digits of `21^34` are 81.

Tens digit = `4 xx 3 = 12 -> 2`,(unit digit of 12)

Therefore last two digits of `1341^73 = 21`

### Last two digits of exponents of a number which ends in '5'

- If the exponent is 1, then the last two digits are the last two digits of the given number itself.
- If the exponent is greater than 1, then the last two digits are always '25'.

### Last two digits of exponents of a number which ends in 3, 7 or 9

- `3^4`, `7^4` and `9^2` are ending in 1.
- Convert the base in the form of ending with 1, through the conversion of the exponent.
- After changing the unit digit of the base to 1, then apply the method which we discussed for numbers ending in 1.

Let's look at an example to see how to find last two digits of an exponent of a number which ends in 7

`17^244 = (17^4)^61`

`= (17^2 xx 17^2)^61`

`= (289 xx 289)^61`

`= ("___21")^61`; Now base ends in 1, we can apply the procedure to find last two digits of exponents of a number which ends in 1

Unit digit = 1

Tens digit = `2 xx 1 = 2`

`:. "Last two digits of " 17^244 = 21`

For finding the last two digits of the exponents of a number which ends in 3, 7 or 9, the following patterns will help you to make a quick approach.

#### Pattern I: Last two digits of 4th power of the numbers which end in 3.

`03^4 -> 81 \leftarrow 53^4`

`13^4 -> 61 \leftarrow 63^4`

`23^4 -> 41 \leftarrow 73^4`

`33^4 -> 21 \leftarrow 83^4`

`43^4 -> 01 \leftarrow 93^4`

Let's look at an example to see how to apply these patterns in practise.

From the above pattern it is easy to catch the last two digits of `33^4`, and those are 21.

`-> "Last two digits of " 21^71 xx 33^3`

`-> "Last two digits of " 21 xx 37` (because the last two digits of `21^71` are 21 and that for `33^3 = 33 xx 33 xx 33 -> 37`)

`:. "Last two digits of "133^287 " are " 77`.

#### Pattern II: Last two digits of 4th power of the numbers which end in 7.

`07^4 -> 01 \leftarrow 57^4`

`17^4 -> 21 \leftarrow 67^4`

`27^4 -> 41 \leftarrow 77^4`

`37^4 -> 61 \leftarrow 87^4`

`47^4 -> 81 \leftarrow 97^4`

`"Last two digits of " (01)^11 xx 57` (From the above pattern we can see that last two digits of `57^4` is 01)

`= 57`

`-> "Last two digits of " 21^39 xx 89`

`-> "Last two digits of " 81 xx 89 = 09`

#### Pattern III: Last two digits of square of the bases which ends in 9.

`09^2 -> 81 \leftarrow 59^2`

`19^2 -> 61 \leftarrow 69^2`

`29^2 -> 41 \leftarrow 79^2`

`39^2 -> 21 \leftarrow 89^2`

`49^2 -> 01 \leftarrow 99^2`

`->" Last two digits of " (21)^60 xx 39` (From the above pattern we can see that last two digits of `39^2` are 21)

`->" Last two digits of " 01 xx 39`

Therefore the last two digits of `39^121` are 39.

### Last two digits of exponents of a number which ends in 2, 4, 6 and 8

- Convert the given bases in the form of `2^10`
- `(2^10)^"even"` will end in 76.
- `(2^10)^"odd"` will end in 24.

Therefore the last two digits are 24.

`= (2^10)^7 xx 2^5`

`-> " Last two digits of " 24 xx 32 = 68`

`= (2^2)^24 xx 27^24`

`= 2^48 xx 27^24`

`=(2^10)^4 xx 2^8 xx 27^24`

Last two digits of `(2^10)^4 = 76`

Last two digits of `2^8 = 56`

Last two digits of `27^24 = (27^4)^6 -> " Last two digits of " (41)^6 -> 41`

Therefore the last two digits of `108^24` = Last two digits of `[76 xx 56 xx 41] = 96`

### Tips for quick calculation

- `76^n` is always end in 76 for any natural number values for n.
- `24^"even"` will end in 76.
- `24^"odd"` will end in 24.
- `76 xx 2^n` will end in the last two digits of `2^n`, where n >= 2.

**Example :**

`76 xx 32` ends in 32.

`76 xx 1024` ends in 24.

`76 xx 16` ends in 16. - `76 xx " any multiple of 4"` will end in the last two digits of the multiple of 4.

**Example:**

`76 xx 04` ends in 04.

`76 xx 88` ends in 88. - `76 xx " any even number but not a multiple of 4"` will end in `50 + "last two digits of the number"`

**Example:**

`76 xx 2` ends in `50 + 2 = 52`

`76 xx 6` ends in `50 + 6 = 56`

`76 xx 22` ends in `50 + 22 = 72`