THE OREMS OF DIVISIBILITY FOR LCMS

Theorems of Divisibility

(a) If a is divisible by b then ac is also divisible by b.

(b) If a is divisible by b and b is divisible by c then a is divisible by c.

(c) If a and b are natural numbers such that a is divisible by b and b is divisible by a then a = b.

(d) 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).

(e) If a is divisible by b and c is divisible by d then ac is divisible by bd.

(f) The highest power of a prime number p, which divides n! exactly is given by

[n/ p] + [n/ p2] + [n/ p3] +…

where [x] denotes the greatest integer less than or equal to x.

As we have already seen earlier –

Any composite number can be written down as a product of its prime factors. (Also called standard form)

Thus, for example the number 1240 can be written as 23 ¥ 311 ¥ 51.

The standard form of any number has a huge amount of information stored in it. The best way to understand the information stored in the standard form of a number is to look at concrete examples. As a reader I want you to understand each of the processes defined below and use them to solve similar questions given in the exercise that follows and beyond:

1. Using the standard form of a number to find the sum and the number of factors of the number:

(a) Sum of factors of a number:

Suppose, we have to find the sum of factors and the number of factors of 240.

240 = 24 ¥ 31 ¥ 51

The sum of factors will be given by:

(20 + 21 + 22 + 23 + 24) (30 + 31) (50 + 51)

= 31 ¥ 4 ¥ 6 = 744

Note: This is a standard process, wherein you create the same number of brackets as the number of distinct prime factors the number contains and then each bracket is filled with the sum of all the powers of the respective prime number starting from 0 to the highest power of that prime number contained in the standard form.

Thus, for 240, we create 3 brackets— one each for 2, 3 and 5. Further in the bracket corresponding to 2 we write (20 + 21 + 22 + 23 + 24).

Hence, for example for the number 40 = 23 ¥ 51, the sum of factors will be given by: (20 + 21 + 22 + 23) (50 + 51) {2 brackets since 40 has 2 distinct prime factors 2 and 5}

(b) Number of factors of the number:

Let us explore the sum of factors of 40 in a different context.

(20 + 21 + 22 + 23) (50 + 51)

= 20 ¥ 50 + 20 ¥ 51 + 21 ¥ 50 + 21 ¥ 51 + 22 ¥ 50 + 22

¥ 51 + 23 ¥ 50 + 23 ¥ 51

= 1 + 5 + 2 + 10 + 4 + 20 + 8 + 40 = 90

A clear look at the numbers above will make you realize that it is nothing but the addition of the factors of 40

Hence, we realise that the number of terms in the expansion of (20 + 21 + 22 + 23) (50 + 51) will give us the number of factors of 40. Hence, 40 has 4 ¥ 2 = 8 factors.

Note: The moment you realise that 40 = 23 ¥ 51 the answer for the number of factors can be got by (3 + 1) (1 + 1) = 8

2. Sum and Number of even and odd factors of a number.

Suppose, you are trying to find out the number of factors of a number represented in the standard form by: 23 ¥ 34 ¥ 52 ¥ 7 3

As you are already aware the answer to the question is (3 + 1) (4 + 1) (2 + 1) ¥ (3 + 1) and is based on the logic that the number of terms will be the same as the number of terms in the expansion: (20 + 21 + 22 + 23) (30 + 31 + 32 + 33 + 34)( 50 + 51 + 52) (70 + 71 + 72 + 73).

Now, suppose you have to find out the sum of the even factors of this number. The only change you need to do in this respect will be evident below. The answer will be given by:

(21 + 22 + 23)( 30 + 31 + 32 + 33 + 34) (50 + 51 + 52) (70 + 71 + 72 + 73)

Note: That we have eliminated 20 from the original answer. By eliminating 20 from the expression for the sum of all factors you are ensuring that you have only even numbers in the expansion of the expression.

Consequently, the number of even factors will be given by: (3) (4 + 1) (2 + 1) (3 + 1)

i.e. Since 20 is eliminated, we do not add 1 in the bracket corresponding to 2.

Let us now try to expand our thinking to try to think about the number of odd factors for a number.

In this case, we just have to do the opposite of what we did for even numbers. The following step will make it clear:

Odd factors of the number whose standard form is : 23 ¥ 34 ¥ 52 ¥ 73

Sum of odd factors = (20) (30 + 31 + 32 + 33 + 34) (50 + 51 + 52) (70 + 71 + 72 + 73)

i.e.: Ignore all powers of 2. The result of the expansion of the above expression will be the complete set of odd factors of the number.

Consequently, the number of odd factors for the number will be given by the number of terms in the expansion of the above expression.

Thus, the number of odd factors for the number 23 ¥ 34 ¥ 52 ¥ 73 = 1 ¥ (4 + 1) (2 + 1) (3 + 1).

3. Sum and number of factors satisfying other conditions for any composite number

These are best explained through examples:

(i) Find the sum and the number of factors of 1200 such that the factors are divisible by 15.

Solution : 1200 = 24 ¥ 52 ¥ 31.

For a factor to be divisible by 15 it should compulsorily have 31 and 51 in it. Thus, sum of factors divisible by 15 = (20 + 21 + 22 + 23 + 24) ¥ (51 + 52) (31) and consequently the number of factors will be given by 5 ¥ 2 ¥ 1 = 10.

(What we have done is ensure that in every individual term of the expansion, there is a minimum of 31 ¥ 51. This is done by removing powers of 3 and 5 which are below 1.)

Once you have covered the basic concept of Divisibility for LCMs, you will be required to learn the application of the same to solve the twists of the MAT 2015 questions. You need to practice lots of mocks to gain speed in solving such questions.