Login
Register
- Mocks
- Previous Papers
- Learn
- Practice
- Colleges
- Courses
- Enroll To CAT 2024
- Offers
- Other Exams
- Blogs
- Adda
Number Systems is the most important topic in the quantitative section. It is a very vast topic and a significant number of questions appear in CAT every year from this section. Learning simple tricks like divisibility rules, HCF and LCM, prime number and remainder theorems can help improve the score drastically. This segment is all about learning short cuts. Due to the sheer size of the topic syllabus, many students never feel very comfortable with Number Systems. The key here is to perform well on a relative scale and improve your percentile.
Real Numbers represent values along a continuous number line extending in both positive and negative directions to infinity. They have a natural ordering. The set of real numbers is the superset of all rational and irrational numbers, integers and fractions. Examples are 4, -1, 1/4, $$\sqrt{2}$$.
Complex Numbers are of the form x+iy where x and y are real numbers and i is the imaginary unit that equals $$\sqrt{-1}$$. They have no natural ordering. Examples are 2+i3, 1-i6, 9+i$$\sqrt{2}$$.
If a continuous line R represents the set of real numbers, the plane with R as the X axis (and a Y-axis representing the imaginary part of the number) represents the set of Complex numbers.
Rational number is a number that can also be written as a fraction - that is it can be expressed as the ratio of two whole numbers. It is the superset of all integers and fractions, whole numbers and natural numbers. Examples are 3, 0, -1, 7/6, 34235/354.
Irrational numbers are numbers that cannot be written as the fraction of whole numbers. Examples are $$\pi$$, $$\sqrt{7 }$$, 2+$$\sqrt{3}$$/2.
Prime numbers are numbers with only two factors- 1 and the number itself. A prime number is not divisible by any number other than 1 and itself. Examples are 2, 3, 5, 7.
Composite numbers are numbers with more than 2 factors. Examples are 4, 6, 8, 9. 0 and 1 are neither composite nor prime.
There are exactly 2 factors of a prime number: 1 and the number itself
There are infinitely many number of prime numbers
Fermat's theorem: For any integer a and prime number p, $$a^p-a$$ is always divisible by p. Hence, $$a^p$$ mod p = a mod p. Also, if a is not divisible by p then $$a^{p-1}$$ mod p= 1 mod p.
Wilson's theorem: According to Wilson's theorem a number n is prime if and only if (n-1)! mod n = -1 mod n. For example, consider the prime number 7. Hence, the remainder when 6! is divided by 7 is -1 i.e. 6.
Only one triplet of prime numbers exists such that x, x+2 and x+4 are prime and that is 3, 5 and 7.
Fermats Theorem: If p is a prime number, $$a^p-a$$ mod p = 0
If a and p are co-primes then $$a^{p-1}$$ mod p= 1 mod p
Wilson's Theorem: If n is prime (n-1)! mod n = -1 mod n
Question 1: What is the remainder when 10! is divided by 11?
Solution: By Wilson's theorem the remainder is -1 i.e. 11-1=10. Hence, remainder = 10
Question 2: What is the remainder when $$24^{13}$$ is divided by 7?
Solution: By Fermat's theorem as 24 and 7 are co-primes, remainder of $$24^6$$ mod 7 =1. Hence, $$24^{13}$$ can be split up as $$24^{6}$$ * $$24^{6}$$ * 24 mod 7 = 1*1*3 mod 7 =3. Hence, remainder is 3.
Question 3: If a number is chosen at random from 1 to 100, what is the probability that it would be prime?
Solution: There are 25 prime numbers in the range 1-100. Hence, probability = 25/100 =0.25.
A number is divisible by 2 if the last digit of the number is divisible by 2 i.e. last digit is 0, 2, 4, 6 or 8
A number is divisible by 4 if the last two digits of the number are divisible by 4. For eg. 1348 is divisible by 4 because 48 is divisible by 4.
A number is divisible by 8 if the last three digits of the number are divisible by 8. For eg. 21348 is not divisible by 8 because 348 is not divisible by 8.
A number is divisible by 16 if the last four digits of the number are divisible by 16. For eg. 1,134,224 is divisible by 16 because 4224 is divisible by 16.
A number is divisible by 3 if the sum of all digits of the number are divisible by 3. Hence 729 (sum of digits = 7+2+9=18) is divisible by 3
A number is divisible by 9 if the sum of all digits of the number are divisible by 9. Hence 62172 (sum of digits = 6+2+1+7+2=18) is divisible by 9.
A number is divisible by 27 if the sum of blocks of 3 from left to right are divisible by 27. Hence 134433 (sum of blocks = 134+433=567) is divisible by 27.
For composite divisors, check if the number is divisible by the factors individually. Hence to check if a number is divisible by 6 it must be divisible by 2 and 3.
The equation $$a^n-b^n$$ is always divisible by a-b. If n is even it is divisible by a+b. If n is odd it is not divisible by a+b.
The equation $$a^n+b^n$$ is never divisible by a-b. If n is odd it is divisible by a+b. If n is even it is not divisible by a+b.
Divisibility by 2: Last digit divisible by 2
Divisibility by 4: Last two digits divisible by 4
Divisibility by 8: Last three digits divisible by 8
Divisibility by 16: Last four digit divisible by 16
Divisibility by 3: Sum of digits divisible by 3
Divisibility by 9: Sum of digits divisible by 9
Divisibility by 27: Sum of blocks of 3 (taken right to left) divisible by 27
Divisibility by 7: Remove the last digit, double it and subtract it from the truncated original number. Check if number is divisible by 7
Divisibility by 11: (sum of odd digits) - (sum of even digits) should be 0 or divisible by 11
Question 1: A number 24X34 is divisible by 9. Find X?
Solution: If the number is divisible by 9 then the sum of the digits must be divisible by 9. Hence 2+4+X+3+4=13+X is divisible by 9. As 0<=X<=9, X=5.
Question 2: A number 4574X is divisible by 11. Find X?
Solution: The number would be divisible by 11 if difference of sum of alternate digits is divisible by 11. Hence, (4+7+X)-(5+4)=X+2. As 0<=X<=9, X must be 9 for X+2 to be divisible by 11. Hence, X=9.
Question 3: What is the remainder when $$6^9+7^9$$ is divided by 13?
Solution: $$a^n+b^n$$ is divisible by a+b when n is odd. Hence, $$6^9+7^9$$ is divisible by (6+7)=13. Hence, remainder=0.
Converting a number from decimal to a different base
Converting a number from a different base to decimal
Remainders applied to numbers in different bases
Quick Recap
Converting from decimal to base b. Let $$R_1$$, $$R_2$$ . . . be the remainders left after repeatedly dividing the number with b. Hence, the number in base b is given by $$ . . . R_2R_1$$.
Converting from base b to decimal - multiply each digit of the number with a power of b starting with the rightmost digit and $$b^0$$.
A decimal number in divisible by b-1 only if the sum of the digits of the number when written in base b are divisible by b-1.
Question 1: Find X where $$356_{7}$$ + $$2134_{7}$$=$$X_{10}$$.
Solution: 356+2134 in base 7 = $$2523_7$$ ( here for last digit 6+4 = 10 = 7+3. So, carry over 1 and last digit is 3. Similarly, for second last digit 5+3+1 = 9. So carry over 1 and second-last digit is 2). Converting this to base 10, we get = 3_7^0 +2_7^1 +5_7^2 +2_7^3 = 3 + 14 + 245 + 686 = 948. Hence X=948.
Question 2: 2464X24 is a number in base 8 which when represented in decimal format is divisible by 7. What is X?
Solution: If the number is divisible by 7 in decimal format then the sum of the digits must be divisible by 7. Hence, 2+4+6+4+X+2+4 = 22+X is divisible by 7. Hence X=6.
To find the last digit of $$a^n$$ find the cyclicity of a. For eg. if a=2, we see that
$$2^1 = 2$$
$$2^2 = 4$$
$$2^3 = 8$$
$$2^4 = 16$$
$$2^5 = 32$$
Hence, the last digit of 2 repeats after every 4 th power. Hence cyclicity of 2 =4. Hence if we have to find the last digit of $$a^n$$, the steps are:
Find the cyclicity of a, say it is x
Find the remainder when n is divided by x, say remainder r
Find $$a^{r}$$ if r>0 and $$a^{x}$$ when r=0
For example, find the last digit of $$4^{102}$$ * $$6^{39}$$
The cyclicity of 4 is as follows:
$$4^1 = 4$$
$$4^2 = 16$$
$$4^3 = 64$$
Hence, cyclicity of 4 is 2 and of 6 is 1. Last digit of $$4^{102}$$ is 6 and that of $$6^{39}$$ is 6. Thus 6*6 would give 6 as the last digit.
Question 1: What are the number of factors in 1020?
Solution: 1020 can be represented as the product of prime factors as 1020 = $$2^2$$ * 3 * 5 * 17
Hence, number of factors = (2+1) (1+1) (1+1) (1+1) =3 * 2 * 2 * 2 =24
Question 2: What are the number of even factors in 2880?
Solution: 2880 can be represented as the product of prime factors as follows: 2880 = $$2^6 * 3^2 * 5$$
Hence number of even factors = 6 * (2+1) * (1+1) = 6*3*2 = 36
Question 3: What are the number of factors in 2880 that are divisible by 10?
Solution: 2880 can be represented as the product of prime factors as follows: 2880 = 2^6 * 3^2 * 5
Hence, for the factor to be a multiple of 10, 2 and 5 must come at least once.
Number of factors divisible by 10 = 6*(2+1)*1 = 18
Question 4: What is the highest power of 5 in 200!?
Solution: Highest power of 5 in 200! = 40 + 8 + 1=49
HCF * LCM of two numbers = Product of two numbers
The greatest number dividing a, b and c leaving remainders of $$x_1$$, $$x_2$$ and $$x_3$$ is the HCF of (a-$$x_1$$), (b-$$x_2$$) and (c-$$x_3$$).
The greatest number dividing a, b and c (a<b<c) leaving the same remainder each time is the HCF of (c-b), (c-a), (b-a).
To find the LCM or HCF of a set of numbers, first represent them as the product of prime factors. While calculating LCM, find the highest exponent for each prime factor among the numbers. The LCM is the product of the prime factors raised to the highest exponent.
For example to find the LCM of 720, 140 and 64, we factorize each number 720 = $$2^4$$ * $$3^2$$ * 5, 140 = $$2^2$$ * 5 * 7, 64 = $$2^6$$
Hence, the highest exponent of each prime factor is as follows: 2 is 6, 3 is 2, 5 is 1 and 7 is 1. Hence LCM = $$2^6$$ * $$3^2$$ * 5 * 7 = 20160.
While calculating HCF, find the lowest exponent for each prime factor among the numbers. The HCF is the product of the prime factors raised to the lowest exponent.
Hence for the 3 numbers the lowest exponent are as follows: 2 is 2, 3 is 0, 5 is 0 and 7 is 0. Hence the HCF = 4.
HCF * LCM of two numbers = Product of two numbers
Hence, if the two numbers are 180 and 320, the HCF=20. LCM = (180*320)/20= 2880.
The greatest number dividing a, b and c leaving remainders of $$x_1$$, $$x_2$$ and $$x_3$$ is the HCF of (a-$$x_1$$), (b-$$x_2$$) and (c-$$x_3$$). For example if a number divides 51, 128, 298 and leaves 3, 8 and 10 as the remainders then the largest number to do so would be the HCF of (48, 120, 288) = 24.
The greatest number dividing a, b and c (a<b<c) leaving the same remainder each time is the HCF of (c-b), (c-a), (b-a). For example the largest number to divide 102, 141 and 258 is the HCF of (258-102, 258-141, 141-102)=HCF of ( 156, 117, 39) = 39
If a number, N, is divisible by X and Y and HCF(X,Y) = 1. Then, N is divisible by X*Y
Question 1: Ajay, Vijay and Alay run on a circular track of 800m at 0.4m/s, 0.5m/s and 0.8m/s. If the start at the same time, how many times will they meet by the time Alay finishes 10 rounds of the track?
Solution: The time taken to finish one round of the track is 2000s, 1600s and 1000s respectively. Hence, they meet every x seconds where x=LCM(2000, 1600, 1000) = 8000s. Hence, by the time Alay completes 10 rounds in 10,000s, they would have met exactly once.
Question 2: A number x leaves the same remainder when it divides 20, 50 and 62. Find the maximum possible value of x?
Solution: The greatest number to leave the same remainder is HCF of (62-20, 62-50, 50-20) =HCF(42, 12, 30) = 6. Hence max value of x=6.
Question 3: The HCF of 24 and a is 8 and the LCM is 48. Find a?
Solution: HCF*LCM = 24*a = 8*48. Hence, a=16.
If a, b, c are the prime factors of N such that N= $$a^p$$ * $$b^q$$ * $$c^r$$
then the number of numbers less than N and co-prime to N $$ \phi (N) $$= N (1-1/a) (1 - 1/b) (1 - 1/c). This function is known as the Euler's totient function.
Question 1: Find the remainder when $$4^{102}$$ is divided by 21?
The Euler's totient function of 21 = 21 (1-1/3) (1 - 1/7) = 12 Hence remainder($$4^{12}$$ / 21)=1. Hence, $$4 ^ {102}$$ can be represented as $$4^{12*8}$$ * $$4^6$$. Hence remainder = 1 * remainder (4^6 /21 ) = remainder (2^12) / 21 = 1
To find the number of factors of a number, convert the number into the product of its prime factors. Prime factors of a number are the divisors that are prime numbers. Hence 720 can be represented as
720 = 16 * 9 * 5 = $$2^4$$ * $$3^2$$ * 5
The individual factors of 720 can be constructed by taking 2 0 times, 1 time, 2 times . . 4 times = 5 ways
Similarly 3 can be taken 0 times, 1 time or 2 times = 3 ways
Similarly 5 can be taken 0 times or 1 time= 2 ways
Hence the number of factors of 720 are = number of combinations of factors = (4+1) * (2+1) * (1+1) = 5*3*2=30.
In general if the number can be represented as N = $$a^{p}$$ ∗ $$b^{q}$$ ∗ $$c^{r}$$ . . . then number of factors is (p+1) * (q+1) * (r+1) . . .
If the number of factors are odd then N is a perfect square.
If there are n factors, then the number of pairs of factors would be n/2. If N is a perfect square then number of pairs (including the square root) is (n+1)/2.
To get even factors of 720, we must take 2 as a factor at least once.
Hence 2 can be taken 1 time, 2 times, 3 times, 4 times = 4 ways
If the number can be expressed as N = $$2^{p}$$ ∗ $$a^{q}$$ ∗ $$b^{r}$$ . . . where the power of 2 is p,
Then the number of even factors of N = p (1+q) (1+r) . . .
The number of odd factors of N = (1+q) (1+r) . . .
Hence the number of even factors of 720 (as shown above) = 4 * (2+1) * (1+1) =4 * 3 * 2 = 24
Hence the number of odd factors of 720 (as shown above) = (2+1) * (1+1) = 3 * 2 = 6
If the number can be represented as N = $$a^{p}$$ \∗ $$b^{r}$$ \∗ $$c^{q}$$ . . .
Then sum of factors is
$$\frac{a^{p+1} -1}{a-1}$$ * $$\frac{b^{q+1} -1}{b-1}$$ * $$\frac{c^{r+1} -1}{c-1}$$ . . .
Hence sum of factors of 720 = $$\frac{2^{5} -1}{2-1}$$ * $$\frac{3^{2+1} -1}{3-1}$$ * $$\frac{5^{1+1} -1}{5-1}$$ = 31 * 13 * 6 = 2418
The factorial of n is represented as n! = 1 * 2 * 3 . . . * (n-1) n
The highest power of a number p in a factorial n! if p is prime:
Lets take the example of highest power of 5 in 30!
To find the highest power of 5 in 30, find the number of multiples of 5 in 30 + find the number of multiples of 25 in 30 + so on
Hence, highest power of 5 in 30= 6+1 = 7
In general, highest power of p in n is sum = number of multiples of p + number of multiples of $$p^2$$ + number of multiples of $$p^3$$ and so on.
The highest power of a number c in a factorial n! if c is composite:
If c is a composite, find its highest prime factor. The power of the composite in n! is the same as the power of its highest prime factor. Hence the highest power of 21 in 100! is the highest power of 7 in 100!. Hence, highest power of 7 in 100! = 14+2=16. Hence the highest power of 21 in 100! is 16.
If N = $$a^{p}$$ ∗ $$b^{q}$$ ∗ $$c^{r}$$ . . . then number of factors is (p+1)(q+1)(r+1) . . .
If the number of factors are odd then N is a perfect square.
If there are n factors, then the number of pairs of factors would be n/2. If N is a perfect square then number of pairs (including the square root) is (n+1)/2.
If the number can be expressed as N = $$2^{p}$$ ∗ $$a^{q}$$ ∗ $$b^{r}$$ . . . where the power of 2 is p,
Then the number of even factors of N = p (1+q) (1+r) . . .
The number of odd factors of N = (1+q) (1+r) . . .
If the number can be represented as N = $$a^{p}$$ ∗ $$b^{q}$$ ∗ $$c^{r}$$ . . .
Then sum of factors is
$$\frac{a^{p+1} -1}{a-1}$$ * $$\frac{b^{q+1} -1}{b-1}$$ * $$\frac{c^{r+1} -1}{c-1}$$ . . .
In general, highest power of a prime p in n is sum = number of multiples of p + number of multiples of $$p^2$$ + number of multiples of $$p^3$$ and so on
If all possible permutations of n distinct digits are added together the sum is given by (n-1)! * (sum of n digits) * (11111... n times)
Number of trailing zeros of n! in base b(b=$$p^m$$, where p is a prime number) is for $$k\ge1$$ $$\frac{1}{m}\left(\Sigma\left[\frac{n}{p^k}\right]\ \right)$$
Properties of Remainders
1. The value of remainders can be from 0 to d-1, where d is the divisor. For example, 24 divided by 5 has a remainder of 4, and when any number is divided by 5, the remainder can be from 0 to 4.
2. If N < d, the given number is less than the divisor, then the remainder will be equal to N. For ex, if 5 is divided by 7, the remainder will be 5.
3. (M + N) mod d = (M mod d + N mod d) Mod d
4. (M - N) mod d = (M mod d - N mod d) Mod d
5. (M x N) mod d = (M mod d X N mod d ) Mod d
Chinese Remainder Theorem: When a divisor can be split into two co-prime factors a and b such that N = a x b , then by dividing the given number M with individual factors such that remainder in each case is p and q that is M mod a = p and M mod b = q and two variables are introduced and an equation is formed such that ax+by = 1, it is important to note that x and y can only take integral values. So after finding the individual remainders of M when divided by factors a and b, this equation is solved to get integral values of x and y.
Thus, the Chinese remainder states that
M mod N = (aqx+ bpy) mod N
Where a and b are factors of divisors and are co-prime
p and q are individual remainders when M is divided by a and b
M mod a = p and M mod b = q
x and y are integers that satisfy the equation ax+by = 1
Fermat's Theorem - For any integer $$a$$ and prime number $$p$$, $$a^p-a$$ is always divisible by $$p$$
Wilson's Theorem - For a prime $$p$$, remainder when $$(p-1)!$$ i divided by $$p$$ is $$(p-1)$$
Euler's Theorem - If M and N are co-prime to each other then the remainder when $$M^{\phi(N)}$$ is divided by N is 1
