- INTRODUCTION
- FACTORS AND MULTIPLES
- HIGHEST COMMON FACTOR
- LEAST COMMON MULTIPLE
- HCF AND LCM
- DIVISIBILITY
TESTS
- DIVISIBILITY TEST OF 2
- DIVISIBILITY TEST OF 3
- DIVISIBILITY TEST OF 4
- DIVISIBILITY TEST OF 5
- DIVISIBILITY TEST OF 6
- DIVISIBILITY TEST OF 7
- DIVISIBILITY TEST OF 8
- DIVISIBILITY TEST OF 9
- DIVISIBILITY TEST OF 10
- DIVISIBILITY TEST OF 11
- DIVISIBILITY TEST OF 12
- DIVISIBILITY TEST OF 13
- DIVISIBILITY TEST OF 14
- DIVISIBILITY TEST OF 15
- DIVISIBILITY TEST OF 16
- DIVISIBILITY TEST OF 17
- DIVISIBILITY TEST OF 18
- DIVISIBILITY TEST OF 19
- DIVISIBILITY TEST OF 20
- DIVISIBILITY TEST FOR PRIME NUMBERS
- DIVISIBILITY TESTS FOR ANY NUMBER OF THE FORMAT ((10n ± 1) WHERE n IS A NATURAL NUMBER
- DIVISORS
- SUM OF DIVISORS
- NUMBER OF DIVISORS
- NUMBER OF WAYS OF EXPRESSING A GIVEN NUMBER AS A PRODUCT OF TWO FACTORS
- NUMBER OF WAYS OF WRITING A NUMBER AS A PRODUCT OF TWO CO-PRIMES
- NUMBER OF SETS OF FACTORS OF ANY NUMBER WHICH ARE CO-PRIME TO EACH OTHER
- NUMBER OF CO-PRIMES TO n LESS THAN n
- SUM OF CO-PRIMES LESS THAN n
- CONCEPT OF CYCLICITY
- REMAINDERS
- RULES RELATED TO an + bn OR an − bn
- CONCEPT OF SUCCESSIVE DIVISION
- NUMBER OF EXPONENTS
- OTHER EXAMPLES
Number Theory
Number theory is that branch of pure mathematics which deals with the properties of numbers. It is one of the most important concepts required for any MBA entrance examination.
If a natural number y completely divides a natural number x (without leaving any remainder or decimal portion), then y is called a factor of x. On the other hand, x is called a multiple of y.
Factors are also known as divisors.
So, if we consider the number 9, it can be divided completely by 1, 3 and 9. Thus, 1, 3 and 9 are factors of 9. Also, 9 is said to be a multiple of 1, 3 and 9.
IMPORANT:
- 9 can be completely divided by 4.5 but it does not mean that 4.5 is a factor of 9, because 4.5 is not a natural number.
Similarly, 2 can completely divide 9 without leaving any
remainder, but 2 is not a factor of 9, because the result of the division 9
2 i.e. 4.5 is not a natural number.
Every number has at least two factors, 1 and the number itself.
- If the given number is a prime number then these are the only two factors whereas composite numbers always have more than two factors.
|
Find the factors of 28.
Solution: Factors of 28 are the integral numbers which can completely divide 28 without leaving any remainder or decimal portion.
|
If there are 2 natural numbers x and y, the highest natural number which divides both x and y completely is called the highest common factor (HCF) or greatest common divisor (GCD) of x and y. In general, the largest natural number which completely divides the given natural numbers is the HCF of given numbers.
Let us consider the numbers 6 and 8 to understand the concept of HCF.
The factors of 6 are 1, 2, 3 and 6.
The factors of 8 are 1, 2, 4 and 8.
Common factors to both 6 and 8 are 1, 2.
The highest of the common factors (1 and 2) is 2.
Thus, HCF of 6 and 8 is 2.
This can be written as “HCF (6, 8) = 2”.
Let the two numbers whose HCF we are trying
to calculate be x and y, where x 
y. Then, to find the HCF (x, y):
Step 1: Check if y = 0. If so, then x is the HCF.
Step 2: If y ≠ 0, then write HCF (x, y) as HCF (y, x mod y) where ‘x mod y’ is the remainder when x is divided by y.
These become the new values for (x, y).
Continue performing the above two steps until y becomes 0; then x will be the HCF.
|
Find the GCD of 300 and 450.
Solution: Let x = 450 and y = 300 (
Now, (450 mod 300) = 150. Hence, HCF (450, 300) becomes HCF (300, 150).
Following a similar approach (now x = 300 and y = 150), HCF (300, 150) becomes HCF (150, 0).
Now, y has become 0; thus, x = 150 will be the HCF.
Hence, the GCD (300, 450) = 150 |
Step 1: Factorize all the given numbers into their prime factors.
Step 2: Collect all the common prime factors.
Step 3: Raise each of the prime factors to its minimum available power and multiply.
REMEMBER:
- You can also use this method to find HCF of two numbers.
|
Find the GCD of 300 and 450.
Solution: On factorizing all numbers into their prime factors, we get,
300 = 2
450 = 2
So, looking at the common factors, we see that 2, 3 and 52 are a part of both numbers.
Hence, the GCD (300, 450) = 2 |
REMEMBER:
- As seen by comparing the solutions using the two methods, it is generally faster to find the HCF of two numbers using the Euclidean algorithm rather than the above method.
|
Find the HCF of 100, 200 and 250.
Solution: On factorizing all numbers into their prime factors, we get, 100 = 22 200 = 23 250 = 21
Raising the common prime factors 2 and 5 to the minimum available powers gives, HCF (100, 200, 250) = 21 |
Let us consider an example,
|
Find the greatest number which when divides 49 and 35 leaves remainder 4 and 5 respectively.
Solution: Let the required number be n. When n divides 49, the remainder is 4.
Similarly, when n divides 35, the remainder is 5.
We can say that n is a common factor of 45 and 30. Since, n is the greatest possible number, we can say that n is the HCF of 45 and 30, i.e. 15. We can generalize the above concept as given below:
“The greatest natural number that will divide
x, y and z leaving remainders r1,
r2 and r3, respectively, is the HCF of
(x |
|
Find the greatest number which when divides 148, 635 and 762 leaves remainders 4, 5 and 6 respectively.
Solution: The required number = HCF of (148 = HCF (144, 630, 756) = 18 |
If we take the prime factors of any 2 prime numbers, let’s say 7 and 13, we get,
7 = 71
13 = 131
Thus HCF (7, 13) = 1
Thus for any two different prime numbers, the HCF is always 1.
Similarly, for any two different co-prime numbers, the HCF is always 1.
If there are 2 natural numbers x and y, the least natural number which can be divided by both x and y completely is called the least common multiple (LCM) of x and y. In general, the smallest natural number which is completely divisible by the given natural numbers is the LCM of given numbers.
Let us consider the numbers 6 and 8 to understand the concept of LCM.
The multiples of 6 are 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, …
The multiples of 8 are 8, 16, 24, 32, 40, 48, 56, 64, …
Common multiples to both 6 and 8 are 24, 48, …
The least of the common multiples (24, 48, …) is 24.
Thus, LCM of 6 and 8 is 24.
This can be written as “LCM (6, 8) = 24”.
|
Find the LCM of 96 and 36.
Solution: The multiples of 96 are 96, 192, 288, …
The multiples of 36 are 36, 72, 108, 144, 180, 216, 252, 288, …
The least common multiple for 96 and 36 is 288.
Thus, LCM (96, 36) = 288 |
Step 1: Factorize all the given numbers into their prime factors.
Step 2: Collect all the distinct prime factors.
Step 3: Raise all the prime factors to their maximum available powers and multiply.
|
Find the LCM of 42 and 36.
Solution: On factorizing all numbers into their prime factors we get, 42 = 2 36 = 2
The distinct prime factors that occur in either of the given numbers are 2, 3 and 7.
The highest power of 2 is 22, the highest power of 3 is 32, while the highest power of 7 is 71.
Thus, LCM (42, 36) = 22 |
This method can be used to find LCM of more than two numbers as well.
|
Find the LCM of 8, 12 and 15.
Solution: 8 = 23 12 = 22 15 = 3 Hence, LCM (8, 12, 15) = 23 |
Let us consider an example,
|
Find the least number which when divided by 42 and 70 leaves remainder 4 in each case.
Solution: Let the required number be n.
When n is divided by 42, the remainder is 4.
Similarly, when n is divided by 70, the remainder is 4.
We can say that (n – 4) is the common multiple of both 42 and 70. Since n is the least possible number, we can say that (n – 4) is the LCM of 42 and 70 i.e. 210.
|
We can generalize the above concept as given below:
“The smallest natural number that is divisible by x, y and z leaving the same remainder r in each case is equal to LCM of (x, y, z) + r”.
|
Find the least number which when divided by 12, 14 and 20 leaves remainder 3 in each case.
Solution: The required number = LCM (12, 14, 20) + 3 = 420 + 3 = 423 |
|
Find the least number which when divided by 11, 15 and 20 gives the remainders 7, 11 and 16 respectively.
Solution: Let the required number be x. Then, the remainder when x is divided by 11 is 7. So, (x – 7) is completely divisible by 11. Since, 11 is obviously divisible by 11, it implies that [(x – 7) + 11] is also divisible by 11.
Similarly, (x + 4) is also completely divisible by 15 and 20.
Hence, (x + 4) is the LCM (11, 15, 20)
|
|
Let x denote the greatest 4-digit number which when divided by 6, 7, 8, 9 and 10 leaves a remainder of 4, 5, 6, 7 and 8 respectively. Then, the sum of the four digits of x is: [JMET 2010]
(1) 25(2) 18 (3) 20(4) 22
Solution: The LCM of 6, 7, 8, 9 and 10 is 2520. The largest possible 4-digit multiple of 2520 is 7560. As x leaves remainders of 4, 5, 6, 7 and 8 when divided by 6, 7, 8, 9 and 10 respectively, x = 7558
Hence, option 1. |
|
IBM-Daksh observes that it gets a call at an interval of every 10 minutes from Seattle, at every 12 minutes from Arizona, at the interval of 20 minutes from New York and after every 25 minutes it gets the call from Newark. If in the early morning at 5:00 a.m. it has received the calls simultaneously from all the four destinations, then at which time it will receive the calls at a time from all places on the same day? [IIFT 2007]
(1) 10:00 a.m.(2) 3:00 a.m. (3) 5:00 p.m.(4) both (1) and (2)
Solution: IBM-Daksh will get calls from all four places simultaneously after every (LCM of 10, 12, 20 and 25 =) 300 minutes, which is 5 hours. So, the company gets all 4 calls simultaneously at 10 a.m., then at 3.00 p.m., and then finally at 8.00 p.m. (only calls on the same day have been included.) Hence, option 1. |
|
How many even integers n, where 100 [CAT 2003 Leaked Test]
(1) 40(2) 37 (3) 39(4) 38 Solution: Number of even integers satisfying inequality i.e.
100
Total even integers divisible by 7 = 112, 126, 140, 154, 168, 182, 196 = 7
Total even integers divisible by 9 = 108, 126, 144, 162, 180, 198 = 6
The number 126 is repeated in both the sets.
Hence, option 3. |
If we take the prime factors of any 2 prime numbers, let’s say 7 and 13, we get
7 = 71
13 = 131
Thus LCM (7, 13) = 71 
131 = 91
Thus for any two different prime numbers, the LCM is the product of the two numbers.
For example, LCM (3, 11) = 33
Similarly, for any two different co-prime numbers, the LCM is the product of the two numbers.
For example, LCM (4, 9) = 36
We begin with an example to establish the relation between factors and LCM.
Consider a number n = 36, then how many sets of pairs of two factors (a, b) of n are there for which the LCM (a, b) = 36?
Here n = 36 = 22
32
Here the factors a and b must be such that both 22 and 32 must be contained in either a or b
Possible sets satisfying above condition are (36, 1); (36, 2); (36, 3); (36, 4); (36, 6); (36, 9); (36, 12); (36; 18); (36, 36); (18, 4); (18, 12); (12, 9); (9, 4).
Thus there are 13 sets of numbers which have LCM = 36
In general if n =
ax
by
cw
…, then the set of values (a, b) such that LCM (a,
b) = n can be given by:
In the above case, x = 2 and y = 2, hence,
|
Find the possible number of distinct ordered pairs (a, b) of two integers a and b, such that LCM (a, b) = 24.
Solution: 24 = 23
Number of sets (a, b)
Here, x = 3 and y = 1
Number of sets (a, b)
= 11 Except one pair (24, 24), the other 10 pairs can be
reversed to get distinct ordered pairs; hence the total number of pairs =
10 |
Process to find HCF and LCM of fractions is slightly different from the method discussed above (for natural numbers).
The following formula is useful to find HCF of fractions:
HCF of factions 
The following formula is useful to find LCM of fractions:
|
Find the LCM of 1/2 and 3/4.
Solution: Here the LCM of the numerators, i.e. 1 and 3, is 3 and the HCF of the denominators, i.e. 2 and 4, is 2. Thus, using the above formula: LCM of 1/2 and 3/4 = (LCM of 1 and 3)/(HCF of 2 and 4) = 3/2 |
|
Find the product of HCF and LCM of 7/13 and 3/5.
Solution: HCF of numerators = HCF (7, 3) = 1
LCM of denominators = LCM (13, 5) = 13
Thus HCF of fractions = 1/65
Similarly,
LCM of numerators = LCM (7, 3) = 7 HCF of denominators = HCF (13, 5) = 1
Thus LCM of fractions = 21/1 = 21
Thus, the required product = HCF |
REMEMBER:
- In the above example, product of the two fractions = 7/13
3/5 = 21/65
Thus, HCF
LCM of two numbers = Product of two numbers
Let us take one more example,
HCF (6, 8)
LCM (6, 8) = 2
24 = 48
= Product of two numbers 6 and 8
This is true for two numbers only. However, if there are more than two co-prime numbers, then this formula can be applied to any number of numbers.
IMPORTANT:
- It must be kept in mind that HCF and LCM are concepts defined only for positive numbers, be it an integer or a fraction. HCF and LCM are not defined for negative numbers or zero.
|
How many pairs of natural numbers exist that such that their HCF = 19 and their LCM = 5985?
Solution: Let the two numbers be a and b respectively. Now, HCF of the two numbers = 19. This means that both a and b are multiples of 19. That is, the prime factorization of a and b would look something like this:
a = 19
b = 19
Since HCF = 19, therefore 19 will be the only prime factor that is common to both a and b.
Now, LCM of a and b = 5985 =
32
This means that between the two numbers, only the primes 32, 5, 7 and 19 should be used (no other number, prime or otherwise, can be used). Combining this with the condition that 19 should be the only prime factor that is common to both numbers, we have the following possibilities:
Hence, FOUR pairs of natural numbers exist that such that their HCF is 19 and their LCM is 5985. |
|
In a book store, the words of the glowsign board "MODERN BOOK STORES" are individually flashed after 5/2, 17/4 and 41/8 seconds respectively. Each word is put off after a second. What is the least time after which full name of the book store can be read? [CAT 2002]
(1) 73.5 seconds(2) 79.4 seconds (3) 68.2 seconds(4) None of these
Solution: The words MODERN, BOOK and STORES appear after 5/2, 17/4 and 41/8 seconds respectively and are put off after 1 second. So, if all the words flashed together at t = 0 seconds, then MODERN will flash after (5/2 + 1) = 7/2 seconds BOOK will flash after (17/4 + 1) = 21/4 seconds STORES will flash after (41/8 + 1) = 49/8 seconds. So, all the words will flash together again after LCM(7/2, 21/4, 49/8) seconds.
Hence, option 1. |
|
There are three pieces of cake weighing 9/2 lbs, 27/4 lbs and 36/5 lbs. Pieces of the cake are equally divided and distributed in such a manner that every guest in the party gets one single piece of cake. Further the weight of the pieces of the cake is as heavy as possible. What is the largest number of guest to whom we can distribute the cake?
[CAT 2002]
(1) 54(2) 72 (3) 20(4) None of these
Solution: The weight largest possible piece of cake from the three given pieces [9/2, 27/4, 36/5] can be obtained by finding the H.C.F of the three fractions,
|
REMEMBER:
- HCF of co-prime numbers is always 1.
- LCM of co-prime numbers is product of the numbers.
- HCF
LCM of two numbers = Product of the two numbers
- HCF of fractions
- LCM of fractions
Sometimes we have to determine whether a given number is divisible by some other number; but we don’t need the quotient, so it would be a waste of time to actually divide the number. Instead, we have simple tests to do this. These are called divisibility tests and they help us in finding out factors of any number.
To find out if a number is divisible by 2, we just need to check the last digit of that number. If the last digit of a number is 2, 4, 6, 8 or 0, then it is divisible by 2; otherwise it is not.
For example, 5132 is divisible by 2 but 26119 is not divisible by 2.
Add all the digits of the given number. If the sum obtained is divisible by 3, only then is the number divisible by 3.
For example, 143 is not divisible by 3, because sum of digits = 1 + 4 + 3 = 8 and 8 is not divisible by 3.
Similarly, 186 is divisible by 3, because sum of digits = 1 + 8 + 6 = 15 and 15 is divisible by 3.
REMEMBER:
- Any number that is not divisible by 3, will leave a remainder of 1 when its square is divided by 3.
If the number formed by last two digits of a number is divisible by 4, then the number is divisible by 4.
For example, 6124 is divisible by 4, because the number formed by last two digits i.e. 24 is divisible by 4.
But, 3842 is not divisible by 4, because the number formed by last two digits i.e. 42 is not divisible by 4.
If last digit of a number is 5 or 0, only then is it divisible by 5.
For example, 2365890 and 455152125 are divisible by 5 but 22445644 is not divisible by 5.
If a number is divisible by 2 and 3 both, then it is divisible by 6. (Use divisibility tests of 2 and 3 individually on the given number; if it passes both, then it is divisible by 6). This is because 6 is the product of two relatively prime numbers, 2 and 3; any natural number n that is divisible by two co-prime numbers, p1 and p2 individually, will also be divisible by the product p1p2. This concept had been covered in the Concept Builder of Number Systems.
For example, the last digit of 258 is 8; thus, it is divisible by 2. The sum of digits of 258 = 2 + 5 + 8 = 15, which is divisible by 3. Thus, 258 is divisible by both 2 and 3; hence it is divisible by 6.
Double the last digit and subtract it from the number left with the remaining digits. If the result is divisible by 7, then the number is divisible by 7; otherwise it is not.
For example, 161 is divisible by 7, because the last digit of 161 is 1. Doubling it we get 2. Remaining digits give the number 16. On subtracting 2 from 16 we get 14, which is divisible by 7.
The process can be repeated for number with more than 3 digits. For example, to test the number 109543.
REMEMBER:
- 0 is divisible by 7. So, if the result turns out to be 0, then the number is divisible by 7. For example, check for the divisibility of 1932 by 7 using the above method.
If the number formed by last three digits of a number is divisible by 8, only then is the number divisible by 8.
For example, 6124 is not divisible by 8, because the number formed by last three digits, i.e. 124, is not divisible by 8.
REMEMBER:
- When an odd number x is squared, then x2 will always leave a remainder of 1 when divided by 8.
Add all the digits of the number. If the sum obtained is divisible by 9, then the number is divisible by 9; otherwise, it is not.
For example, 51363 is divisible by 9, because the sum of the digits = 5 + 1 + 3 + 6 + 3 = 18 is divisible by 9.
REMEMBER:
- Also, the difference between two numbers ab and ba, i.e. |ab – ba| is always divisible by 9.
If last digit of a number is 0, only then is it divisible by 10.
For example, 2110 is divisible by 10, but 10001 is not divisible by 10.
Add up all the digits in odd positions of the number. Then add up all the digits in even position. If the difference of these two additions is a multiple of 11, then the number is divisible by 11; otherwise, it is not. The positions of the digits are taken from left to right; i.e. the first digit will have position 1 (odd position), the second digit will have position 2 (even position), and so on.
For example, consider the number 13475:
Digits in odd positions are 1 (position 1), 4 (position 3) and 5 (position 5).
Their sum is 1 + 4 + 5 = 10
Digits in even positions are 3 (position 2) and 7 (position 4). Their sum is 3 + 7 = 10
The difference in the two sums = 10 
10 = 0
Since 0 is divisible by 11, 13475 is divisible by 11.
When a number is divided by 11 and the remainder is asked, start by calculating:
CASE 1: [(Sum of the digits in odd positions) – (Sum of the digits in even positions)], if the number of digits in odd positions is greater than the number of digits in even positions.
CASE 2: [(Sum of the digits in even positions) – (Sum of the digits in odd positions)], otherwise (i.e. if the number of digits in odd positions and the number of digits in even positions are equal.)
Then, find the remainder when the above result is divided by 11.
Generally speaking, in cases where the dividend or divisor or both are negative, there may be 2 possible remainders for the same division – one positive and the other negative. You can convert the negative remainder to the positive one by adding the absolute value of the divisor to it (i.e. positive remainder = |divisor| + negative remainder).
The remainder we require will be the positive one. For example, if you get the result of Case 1 (or 2) as –190, which on division by 11 gives quotient q and remainder r,
–190 = (11) q + r
Here, when q = –17, r = –3
Thus, positive remainder = |11| + (–3) = 8 (which is true when q = –18)
If the number is divisible by 3 and 4 both, then the number is divisible by 12.
Here we use the divisibility tests of 3 and 4 individually on the given number, as they are co-prime numbers.
IMPORTANT:
- We cannot use the divisibility tests of 6 and 2 (for divisibility test of 12) as 6 is a multiple of 2.
If (x + 4y) is divisible by 13 then the number is divisible by 13. Here, y is the units place digit and x is the number formed by all the remaining digits.
For example:
Let us consider the number 182.
Here y = 2 and x = 18, then (x + 4y) = 26 which is divisible by 13. Thus the given number 182 is divisible by 13.
Similar to the divisibility test we had applied for 7, this test can also be repeated several times for larger numbers. For example, to find whether 203437 is divisible by 13:
20343 + (7
4) = 20371
2037 + (1
4) = 2041
204 + (1
4) = 208
20 + (8
4) = 52, which is divisible by 13
Hence, 203437 is divisible by 13.
If the number is divisible by 2 and 7 both, then the number is divisible by 14. Thus, the number must always be even if it has to be divisible by 14.
If the number is divisible by 3 and 5 both, then the number is divisible by 15. In other words, if the sum of digits is divisible by 3 and the unit’s digit is 0 or 5, then the number is divisible by 15.
If the number formed by the last 4 digits of the number taken together is divisible by 16, only then is the number divisible by 16.
If (x
5y) is divisible by 17, then the number is divisible by 17. Here,
y is the units place digit and x is the number formed by all the
remaining digits.
For example:
Let us consider the number 527.
Here y = 7 and x = 52, then
x
5y = 17 which is divisible by 17.
Thus the given number 527 is divisible by 17.
Now let’s consider the number 56933.
5693 – (3
5) = 5678
567 – (8
5) = 527, which we have just shown is divisible by 17.
Hence, 56933 is divisible by 17.
If the number is divisible by 2 and 9 both, then the number is divisible by 18.
If (x + 2y) is divisible by 19, then the number is divisible by 19. Here, y is the units place digit and x is the number formed by all the remaining digits.
For example:
Let us consider the number 665.
Here y = 5 and x = 66, then x + 2y = 76 which is divisible by 19.
Thus the given number 665 is divisible by 19.
Now, let us consider the number 12635.
1263 + (5
2) = 1273
127 + (3
2) = 133
13 + (3
2) = 19, which is definitely divisible by 19.
Hence, 12635 is divisible by 19.
If the number is divisible by 4 and 5 both, then the number is divisible by 20.
The process to check whether a natural number is divisible by a prime number p, is as follows:
Step 1: Find the smallest multiple of
p, which is of the form (10k + 1) or (10k
1), where k is a natural number.
Step 2: If it is of the form (10k – 1), then we check whether (x + ky) is divisible by p or not, and if it is of the form (10k + 1) then we check whether (x – ky) is divisible by p or not. Here y is the unit’s digit of the given prime number and x is the number formed by rest of the digits of the given prime number. The process can be repeated if the given number is having more than 3 digits.
REMEMBER:
- Please don’t try using this method for the prime numbers 2 and 5; use the ones mentioned above instead. It is, however, possible to use this method for divisibility by 3; it will result in the form (x + y).
|
Is 4012 divisible by 17?
Solution: The least multiple of 17 of the form (10k
Thus the divisibility rule of 17 is to check whether
(x Here x = 401 and y = 2, hence
(x
Now, we repeat the process for divisibility test of
17 for 391.
The new x = 39 and new y = 1, hence
new (x
Since 34 is divisible by 17, hence 391 is divisible
by 17 and hence 4012 is also divisible by
17. |
A brief summary of the divisibility tests:
| For a number to be divisible by: |
It should satisfy the following conditions: |
| 2 | The last digit should be divisible by
2; i.e. it should be 2, 4, 6, 8 or 0. |
| 4 | The number formed by the last 2 digits should be divisible by 4. |
| 8 | The number formed by the last 3 digits should be divisible by 8. |
| 16 | The number formed by the last 4 digits should be divisible by 16. |
| 3 | The sum of its digits should be divisible by 3. |
| 9 | The sum of its digits should be divisible by 9. |
| 5 | The last digit should be either 5 or 0. |
| 10 | The last digit should be 0. |
| 7 | (x – 2y) should be divisible by 7.* |
| 13 | (x + 4y) should be divisible by 13.* |
| 17 | (x – 5y) should be divisible by 17.* |
| 19 | (x + 2y) should be divisible by 19.* |
| * Here, y is the last
digit and x is the number formed by the remaining digits. These 4 results can be derived using the divisibility test for prime numbers. | |
| 6 | It should be divisible by both 2 and 3. |
| 12 | It should be divisible by both 3 and 4. |
| 14 | It should be divisible by both 2 and 7. |
| 15 | It should be divisible by both 3 and 5. |
| 18 | It should be divisible by both 2 and 9. |
| 20 | It should be divisible by both 4 and 5. |
| 11 | The difference of the sum of the digits in
odd positions and the sum of the digits in even positions should be divisible by 11. |
|
What should be the values of a and b such that 1a8b is divisible by 2, 3, 4, 6, 7 and 8?
Solution: In order for 1a8b to be divisible by 2, b should be 2, 4, 6, 8 or 0.
Also, since 1a8b is divisible by 4, the number formed by the last two digits (i.e. 8b) should be divisible by 4. Hence, b must be 0, 4 or 8.
Since the number is divisible by 3, the sum of all its digits should be divisible by 3; i.e. (9 + a + b) should be divisible by 3. As 9 is already divisible by 3, we can effectively say that (a + b) ought to be divisible by 3. So, the possible pairs of (a, b) are (3, 0), (6, 0), (9, 0), (2, 4), (5, 4), (8, 4), (1, 8), (4, 8) and (7, 8).
There is no need to check whether the number is divisible by 6, since any number divisible by both 2 and 3 will be divisible by 6.
To be divisible by 8, the number formed by the last
3 digits (i.e. a8b) should by divisible by 8. Of the above
possible pairs, only the pairs (6, 0), (5, 4) and (4, 8) satisfy this
criteria (
For a number to be divisible by 7, (x – 2y) must be divisible by 7, where y is the unit’s digit and x is the number formed by the remaining digits. Now, let’s substitute the above 3 pairs of a and b and see which of those satisfy this criteria: 1488
1584 1680
Hence, a = 6 and b = 0 |
148 – 16 = 132
|
What will be the remainder when 703477 is divided by 11?
Solution: Sum of digits in odd positions = 7 + 3 + 7 = 17 Sum of digits in even positions = 0 + 4 + 7 = 11
Since the number of digits in odd positions and the number of digits in even positions are equal, hence,
[(Sum of the digits in even positions) – (Sum of the digits in odd positions)] = 11 – 17 = –6 Hence, remainder when 703477 is divided by 11 = |11| + (– 6) = 5 |
|
The digits of a three-digit number A are
written in the reverse order to form another three-digit number B.
If B > A and B [CAT 2005]
(1) 100 < A < 299(2) 106 < A < 305 (3) 112 < A < 311(4) 118 < A < 317
Solution: Let A = 100x + 10y + z (x ≠ 0, x, y, z are single-digit numbers)
As (B – A) is divisible by 7 and 99 is not, (z – x) is divisible by 7.
y can have any value from 0 to 9.
A = 1y8 or 2y9
Hence, option 2. |
1) WHERE n IS A NATURAL NUMBER
In this method, we will consider two factors
– one is the value of n and the other being the sign between
(10n 
1). The value of n will decide the number of digits to be taken at a time
and the sign indicates in what manner these digits will be taken.
Case 1: When n = 1 and the sign is positive:
Then (10n + 1) = 11
This is the divisibility rule of 11 stated earlier where we took one digit at a time and subtracted the sum of alternate digits starting from the right.
Thus n = 1 means that one digit has to be taken at a time and the positive sign implies that the sum of alternate digits must be subtracted starting from the right. Then, we check whether this result is divisible by 11 or not.
Case 2: When n = 1 and the sign is negative:
Then (10n
1) = 9
This is the divisibility rule of 9 stated earlier where we took one digit at a time and added all the digits starting from the right.
Thus n = 1 means that one digit to be taken at a time and negative sign implies that the digits must be added starting from the right. Then we check whether this result is divisible by 9 or not.
Case 3: When n = 2 and the sign is positive:
Then (10n + 1) = 101
Thus we want to find the divisibility rule for 101.
Here n = 2 means that two digit pairs are to be taken at a time and positive sign implies that the sum of two alternate digit pairs must be subtracted starting from the right. Then we check whether this result is divisible by 101 or not.
|
Check the divisibility of 21802971 by 101?
Solution: Step 1:
Here n = 2, thus group the digits into pairs of two starting from the right.
21 80 29 71
Step 2: Sum of all odd digit pairs = 71 + 80 = 151 Sum of all even pairs = 29 + 21 = 50 Difference of the sum of odd and even pair sums = 101
This is divisible by 101, which shows that the number is divisible by 101. |
Case 4: When n = 2 and the sign is negative:
Then (10n
1) = 99
Thus we are finding the divisibility rule of 99.
Here n = 2 means that two digit pairs are to be taken at a time and negative sign implies that the sum of two digit alternate pairs must be added starting from the right.
|
Is 1222155 divisible by 99?
Solution: Step 1: Here n = 2, thus group the digits into pairs of two starting from the right. 01 22 21 55 Step 2: Sum of all the two digit pairs = 01 + 22 + 21 + 55 = 99
This is divisible by 99, which shows that the number is divisible by 99. |
This concept can be extended for any natural number n.
REMEMBER:
- As we have discussed the tests for divisibility, we can see that
unique rules for test of divisibility is available for prime numbers (for
example, 2, 3, 5, 7, 11, 13, 17, 19 etc.) or any power of prime numbers (for
example, powers of 2 = 4, 8, 16, 32 etc. or powers of 5 = 25, 125, 625 etc.).
The rules of tests of divisibility for prime numbers and the corresponding
powers of prime numbers are similar. For example, to check the divisibility by
2 or 4 or 8, we check whether the number formed by last 1 or 2 or 3 digits
respectively is divisible by 2 or 4 or 8 respectively [
2 = 21, 4 = 22 and 8 = 23]. Also, to check
the divisibility by 5 or 25 or 125, we need to check if the number ends in 5
or 0 (for divisibility by 5), or in 25, 50, 75 or 00 (for divisibility by 25),
or in 125, 250, 375, 500, 625, 750, 875 or 000 (for divisibility by
125).
- For other composite numbers which cannot be represented as a
power of a prime number, we re-write the number as product of two co-prime and
then apply the tests of divisibility for both these numbers. For example, to
test the divisibility by 24, we write 24 as 3
8 and then apply the tests of both 3 and 8 to check whether the given number
is divisible by 24 or not. Similarly to test the divisibility by 36, we apply
the tests of both 4 and 9 [
36 = 4
9].
If we are interested in finding the sum of divisors of a number we can follow the following steps:
Step 1:
Factorize the number n into its prime factors.
i.e. n = ax
by
cw
…, where a, b, c are prime numbers.
Step 2:
For example, the divisors of 12 are 1, 2, 3, 4, 6 and 12. Hence, the sum = 28
Using the above method, we have,
12 = 22
3
|
Find out the sum of divisors of n = 420
Solution: Factorizing the number into its prime factors, we get,
420 = 22
|
If we are interested in finding the number of divisors of a number, we can follow the following steps:
Step 1:
Factorize the number n into its prime factors.
i.e. n = ax
by
cw
… where a, b, c are prime numbers.
Step 2:
Then, number of divisors = (x + 1)(y + 1)(w + 1)…
For example, the divisors of 12 are 1, 2, 3, 4, 6 and 12. Hence, it has 6 divisors.
Using the above method, we have,
12 = 22
31
Number of divisors = (2 + 1)(1 + 1) = 3
2 = 6
Explanation:
This can be derived from basics of permutation which is discussed below:
There are x a’s, i.e. we can have (x + 1) combinations of these x a’s as we can vary the power of a from 0 to x. Similarly, permutations for other prime factors will be (y + 1), (w + 1) and so on. Thus total number of divisors will be a product of these different combinations.
Thus, total number of divisors possible =
(x + 1)
(y + 1)
(z + 1) and so on.
|
Determine the number of divisors of n = 1680
Solution: Factorizing the number into its prime factors, we get,
1680 = 24
Thus, number of divisors = (4 + 1)(1 + 1)(1 + 1)(1 + 1)
Thus, number of divisors of 1680 = 5 |
The number of ways in which a composite number n (= axbycz) which is not a perfect square may be resolved into two factors
Here, neither of x, y nor z are even as the number is not a perfect square.
For example, 12 is not a perfect square. It
can be written as 12 = 22
3
Hence, the number of ways of expressing it as a product of 2 factors
These are (1, 12), (2, 6) and (3, 4).
However, if x, y and z
are all even i.e. n is a perfect square, then the product (x +
1)(y + 1)(z + 1)… becomes odd and the above rule will not be valid
since we cannot halve an odd number to get a natural number (the number of
ways). Being a perfect square, it can be written in the form of 
square root.
For example, we can write 36 = 
which will add one way in which the number can be expressed.
So, two different cases arise in the case of
perfect squares depending on whether we are considering the case where we can
write the number as
The number of ways in which a perfect square n may be resolved into two factors:
and,
For example, consider the perfect square 36.
It has 5 ways of expressing it as a product of its factors if 
was to be included; these are (1
36), (2
18), (3
12), (4
9) and (6
6). Obviously, there’ll only be 4 ways to express it if 
Now, let’s try using the above method: 36 =
22
32
Using the same notation as above, i.e.
n = ax
by
cz, the number of ways of writing n as a product of 2
co-primes can be given by:
where, m is the number of distinct prime factors of number n.
For example, 120 can be written as (3
40), (8
15), (24
5) and (120
1); i.e. there are a total of 4 ways of writing 120 as a product of 2
co-primes.
Using the above method, we have,
120 = 23
3
5
Thus, it has 3 distinct prime factors, 2, 3 and 5 (i.e. m = 3).
The number of ways of writing 120 as a product of 2 co-primes = 23 –
1 = 22 = 4
Explanation:
Let n = ax
by
cz be the number where a, b and c are
primes and x, y and z are natural numbers.
Since we need to write n as a product of 2 factors that are co-prime to each other, hence each of the terms a, b and c can be part of ONLY one factor. This is because, if for example, we split ax as (ax – 1) and a1, and make them part of two different factors, then the two factors will no longer be co-prime (since their HCF is now a, and not 1).
So, for our purpose, n =
ax
by
cz is equivalent to writing n =
a1b1c1. Using the formula
for finding the number of ways to write a number as a product of 2 factors, we
have,
Where, m is the number of distinct prime factors of n.
Here, we are interested in finding out the number of sets of factors of a given number n which are co-prime to each other.
The number of sets of co-prime factors for
n = ax
by will be equal to (x + 1)(y + 1)
1 + xy
Similarly if a number has three prime
factors, i.e. n = ax
by
cz, then the number of sets of co-prime factors will be given
by:
Number of sets of co-prime factors =
(x + 1)(y + 1)(z + 1)
1 + xy + yz + xz + 3xyz
For example, the number 12 whose factors are 1, 2, 3, 4, 6 and 12 has the following sets of co-prime factors:
(1, 2), (1, 3), (1, 4), (1, 6), (1, 12), (2, 3) and (3, 4), i.e. 7 in number.
Using the above method, we have,
12 = 22
31
Number of sets of co-prime factors = (2 + 1)(1 + 1) – 1 + (2
1) = 3
2 – 1 + 2 = 7
The number of co-primes of n =
ax
by
cz which are less than n is represented by the
function,
This is known as Euler’s function.
For example, let us consider the number 12.
If this is factorized, we get the co-prime factors as 2 and 3.
These four numbers, which are less than 12 and co-prime to it, are 1, 5, 7 and 11.
After finding the number of co-primes to n less than n, the next task would be to calculate the sum of these co-primes less than n.
where, f(n) is the number of co‐primes < n
Continuing with our previous example and using the above formula, we have,
This can be proved as the sum of the numbers which are less than 12 and co-prime to it = 1 + 5 + 7 + 11 = 24
A Summary:
Let’s consider the number 12 as the standard example for all the following operations.
It’s factors are 1, 2, 3, 4, 6 and 12 and its prime factorization is expressed as
12 = 22
3 = ax
by (i.e. a = 2, b = 3, x = 2 and y
= 1)
REMEMBER:
- If p is a prime number and a and b are integers, then the coefficient of every term in the expansion of (a + b)p, except the first and the last, is divisible by p.
|
Find the ways in which the number 192 can be written as a product of 2 of its co-prime factors? Also, find the number of ways to express it as a product of any 2 factors.
Solution: Factorizing 192 in terms of its prime factors, we get, 192 = 26
01 22 21 55 Thus here m = 2, which represents the number of co-prime factors, i.e. 2 and 3. Also, x = 6 and y = 1.
Number of ways of writing the number as a product of 2 of its co-primes = 2m–1 = 22 Also, number of ways of writing 192 (note that it is not a perfect square) as a product of 2 of its factors
|
|
If the difference between (1034 + 57) and (1033 + n) is divisible by 9, then what could be the value of n from among the following?
(1) 569(2) 570(3) 571 (4) 572(5) 573
Solution: Here, we will use the property that the difference between ab (i.e. 10a + b) and ba (i.e. 10b + a) is divisible by 9. So, let us write (1034 + 57) in the form (10a + b):
1034 + 57 = 10 a = 1033 and b = 57
So, if the other number were in the form (10b + a), then the difference will be divisible by 9.
Hence, the second number could be: (10b + a) = 10
Hence, option 2. |
We can use this concept to find the unit’s or tens’ digit of a number raised to some large power which can be used further during division.
For example:
Find the last digit of (167)125?
How do we solve this type of a question? It is not possible to evaluate such a large number to find its unit’s digit even on a calculator. This is done using the cyclicity rule.
The last digit of (167)125 depends only on the last digit i.e. 7.
So, last digit of (167)125 is same as the last digit of (7)125. If we find this out, we get the answer.
To find out last digit of (7)125, let us start noting the powers of 7.
and so on.
Thus, last digit of power of 7 changes after very four numbers.
So to find last digit of (7)x for any value of x:
Step I:
Divide x by 4 and find the remainder.
Step II:
If remainder is 1, the last digit is 7.
If remainder is 2, the last digit is 9.
If remainder is 3, the last digit is 3.
If remainder is 0, the last digit is 1.
|
Find the last digit of (7)125.
Solution: Step I: 125 divided by 4 gives remainder 1. Step II: The last digit is 7. |
Thus,
Last digit of (167)125 = Last digit of (7)125 = 7.
For example: Find the last digit of (129)468.
The last digit of (129)468 depends only on the last digit i.e. 9.
So, last digit of (129)468 is same as the last digit of (9)468. If we find this out, we get the answer.
Similarly,
To find out last digit of (9)468, let us start noting the powers of 9.
and so on.
Thus, last digit of power of 9 changes after very two numbers.
So to find last digit of (9)x for any value of x:
Step I:
Divide x by 2 and find the remainder.
468 divided by 2 gives remainder 0.
Step II:
If remainder is 1, the last digit is 9.
If remainder is 0, the last digit is 1.
Here, the last digit is 1.
Thus,
Last digit of (129)468 = Last digit of (9)468 = 1
Similarly, we can show that,
Cyclicity of 2 = 4
Cyclicity of 3 = 4
Cyclicity of 4 = 2
Cyclicity of 5 = 1 as the last digit will always be 5
Cyclicity of 6 = 1 as the last digit will always be 6
Cyclicity of 7 = 4
Cyclicity of 8 = 4
Cyclicity of 9 = 2
|
What is the unit’s digit of (248)4667
Solution: The unit’s digit of (248)4667 will be the same as the unit’s digit of (8)4667. Now, cyclicity of 8 is as follows:
81 82 83 84 85 .. . .. . .. . and so on. So, the cyclicity is 4. The remainder when 4667 is divided by 4 is 3; and the last digit of 83 is 2. Hence the unit’s digit of (248)4667 is 2.
The unit’s digit of (876)873 will be the same as that of (6)873. Now, cyclicity of 6 is 1. Hence, the unit’s digit of (876)873 will be 6.
The unit’s digit of (124)42 will be the same as the unit’s digit of (4)42. Now, cyclicity of 4 is as follows: 41 42 43 ... ... ... and so on. So, the cyclicity is 2. The remainder when 42 is divided by 2 is 0; and the last digit of 42 is 6. Hence the unit’s digit of (124)42 is 6.
The unit’s digit of (62)342 will be the same as that of (2)342. Now, cyclicity of 2 is as follows: 21 22 23 24 25 . . . . . . . . . and so on. So, the cyclicity is 4, and the remainder when 342 is divided by 4 is 2. Hence, the unit’s digit of (62)342 will be 4.
Hence, the unit’s digit of (248)4667 |
|
The rightmost non-zero digit of the number 302720 is [CAT 2005]
(1) 1(2) 3 (3) 7(4) 9 Solution: 302720 = 32720
The rightmost non-zero digit of 302720 will be the digit in the unit’s place of 32720.
3’s power cycle is 3, 9, 7, 1 and cyclicity is 4. i.e. if we get a remainder of 1, 2, 3, or 0 when 2720 is divided by 4, then the digit in the units place will be 3, 9, 7, or 1 respectively.
2720 = 680
Hence, option 1. |
|
Find the unit’s digit of
Solution:
Hence, the unit’s digit of
|
Just as the unit’s digit of a number that is raised to varying powers repeats itself in cycles, similarly the ten’s digit also shows cyclicity.
For example,
71 = 07,
72 = 49,
73 = (__43),
74 = (__01),
75 = (__07),
76 = (__49),
77 = (__43),
78 = (__01),
. . .
. . .
. . .
and so on.
Hence, the ten’s digit cyclicity of 7 is 4. That is, if a power n when divided by 4 gives the remainder 1, 2, 3 or 0, then the ten’s digit of 7n will be 0, 4, 4 or 0 respectively.
The cyclicity of the ten’s digit of the digits from 2 to 9 is given:
|
What is the tens’ place digit of (13)42?
Solution: For this we will expand (13)42 by using the binomial theorem as (10 + 3)42. This expression will have 43 terms. Out of these 43 terms, the first 41 terms will be having both their tens and units place digit as 0. So the last two terms will decide the tens’ place digit.
Here 42nd term is
42C41 Similarly, 43rd term is
42C42
Summing up both terms tens’ place digit of the given number is tens’ digit of 1260 + 09 = 6 Hence, tens’ digit of given number = 6 |
|
What are the last two digits of 72008? [CAT 2008]
(1) 21(2) 61(3) 01 (4) 41(5) 81
Solution: 72 = 49 73 = 343 74 = 2,401 75 = 16,807 76 = 1,16,649 77 = 8,23,543 78 = 57,64,801 As we can see, for every 4th power of 7, the last two digits are 01. Since 2008 is divisible by 4, we can conclude that last two digits of 72008 are 01. Hence, option 3. |
REMEMBER:
- Unit’s digit of (any even number)4n = 6
- Unit’s digit of (any odd number)4n = 1
For example, Unit’s digit of (25532)2216 will have unit’s digit of 6
Exceptions to above rule: 0, 1, 5, 6 which are independent of power and unit digit will be the same respectively.(25)n and (76)n will always give 25 and 76 as the units and tens digit for any natural number value of n.
Dividend = Quotient
Divisor + Remainder
There are two methods to find the remainder,
- Cyclicity or Pattern method
- Theorem method
There exists cyclicity in case of remainders as well. Here, we keep finding the remainders for different powers until the remainder repeats itself.
|
What is the remainder when 496 is divided by 6? [CAT 2003 Re-Test]
(1) 0(2) 2 (3) 3(4) 4
Solution: 41, 42, 43, 44, … and so on give remainder 4 on division by 6. That is, 4n (n being any positive integer) when divided by 6, will always give the remainder 4. Hence, option 4. |
|
Find the remainder when 41001 is divided by 7?
Solution: Start with the least power of 4 which on dividing by 7 will give the remainder. Follow the same procedure by increasing the powers of 4 until there is some sort of cyclicity generated. This will give us the cyclicity of remainders. Then divide the given power by the cyclicity to find the remainder which will give us the required remainder.
Now 44 gives us the same remainder as 41, so the cyclicity is of 3 as the remainders start repeating themselves after 43. Cyclicity = 3 So, any power of 3 or a multiple of 3 will give a remainder of 1. So 4999 will give a remainder of 1. Thus, final remainder = (1 |
The product of two or more natural numbers has the same remainder when divided by any natural number n, as the remainder obtained when product of the individual remainders of the natural numbers is divided by n.
In other words, if x, y,… are
natural numbers, and the remainder of [(x
y
…)/n] is r, the remainder of (x/n) is
rx, the remainder of (y/n) is
ry, and so on…; then the remainder of [(rx
ry
…)/n] will also be equal to r.
For example: Find remainder of 323/14.
To solve this we will use the remainder theorem.
Now, 323 = 19
17
By remainder theorem, the remainder of 323/14 equals the remainder of the product of the remainders of 19/14 and 17/14 when divided by 14.
Remainder of 19/14 = 5
Remainder of 17/14 = 3
Remainder of the product of the remainders of 19/14 and 17/14 when divided by 14
= remainder of [(5
3)/14] = 1
This is the remainder when 323 is divided by 14.
|
The remainder when 2256 is divided by 17 is [CAT 2002]
(1) 7(2) 13 (3) 11(4) 1
Solution: 24 =
Hence, option 4. |
|
Find the remainder when 541001 is divided by 7?
Solution: One of the simplest ways to tackle these types of questions is to jointly use the Remainder Theorem and the cyclicity property of remainders. Now, the remainder when 541 is divided by 7 is 5.
Again, using remainder theorem, the remainder when
543 or (542
Similarly, the remainder when 544 or
(542
The remainder when 545 or (544
The remainder when 546 or (545
The remainder when 547 or (546
The remainder when 548 or (544
And so on… Thus, the cyclicity of 54 is 6. The remainder when 1001 is divided by 6 is 5. Since the remainder when 545 is divided by 7 is 3, hence the remainder when 541001 is divided by 7 is equal to 3. |
Remainder theorem gave rise to the concept of modulo operation.
The modulo operation finds the remainder of division of one number by another.
If a number x is divided by n which leaves a remainder y, then this can be represented in terms of mod operator as:
x mod n = y
Thus, 323 mod 14 = 1
Similarly, 19 mod 14 = 5
Thus, remainder theorem can be restated as
“the modulo of a number (x
y) is equal to the modulo of the product of the moduli of x and
y”.
i.e. xy mod n = [(x mod
n)
(y mod n)] mod n
- PROPERTIES OF THE MOD OPERATOR
Addition, subtraction, division and multiplication of two mod functions is possible.
For example:
19 mod 14 = 5 … (i)
17 mod 14 = 3 … (ii)
Adding (i) and (ii), we get,
36 mod 14 = 8, which is obviously true as 36/14 gives a remainder of 8
Subtracting (i) and (ii), we get,
2 mod 14 = 2, which is again true
Multiplying (i) and (ii), we get,
323 mod 14 = 15; and 15 mod 14 = 1, which is again true
Similarly the mod operator follows laws of indices. Thus we can raise it to any power.
|
Find the remainder when 2128 is divided by 17.
Solution:
Here instead of using the cyclicity concept, we use the mod operator concept.
Now, 16 mod 17 =
i.e. 24 mod 17 = Now, mod operator follows laws of indices:
Thus, remainder is 1 when 2128 is divided by 17. |
|
Let N = 1421 [CAT 2000]
(1) 0(2) 9 (3) 3(4) 6
Solution: N = 1421 = (1422 – 1)(1422 + 1)(1428 – 3) = (14222 – 12)(1428 – 3) Both 14222 and 1428 are divisible by 3 as well as 4. N = (14222 – 1)(1428 – 3) = X + 3, where X is divisible by 12 Thus, when N = 1421 Hence, option 3.
Alternatively, 1421 1425
= 315(mod 12) = 3(mod 12)
Hence, option 3. |
5(mod 12); 1423 Let p be a prime number and a
be a number that is co-prime to p. Then, the remainder obtained when
ap1
is divided by p is 1.
REMEMBER:
- This is just another form of writing Fermat’s Little Theorem, which we had covered in the Concept Builder of Number Systems.
There, we had mentioned that if p is prime and
a is any integer, then (ap – a) will be
perfectly divisible by p. This implies that [a (ap –
1 – 1)] is also perfectly divisible by p. Hence, either a
or (ap – 1 – 1) has to be divisible by it (
p is a prime number). Now, in Fermat’s remainder theorem, we assume
a to be co-prime to p, hence a cannot be divisible by it.
Therefore, (ap – 1 – 1) has to be divisible by p.
This obviously means that if ap – 1 is divided by p,
then the remainder will be 1.
|
What is the remainder when (2100 + 2) is divided by 101?
Solution: By Fermat’s remainder theorem, the remainder when 2100 is divided by 101 is 1. Also, the remainder when 2 is divided by 101 is 2.
Hence, the remainder when (2100 + 2) is divided by 101 is 3. |
Let f(n) be the number of integers less than n and co-prime with n, then the remainder obtained when m f(n) is divided by n is 1, where m and n are co-prime to each other.
We can see that f(2) = 1, f(3) = 2, f(4) = 2, f(5) = 4
For example, Find the remainder when 84 is divided by 5?
By Euler’s theorem, when 8f(5) = 4 is divided by 5 is 1. Similarly, the remainder obtained when any power of 8 divisible by 4 such as 84 or 812 and so on will give the same remainder when divided by 5.
REMEMBER:
- all natural numbers a and n
a remainder of a when n is odd
Here a, b and n are positive integers.
Rules for an
bn:
Always divisible by (a
b) for all odd and even n.
When n is even, then also divisible by (a + b).
When n is odd, it is divisible by (a + b) if (a + b) is a factor of 2bn.
For example, consider (63n
1), which is of the above form.
(a
b) is a factor of (an
bn) for even as well as odd n.
Hence, (63n – 1) is divisible by 62.
|
For all integers n > 0, 76n – 66n is divisible by [CAT 2002]
(1) 13(2) 127 (3) 559(4) All of these
Solution: Factorizing the given expression, (73n – 63n)(73n + 63n) i.e. (7n – 6n)(72n + 62n + 7n6n)(73n + 63n) ... (i)
Substitute n = 1 in equation (i), The three factors are 1, 127 and 559.
Since 559 is divisible by 13, hence 13 will also be a factor. Hence, option 4. |
|
[CAT 2005]
(1) 0 < R (3) 0.5 < R
Solution:
Hence, option 4. |
Rules for an + bn:
Divisible by (a + b) for all odd n.
When n is odd, it is divisible by
(a
b) if (a
b) is a factor of 2bn.
When n is even, it is divisible by (a + b) if (a + b) is a factor of 2bn.
|
The remainder, when (1523 + 2323) is divided by 19, is: [CAT 2004]
(1) 4(2) 15 (3) 0(4) 18
Solution: (1523 + 2323) is divisible by (15 + 23) ie, 38.
Hence, option 3. |
If a number n is divided successively by a and b which gives remainders of x and y respectively then it means that first the number is divided by a giving a remainder x and the quotient k obtained from this division is further divided by b to give remainder y.
This successive division process can continue up to any number of steps – until the quotient in a division becomes zero for the first time.
Thus quotient in first division is taken as the dividend in the second division; the quotient in the second division is taken as the dividend in the third division and so on.
Here we start from the end (reverse engineering); i.e. substitute the value of k in the first equation.
Thus, n = a
(b
m + y) + x
Thus, n = (a
b)
m + (a
y + x)
Thus, when the number is divided by the
product of successive divisors a and b, instead of a and
b individually, we get the remainder (a
y + x)
Similarly for 3 successive divisions of a number n with a, b, c giving remainders x, y, z and quotients k, m, s, we get the final remainder as
[(a
b)z + (a
y) + x] when divided by (a
b
c) instead of a, b and c
individually.
Looking carefully we see that this formula can be generalized for any number of successive divisions to find the remainders.
|
What is the remainder when 3326 is divided by 15 if the number on successive division by 3 and 5 leaves a remainder of 2 and 3 respectively? Solution: Starting from the end, we can see that the dividend for second division must be the quotient for the first division.
Thus, if k is the quotient of first division and m is quotient of second division, then, k = 5m + 3 and the original dividend 3326 = 3k + 2
Substituting the value of k, we get, 3326 = 3(5m + 3) + 2
Thus, if 3326 is divided by 15, then the remainder will be 11. |
|
When a natural number n is divided successively by 4, 5 and 7, it leaves remainders of 2, 3 and 6 respectively. Find the least possible value of n such that it is greater than or equal to 800.
Solution: Let the quotients when n is divided successively by 4, 5 and 7 be k, m and s respectively. Also, let the required unknown natural number (i.e. the dividend for the first division) be n. Then, the dividends for the second and third divisions will be k and m respectively.
Now, we have, n = 4k + 2 = 4(5m
+ 3) + 2( = 20m + 12 + 2 =
20(7s + 6) + 14( = 140s + 134 We need to find the smallest n which is greater than or equal to 800. Also, keep in mind that s being a quotient has to be a whole number. The value of n will be smallest when s
is as small as possible. So, the least value of n s = 5; i.e. n = 834. |
|
On dividing a number by 3, 4 and 7, the remainders are 2, 1 and 4 respectively. If the same number is divided by 84 then the remainder is [CAT 2002]
(1) 80(2) 76 (3) 53(4) None of these
Solution: Smallest number possible as per the given condition = [(4
Consider a number, N = 53 + (3
Hence, option 3. |
Let us take a simple number 104.
This is the same as (10
10
10
10). Here, 10 is said to be the base of the operation and 4 is called the
exponent.
In simple terms, exponents are nothing but the power to which a number is raised.
We can factorize any number in terms of its prime factors raised to some exponents. Thus, the exponent of any prime number p in any natural number n can be found by factorization.
However, if we are interested in finding the exponent of any prime number p in n!, then the following formula is used:
where, [a] is the largest integer
value that is 
a
In other words, if n is a natural number and p is a prime number, then the highest possible exponent of p (say x) such that n! is perfectly divisible by px is given by the above formula.
|
What is the highest power of 7 that can exactly divide 780! ?
Solution: The highest power of 7 that can exactly divide 780! is given by:
= 111 + 15 + 2 = 128
Hence, the highest power of 7 that can exactly divide 780! is 128. |
Composite numbers can be written either as the product of two prime numbers or as a prime number raised to some power.
Case 1: If the composite number is the product of two prime numbers and we want the highest power of this composite number in n!, then we can split this problem to finding the exponents of each of the prime numbers individually and taking minimum of the values.
For example, suppose that we want the maximum power of 15 in 500!. Then, first we need to find the exponents of 3 and 5 in 500! individually, using the above formula, and then take the minimum of the two values which will represent the exponent of 15 in 500!
Case 2: On the other hand, if the composite number is of the form (prime number)m and we want to find the maximum available exponent of this composite, then we will first find the exponent of this prime number and divide the value by m which will give the value of the exponent in n!
|
Find the exponent of 25 in 250!.
Solution: Here 25 is not a prime; thus we cannot use the above formula directly which is valid only for p being a prime.
However 25 = 52; so we will find the exponent of 5 in 250! And divide the exponent value by the power of 5 which is 2 here to get the exponent of 25.
Thus exponent of 5 = 50 + 10 + 2 = 62 Thus exponent of 25 in 250! = 62/2 = 31 |
|
What is the largest possible value of n such
that Solution: Now, 21 = 3 If 54! is to be exactly divisible by
21n, then it should also be divisible by (3 Thus, 54! should be exactly divisible by both 3n and 7n individually as well.
It is obvious that 54! will contain more multiples of 3 than of 7 (i.e. the exponent of 7 will be less than that of 3). Hence, it is the number of multiples of 7 present in 54! that will give us the largest value of n. Therefore,
= 7 + 1 = 8 This means that there are 8 multiples of 7 and is greater than or equal to 8 multiples of 3 in 54!. Since we need both a 3 and a 7 to form a 21, the limit on the number of multiples of 21 in 54! is set by the number of multiples of 7 present in it.
|
|
How many zeroes are present at the end of 43!?
Solution:
Now, 43! = 43 Every time a multiple of 5 is multiplied by an even number, we can add one 0 to the end of the number. Thus, the number of zeroes will depend entirely upon the number of multiples of 5 in the series (since the number of multiples of 2 will definitely be greater).
However, it should be taken care that 25 = 5 Thus, 43! contains 9 multiples of 5; hence it will have 9 zeroes trailing it.
Alternatively, If we find out the number of multiples of 5 present in 43!, then that will be equal to the number of zeroes trailing 43! (since the number of 2s in 43! will definitely be greater). Hence, we have,
= 8 + 1 = 9
Hence, 9 zeroes are present at the end of 43! |
- The greatest number that will divide a, b, c leaving
remainders x, y, z, respectively, is the HCF of (a
x), (b
y) and (c
z).
- The lowest number that is divisible by a, b and c leaving the same remainder r in each case is the LCM of (a, b and c).
|
Three friends, returning from a movie, stopped to eat at a restaurant. After dinner, they paid their bill and noticed a bowl of mints at the front counter. Sita took 1/3 of the mints, but returned four because she had a momentary pang of guilt. Fatima then took 1/4 of what was left but returned three for similar reasons. Eswari then took half of the remainder but threw two back into the bowl. The bowl had only 17 mints left when the raid was over. How many mints were originally in the bowl? [CAT 2001]
(1) 38(2) 31 (3) 41(4) None of these
Solution: Sita takes 1/3rd of the total mints which implies that the total number of mints in the bowl should be a multiple of 3. None of the options is a multiple of 3. Hence, option 4.
Alternatively, This problem can be best solved by working backwards. Number of mints before Eswari = (17 ( 2)
= 48
Hence, option 4. |
|
Let b be a positive integer and a =
b2 – b. If b [CAT 2001]
(1)15(2) 20 (3) 24(4) None of these
Solution: a2 – 2a = a(a – 2) Substituting a = b2 – b, we get, a2 – 2a = (b2 – b)[(b2 – b) – 2] = b(b – 1)(b2 – b – 2) = b(b – 1)(b – 2)( b + 1) = (b – 2)(b – 1)b(b + 1) This is a product of 4 consecutive positive integers which will definitely have a multiple of 2, 3 and 4.
Hence, option 3. |
|
Ashish is given Rs. 158 in one rupee denominations. He has been asked to allocate them into a number of bags such that any amount required between Re. 1 and Rs. 158 can be given by handing out a certain number of bags without opening them. What is the minimum number of bags required? [CAT 2001]
(1) 11(2) 12 (3) 13(4) None of these
Solution: To express any number with the least number of bags of coins, we need these bags of coins to consist of the number of coins as 20, 21, 22, 23, …, and the remaining coins should be put in one bag.
This takes care of 127 coins. There are 31 coins remaining. These 31 coins can be further put into bags each containing 1, 2, 4, 8, 16 coins.
Hence, option 2. |
