The document Introduction & Concept: Divisibility Notes | EduRev is a part of the CAT Course Quantitative Aptitude (Quant).

All you need of CAT at this link: CAT

**Introduction**

- A number 'x' is said to be divisible by another number ‘y’ if it is
**completely divisible**by y (i.e., it should leave no remainder). - In general, it can be said that any integer I, when divided by a natural number N, there exist a unique pair of numbers Q and R which are called the
**quotient and Remainder**respectively. Thus,**I = QN + R**. Where Q is an integer and N is a natural number or zero and 0 £ R < N (i.e. remainder has to be a whole number less than N).

- If the remainder is zero, we say that the number I is divisible by N.
- When R π 0, we say that the number I is divisible by N with a remainder.
- Thus, 25/8 can be written as: 25 = 3 * 8 + 1 (3 is the quotient and 1 is the remainder).
- While –25/7 will be written as –25 = 7 * (–4) + 3 (–4 is the quotient and 3 is the remainder).

Note:An integer b not equal to 0 is said to divide an integer a if there exists another integer c such that: a = bc

- It is important to explain at this point, a couple of concepts with respect to the situation when we divide a negative number by a natural number N.
- Suppose, we divide – 32 by 7. Contrary to what you might expect, the remainder, in this case, is + 3 (and not – 4). This is because the remainder is always non-negative. Thus, –32/7 gives quotient as – 5 and remainder as + 3.

**Theorems of Divisibility**

- If a is divisible by b, then ac is also divisible by b.
- If a is divisible by b and b is divisible by c then a is divisible by c.
- If a and b are natural numbers such that a is divisible by b and b is divisible by a then a = b.
- If n is divisible by d and m is divisible by d then (m + n) and (m – n) are both divisible by d. This has an important implication. Suppose 28 and 742 are both divisible by 7. Then (742 + 28) as well as (742 – 28) are divisible by 7. (and in fact so is + 28 – 742).
- If a is divisible by b and c is divisible by d then ac is divisible by bd.
- The highest power of a prime number p, which divides n! exactly is given by [n/p] + [n/p
^{2}] + [n/p^{3}] +... where [x] denotes the greatest integer less than or equal to x.

**Factors**

- The number of factors based questions has regularly appeared in various competitive exams, including CAT. Primarily, these questions are based on the prime factorization of a number.
__Generally, factors based questions are of following types:__► The number of factors.

► The sum of factors.

► Product of factors.

► Odd and Even Factors.

► Number of Factors which are perfect squares for certain kinds of questions.- We already have the direct formula and shortcut techniques which we apply to get the answer. However, if an aspirant wants to master this topic, must also understand the conceptual approach to solve these types of questions.

This article will focus more on the concepts and approach to tackle question based on factors.

**Prime Factorisation**

We all know that every composite number can be written as a product of some prime numbers.**Example**: We can write 90 as 2 × 3^{2} × 5. This process is called prime factorisation, and it is the first step to solve any questions related to factors.

**➢ Number of Factors of a Number**

- Factors are those numbers that divide the given number completely. For example, below is the list of all factors of number 72.
**Factors**: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 48 and 72. - Observe that the number 1 is always a factor of every number, and the number itself will be the factor of the number. Here we can see that there are 12 factors of 72.
- Now let us understand the formula for finding the number of factors of any composite number. We will take the above example of 72.

► 72 = 2^{3}× 3^{2} - Clearly, the number 72 is divisible by each of 2
^{0},2^{1}, 2^{2}, 2^{3}...^{ }but not by any higher power of 2 like 2^{4}, 2^{5}, …__Similarly, the number 72 is divisible by each of:__► 3^{0}, 3^{1}, 3^{2},.....

► but not by 3^{3},3^{4},…. - We should also observe that the number can be divisible by any ‘combination’ of one of 2
^{0},2^{1}, 2^{2}, 2^{3}and one of 3^{0}, 3^{1}, 3^{2}.....by numbers of type 2^{1}× 3^{2}or 2^{2 }× 3^{1 }and so on.

Now that you have understood the basics of how to write a number into its prime factors let’s try to understand how questions are asked in CAT exam

**➢ How to Find the Sum and Number of Factors of a Number**

- You might have encountered with such questions in earlier CAT papers or any Test series. Well, questions of such types require
**prior knowledge of solving it**. Otherwise, you will waste time trying to solve such questions and end up with no results. - So is there any formula for such questions?. In fact, there is a complete algorithm to solve such questions. If you follow the algorithm and practice a few questions, you will solve it within minutes.
- Let's take a number 720. So the question is to
**“Find the sum and number of Factors of 720 .”****Approach**:

► Write the number in Standard Form.

So , 720 = 2^{4}x 3^{2}x 5^{1}

► Create a number of brackets as the number of prime factors.

► Fill each bracket with the sum of all the powers of the respective prime number starting from 0 to the highest power of that number.

► Sum of the factors = (2^{0}+ 2^{1}+ 2^{2}+ 2^{3}+ 2^{4}) x (3^{0}+ 3^{1}+ 3^{2}) x (5^{0}+ 5^{1})

= (1 + 2 + 4+ 8 +16) x (1 + 3 + 9) x (1+ 5)

= 31 x 13 x 6 = 2418

**➢ How to Find Number of Factors of a Number?**

- If you will check the sum of factors in step 3, and expand the bracket, you will find that all are actually factors of the number.
__Lets take a small number for this say 80:__► 80 = 2^{4}x 5^{1}

► Sum of the factors = (2^{0}+ 2^{1}+ 2^{2}+ 2^{3}+ 2^{4}) x (5^{0}+ 5^{1}) = 31 x 6 = 186

= 2^{0}x 5^{0}+ 2^{1}x 5^{0}+ 2^{2}x 5^{0}+ 2^{3}x 5^{0}+ 2^{4}x 5^{0}+ 2^{0}x 5^{1}+ 2^{1}x 5^{1}+ 2^{2}x 5^{1}+ 2^{3}x 5^{1 }+ 2^{4}x 5^{1}

= 1 + 2 + 4 + 8 + 16 + 5 + 10 + 20 + 40 + 80 = 186__So to calculate the number of factors of 80:__► Add 1 to the powers of prime factors and multiply it

► No. of Factors of 80 = (4 + 1) x (1 + 1) = 10.

Let's get back to the original question ” Find the number of Factors of 720 ” So, 720 = 2^{4}x 3^{2}x 5^{1}

► Number of Factors of 720 = (4 + 1) x (2 + 1) x (1 + 1) = 5 x 3 x 2 = 30

Question 1:Find the number of divisors of 1080 excluding the divisors, which are perfect squares.

Question 2:Find the sum the sums of divisors of 144 and 160.

**Divisibility Rules**

- As the name suggests, divisibility rules or tests the are procedures used to check whether a number is divisible by another number without necessarily performing the actual division.
- A number is divisible by another number if the results or quotient is a whole number and the remainder is zero.
- Since not all number is completely divisible by other numbers, therefore, the divisibility rules are actually the shortcuts of determining the actual divisor of a number just by examining the digits that make the number.

__Let us now look into these divisibility rules for different numbers:__

**➤ Divisibility Test for 1**

- The divisibility test for 1 does not have any condition for numbers. All numbers are divisible by 1 irrespective of how large the numbers are.
- When any number is divided by 1, the result is the number itself.
**Example**: 5/1= 5 and 100000/1 = 100000.

**➤ Divisibility Test for 2**

- A number is divisible by 2 if the last digit of the number is 2, 4, 6, 8 or 0.
**Example**: 102/2 = 51, 54/2 = 27, 66/2 = 33, 28/2 = 14 and 20/2 = 10.

**➤ Divisibility Test for 3**

- The divisibility test for 3 states that a number is completely divisible by 3 if the digits of the number are divisible by 3 or is a multiple of 3.
**Example**:__Consider two numbers 308 and 207:__

► To check if 308 is divisible by 3 or not, find the sum of the digits. 3 + 0 + 8 = 11.

► Since the sum is 11 which not divisible by 3, then 308 is also not divisible by 3.

► Check 207 by summing its digits: 2 + 0 + 7 = 9, since 9 is a multiple of 3, then 207 is also divisible by 3.

**➤**** Divisibility Test for 4**

- The divisibility test for 4 states that a number is divisible by 4 if the last two digits of the number are divisible by 4.
**Example**: Consider two numbers, 2508 and 2506.

► The last digits of the number 2508 are 08. Since 08 is divisible by 4, then the number 2508 is also divisible by 4.

► 2506 is not divisible by 4 because the last two digits; 06 are not divisible by 4.

**➤ Divisibility Test for 5 **

- All numbers with the last digit as 0 or 5 are divisible by 5.
**Example**: 100/5 = 20, 205/5 = 41.

**➤ Divisibility Test for 6 **

- A number is divisible by 6 if its last digit is an even number or zero and the sum of the digits is a multiple of 3.
**Example**: 270 is divisible by 2 because the last digit is 0.

► The sum of the digits is: 2 + 7 + 0 = 9 which is also divisible by 3.

► Therefore, 270 is divisible by 6.

**➤ Divisibility Rules for 7**

- The divisibility test of 7 is explained in the following algorithm Consider a number 1073.
- To check whether the number is divisible by 7 or not? Eliminate number 3 and multiply it by 2, which becomes 6.
- Subtract 6 from the remaining number 107, therefore 107 – 6 = 101. Repeat again the process we have 1 x 2 = 2, and the remaining number is 10 – 2 = 8.

Since 8 is not divisible by 7, therefore the number 1073 is also not divisible by 7.

**➤ Divisibility Test for 8**

- The divisibility test for 8 states that a number is divisible by 8 if its last three digits are divisible by 8.

**➤ Divisibility Test for 9**

- The divisibility test for 9 is the same as the divisibility test for 3. If the sum of the digits of a number is divisible by 9, then the number is also divisible by 9.
**Example:**In a number like 78532, the sum of its digits is: 7+8+5+3+2 = 25. - Since 25 is not divisible by 9, the 78532 is also not divisible by 9. Considering another case of number: 686997, the sum of digits is: 6 + 8 + 6 + 9 + 9 + 7 = 45. Since the sum is divisible by 9, then the number 686997 is divisible by 9.

**➤ Divisibility Test for 10**

- The divisibility rule for 10 states that any number whose last digit is zero, then the number I divisible by 10.
**Example:**The numbers: 30, 50, 8000, 20 33000 are divisible by 10.

**➤ Divisibility Rules for 11**

- This rule states that a number is divisible by 11 if the difference of the sum of alternative digits is divisible by 11.
**Example**:__To check whether number 2143 is divisible by 11 or not, the procedure is:__

► The sum of alternative digits of each group is: 2 + 4 = 6 and 1+ 3 = 4

► Therefore, 6-4 = 2, and so the number is not divisible by 11.

► Therefore 2143 is not divisible by 11.

**➤ Divisibility Rules for 13**

- To check whether a number is divisible by 13, repeated addition of the last digit is done 4 times to the remaining number until a two-digit number is arrived at.
- If the two-digit number is divisible by 13, then the whole number is also divisible by 13.
**Example**: 2795 → 279 + (5 x 4) → 279 + (20) → 299 → 29 + (9 x 4) → 29 + 36 →65.

► In this case, the two-digit number is found to be 65, which is divisible by 13. Therefore, the number 2795 is also divisible by 13.

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

220 videos|146 docs|134 tests