# Number System Tutorial II: Divisibility, Remainder, HCF & LCM

This a continuation of article on number system. Here we will discuss few of the important concepts like divisibility, remainders HCF and LCM. This would help us in solving questions which require you to find the remainder when a large number is divided by another. Also, we'll discuss some shortcuts to find the remainders when a number is divided by specific numbers, quickly, based on the pattern.

## Objectives

• Rules of divisibility.
• LCM and HCF.
• Important properties of LCM and HCF.
• Remainders
• Properties of remainders.
• Concept of negative remainders.
• Pattern of remainders.
• Numerical application of Remainder theorem.

## Rules of divisibility

In this area we are going to familiarize some interesting methods for checking the divisibility of some important natural numbers.

### Divisibility by 2 and 5

For checking the divisibility of 2 and 5, it is possible to apply the same method. If the unit place digit of a given number is divisible by 2, then the given number should be divisible by 2. Possible unit place digits are 0, 2, 4, 6, 8. Eg: 172, 234, 510, 2756, 1768 are divisible by 2.

Similarly, if the unit place digit of a number is divisible by 5, then the number is divisible by 5. Possible unit place digits are 0 and 5. Eg: 125, 5690 are divisible by 5.

### Divisibility by 4 and 25

If the last two digits (tens and unit place digits) are divisible by 4, then the number is divisible by 4. Similarly if the last two digits (tens and unit place digits) are divisible by 25, then the number is divisible by 25.
Eg: 100, 172, 8756, 5420 are divisible by 4.
1250, 3700, 54525, 7875 are divisible by 25.

### Divisibility by 8 and 125

For checking the divisibility of 8 and 125, it is enough to check the last three digits of the given number.

If the last three digits of a given number is divisible by 8 then the given number is divisible by 8 and similarly if the last three digits of a given number is divisible by 125 then the given number is divisible by 125.
Eg: 1960, 37648, 123488 are divisible by 8.
4500, 11125, 9375 are divisible by 125.

### Divisibility by 16 and 625

For checking the divisibility of 16 and 625, it is enough to check the last four digits of the given number.

If the last four digits of a given number is divisible by 16, then the given number is divisible by 16 and similarly if the last four digits of a given number is divisible by 625, then the given number is divisible by 625.
Eg: 357296, 83888, 1603760 are divisible by 16.
493125, 2283750 are divisible by 625.

### Divisibility by 3 and 9

For checking the divisibility of 3 and 9, check the sum of all digits in the number

If the sum of all digits in the given number is a multiple of 3, then the given number is divisible by 3.
Eg: 123, 3258, 152724 are divisible by 3.

If the sum of all digits in the given number is a multiple of 9 then the number is divisible by 9.
Eg: 12345678, 342711 are divisible by 9.

### Divisibility by 6,12, 14, 15, 18, 21, 44 and 108: Using co-prime factor method

For checking the divisibility of 6, 12, 14, 15, 18, 21 etc, check the given number is divisible by the co-prime factors of these divisors.

6 can be expressed as the product of its two co-prime factors in the form 2 x 3. So, for checking the divisibility of 6, check whether the given number is divisible by both 2 and 3.
Eg: 1452 is divisible by both 2 and 3, hence 1452 is divisible by 6.

Use the below table to check divisibility by 6,12, 14, 15, 18, 21, 44 and 108.

DivisorCheck the divisibility of
12 3 and 4
14 2 and 7
15 3 and 5
18 2 and 9
21 3 and 7
44 4 and 11
108 4 and 27

### Divisibility by 7, 13, 17, 19 and 23: Using operator and operation based method

To check divisibility by 7, 13, 17, 19 and 23, we can use operator and operation based method, for which below table would be handy. The process of divisibility check using operation and operator method is explained below.

Check the divisibility ofOperatorOperations
7 2 Subtraction ( - )
13 4 Addition ( + )
17 5 Subtraction (-)
19 2 Addition ( + )
23 7 Addition ( + )

Divisibility check using operation and operator method is done in three steps.

• Step 1: Multiply the unit place of the given number by the mentioned operator
• Step 2: Apply the mentioned operation (subtraction or addition) on remaining part of the given number
• Step 3: Continue these steps till you can identify that the resultant difference is a multiple of the divisor or not. If this resultant difference is a multiple of divisor, then the given number is also a multiple of divisor, otherwise it is not.
Check if 22148 is a multiple of 7 or not
We can apply the above steps repeatedly as follows: We can see the operator is 2 and operation is subtraction.
2214 - 2 xx 8 = 2198
219 - 2 xx 8 = 203
20 - 2 xx 3 = 14, 14 it is a multiple of 7.
Hence 22148 is a multiple of 7.
Check 593814 is divisible by 13 or not
We can apply the above steps repeatedly as follows: We can see that operator is 4 and operation is addition
59381 + 4 xx 4 = 59397
5939 + 4 xx 7 = 5967
596 + 4 xx 7 = 624
62 + 4 xx 4 = 78, 78 is divisible by 13.
Hence 593814 is a multiple of 13.

### Divisibility by 11: Using alternate digital sum method

If the difference between the sum of odd place digits and the sum of even place digits in a number is divisible by 11 (either '0' or any multiple of 11), then the given number should be a multiple of 11.

Is 68123 divisible by 11?

In the above illustration, difference between both the sums = 10 - 10 = 0. So 68123 is divisible by 11.

## LCM and HCF

LCM (Least common multiple) of a given set of quantities is the least possible quantity which can be divisible by each of the given quantities in the set.

HCF (Highest common factor)/ GCD (Greatest common divisor) of a given set of quantities is the highest possible quantity which can exactly divide each of the given quantities in the set.

### Prime factorization method for finding LCM and HCF

Prime factorization is an easy method for LCM and HCF for a given group of numbers. Let's look at an example to see how to find LCM and HCF of given set of numbers using prime factorization method.
Illustrative example: Find the LCM and HCF of 96, 108 and 120?
In this method, first find the prime factors of the given numbers. Prime factorized expressions of the numbers are given below.
96 = 2^5 xx 3
108 = 2^2 xx 3^3
120 = 2^3 xx 3 xx 5
LCM = product of maximum exponent forms of each distinct bases which are occurred in any of the given numbers.
:. "LCM" = 2^5 xx 3^3 xx 5 = 4320
HCF = product of maximum exponent form of distinct bases which are occurred commonly in all the numbers.
:. "HCF" = 2^2 xx 3 = 12

Find the LCM and HCF of 48, 36 and 72.?
Prime factorized expressions of the numbers are given below.
48 = 2^4 xx 3
36 = 2^2 xx 3^2
72 = 2^3 xx 3^2
LCM = product of maximum exponent forms of each distinct bases which are occurred in any of the given numbers.
:. "LCM" = 2^4 xx 3^2 = 144
HCF = product of maximum exponent form of distinct bases which are occurred commonly in all the numbers.
:. "HCF" = 2^2 xx 3 = 12

### LCM and HCF of fractions

"LCM of fractions" = "LCM of numerators"/"HCF of denominators"
Find the LCM of 6/5, 9/10 and 27/20?
LCM of 6/5, 9/10 and 27/20 = "LCM(6, 9, 27)"/"HCF(5, 10, 20)" = 54/4
"HCF of fractions" = "HCF of numerators"/"LCM of denominators"
Find the HCF of 16/15, 20/25 and 36/35?
HCF of 16/15, 20/25 and 36/35 = "HCF(16, 20, 36)"/"LCM(15, 25, 35)" = 4/525

### Key points on LCM and HCF

• Product of any two numbers is equal to the product of their LCM and HCF.
Eg: Let us consider two numbers 12 and 8.
LCM (12, 8) = 24
HCF (12, 8) = 4
12 xx 8 = 24 xx 4
i.e. product of 12 and 8 = LCM(12, 8) xx HCF (12, 8)
• HCF of any two numbers is a factor of the difference between the numbers.
Eg: Let A = 36 and B = 63
B - A = 63 - 36 = 27
HCF (36, 63) = 9
9 is a factor of 27.
• Let A and B are two numbers and their LCM and HCF are 'L' and 'H' respectively. A and B can be expressed in terms of their HCF in the following manner.
A = Hp and B = Hq, where p and q are two relatively prime numbers.
LCM of A and B can be expressed in the form; LCM (A, B) = Hpq

Eg: Let A = 48 and B = 32.
LCM = 96 and HCF = 16
A = 16 x 3, B = 16 x 2 : Here 3 and 2 are relatively prime numbers.
:. "HCF" = "16 and LCM" = 16 xx 2 xx 3 = 96

## Remainders

There are a plethora of remainder related questions you can expect in your exam. So it is a mandatory requirement to create a clear awareness of remainders before going to attend the exam.

Based on above illustration, any number 'N' can be expressed as N = dq + r.

### Properties of remainders

• When the dividend is less than divisor, then the remainder is the dividend itself. Eg: when 5 divided by 7, the remainder is 5 itself, and then the quotient of this division is 0.
• Remainders are consistent under basic mathematical operations such as addition, subtraction, multiplication and powers.
Addition:When N_1 and N_2 (two distinct dividends) divided by a divisor d, leaves the respective remainders r_1 and r_2, then the remainder when N_1 + N_2 divided by d is r_1 + r_2.
Eg. "Rem"[11/9] = 2 and "Rem"[14/9] = 5
:. "Rem"[(11 + 14)/9] = 2 + 5 = 7
Subtraction:When N_1 and N_2 (two distinct dividends) divided by a divisor d, leaves the respective remainders r_1 and r_2, then the remainder when N_1 - N_2 divided by d is r_1 - r_2.
Eg. "Rem"[19/10] = 9 and "Rem"[15/10] = 5
:. "Rem"[(19 - 15)/10] = 9 - 5 = 4
Multiplication:When N_1 and N_2 (two distinct dividends) divided by a divisor d, leaves the respective remainders r_1 and r_2, then the remainder when N_1 xx N_2 divided by d is r_1 xx r_2.
Eg. "Rem"[14/10] = 4 and "Rem"[12/10] = 2
:. "Rem"[(14 xx 12)/10] = 4 xx 2 = 8
Powers or exponents:When a dividend 'N' divided by divisor 'd', leaves a remainder 'r', then N^n leaves a remainder r^n when it is divided by d.
Eg. "Rem"[10/8] = 2
:. "Rem"[10^2/8] = 2^2 = 4
• Concept of Negative remainders: As per Eucledian Lemma any number 'N' can be expressed in the following way; N = dq + r
In a similar arrangement, 7 can be expresses as; 7 = 3 × 2 + 1, where 3 is the divisor, 2 is the quotient and 1 is the remainder.
7 can be expressed in the following way too; 7 = 3 × 3 - 2, where 3 is the same divisor which we considered above, 3 is the new quotient and '-2' is the remainder as per the change in the quotient. Therefore the remainders 1 and -2 are representing the same division. Hence -2 is the corresponding negative remainder of the original remainder 1, when the divisor is 3.
"Negative remainder" = "original remainder" - "divisor"
"Therefore original remainder" = "divisor" + "negative remainder"
Let's look at one more example to understand concept of negative remainders.
"Rem"[18/8] = 2 and "Rem"[5/8] = 5
:. "Rem"[(18-5)/8] = 2 - 5 = -3
"Hence the original remainder" = "divisor" + "negative remainder"
= 8 + (-3) = 5
ie; "Rem"[(18-5)/8] = "Rem"[13/8] = 5
• Pattern of remainders:

Pattern of remainders is one of the most aesthetical and very important features of remainders. Let us consider the following pattern of remainders;

"Rem"[3^1/5] = 3
"Rem"[3^2/5] = 3 xx 3 -> 4
"Rem"[3^3/5] = 4 xx 3 -> 2
"Rem"[3^4/5] = 2 xx 3 -> 1
"Rem"[3^5/5] = 1 xx 3 -> 3 and so on...

The above pattern of remainders will repeat cyclically after the occurrence of 1 and the pattern of remainders is 3,4,2,1, 3,4,2,1... In the given example, there are 4 distinct remainders. If the exponent of 3 is any multiple of 4, then the remainder should be 1; Ie. if the exponent is in the form 4k + 1 -> "remainder is 3"
4k + 2 -> "remainder is 4"
4k + 3 -> "remainder is 2"
4k + 0 -> "remainder is 1", Where k is any whole number, k = 0, 1, 2, 3...

Find the remainder when 3^1729 divided by 5
As per the above explanation, there are 4 distinct remainders and those are occurring in the order 3, 4, 2, 1. 1729 = 4k + 1 (when 1729 divided by 4, it leaves the remainder 1). If the exponent is in the form 4k + 1, then the remainder is 3.
Find the remainder when 13^271 divided by 7
First of all develop the cyclic pattern of possible remainders.
"Rem"[13^1/7] = 6
"Rem"[13^2/7] = 6 xx 6 -> 1
"Rem"[13^3/7] = 1 xx 6 -> 6
"Rem"[13^4/7] = 6 xx 6 -> 1
Now we got a pattern of remainders in the cyclic order 6,1,6,1...
Note: In the pattern of remainders if in any step the remainder occurs as 1, then the pattern will start from there. Hence the operation of finding remainders can stop at that point.
In the above pattern, there are two distinct remainder, ie. when the exponent is odd, remainder is 6 and when the exponent is even, then the remainder is 1. :. "Rem"[13^271/7] = 6, because 271 is an odd exponent.

### Fermat's little theorem

Let N and p are two relatively prime numbers and p itself is a prime, then N^(p-1)/p leaves a remainder of 1.

Eg. "Rem"[100^36/37] = 1

Find the remainder when 100^41 divided by 41
As per Fermat's theorem, N^(p-1)/p leaves a remainder of 1, where N and p are two relatively prime numbers and p itself is a prime. In the given question, the divisor 41 is a prime number and 100 and 41 are relatively prime.:. "Rem"[100^40/41] = 1.
So, "Rem"[100^41/41] = "Rem"[(100^40 xx 100)/41] = "Rem"[100/41] = 18

### Wilson's theorem

For all prime p, [(p - 1)! + 1] is always divisible by p.
OR
When (p-1)! Is divided by p, the remainder is (p - 1).

Let's look at an example to understand Wilson's theorem.

Find the remainder when 6! Divided by 7.
As per Wilson's theorem; 7 is a prime -> "Rem"[((7-1)!)/7] = 7-1 = 6

### Remainder theorem and its numerical application

If p(x) is a polynomial in x, then p(a) is the remainder when p(x) divided by (x - a).

Understanding the numerical application of this theorem will help you to solve some complicated type of remainder related questions. Let's take a look at few examples to understand remainder theorem better.

Find the remainder when 2^402 divided by 7.
Consider 2^402 as a polynomial in 2. Also, 7 can be expressed in terms of 2 as: 7 = 2^3 - 1, which can be considered as a polynomial on 2^3
:. "Rem"[2^402/7] = "Rem"[(2^3)^134/ (2^3 - 1)] = 1^134 = 1
Find the remainder when 16^133 divided by 17.
17 = 16 + 1 ->  it is in the form of x + 1, where x = 16
16^133 is in the form of x^133, where x = 16
"Rem"[16^133/(16 + 1)] = (-1)^133 = -1
Here the remainde is negative, so original remainder (positive) is 17 - 1 = 16
Find the remainder when 27^101 divided by 82.
82 = 3^4 + 1
27^101 = (3^3)^101 = (3^4)^75 * 3^3 = (3^4)^75 * 27
"Rem"[27^101/82] = "Rem"[((3^4)^75 * 27)/(3^4 + 1)] = (-1)^75 * 27 = -27`
Here we got negative remainder as -27, so actual remainder is 82 - 27 = 55

#### Popular Videos

How to improve your Interview, Salary Negotiation, Communication & Presentation Skills.

Got a tip or Question?
Let us know