Number Systems

Filter
Theory

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.

Theory
Real and Complex Numbers
  • 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 and Irrational 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.

Integers, Natural Numbers and Whole Numbers
  • Integers are numbers that can be written without their fractional component. Whole numbers are non-negative integers. Natural Numbers are positive integers. Set of integers = {. . . -3, -2, -1, 0, 1, 2, . . . }. Set of Whole Numbers = {0, 1, 2, 3 . . } and Natural Numbers = {1, 2, 3 . . . }
Prime and Composite Numbers
  • 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.

Theory

Prime numbers

How to check if a number is prime
  • To check if n is a prime number lets take the list of all prime factors less than or equal to $$\sqrt{n}$$ rounded up. (i.e. 2, 3, . . .). If none of the prime factors can divide n then n is a prime number. Important fact to remember: there are 25 prime numbers less than 100.
Properties of Prime numbers
  • 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.

Quick Recap
  • 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

Solved Example

Prime Numbers

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.

Formula Questions
Divisibility by 2, 4, 8, 16
  • 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.

Divisibility by 3, 9, 27
  • 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.

Divisibility by 7
  • Remove the last digit, double it and subtract it from the truncated original number. For example: 1638, 163-16=147 is divisible by 7 hence 1638 is divisible by 7. This process should be repeated for larger numbers.
Divisibility by 11
  • Take sum of all even digits and subtract it from the sum of all odd digits. If the difference is a multiple of 11 the original number will be a multiple of 11. Example 23452 (sum odd = 2+4+2=8 sum even=3+5=8) difference=8-8=0 is divisible by 11 hence 23452 is divisible by 11.
Divisibility properties
  • 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.

Quick Recap
  • 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

Solved Example

Divisibility Rules

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.

Theory
Base System

Converting a number from decimal to a different base

  • To convert a number from decimal to base b, repeatedly divide the number with b. The remainder becomes the rightmost digit of the converted number and the quotient is divided again by b. For example to convert 1342 to base 3, the steps are as follows: 1342/3= Quot=447 Rem=1. Dividing 447/3 = Quot=149 Rem=0. Dividing 149/3= Quot 49 Rem=2, Dividing 49/3= Quot 16 Rem=1. Dividing 16/3 = Quot 5 Rem 1. Dividing 5/3= Quot 1 Rem=2. Hence the converted number is 1211201.

Converting a number from a different base to decimal

  • To convert a number from base b to decimal, multiply each number with the corresponding power of b and sum it up. Hence, to convert 1211201 from base 3 to decimal, converted number = $$1*3^0$$ + $$0*3^1$$ + $$2*3^2$$ + $$1*3^3$$ + $$1*3^4$$ + $$2*3^5$$ + $$1*3^6$$ = 1 + 0 + 18 + 27 + 81 + 486 + 729 = 1342.

Remainders applied to numbers in different bases

  • 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. For example 1211201 written in base 3. The sum of the digits = 8 is divisible by 2. Hence $$1211201_3$$=$$1342_{10}$$ is divisible by 2.

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.


Solved Example

Base Systems

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.

Formula Questions

Cyclicity

  • 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:

    1. Find the cyclicity of a, say it is x

    2. Find the remainder when n is divided by x, say remainder r

    3. 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.

Solved Example

Factors and Cyclicity

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

Formula Questions
  • 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).

  • LCM of fractions = LCM of Numerators รท HCF of Denominators.
Theory
How to find LCM and HCF
  • 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.

Properties of LCM, HCF
  • 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

Solved Example

HCF and LCM

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.

Formula Questions
Remainder Theorem
  • 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.

Euler's theorem
  • If M and N are co-prime to each other then remainder when $$M ^ {\phi (N)} $$ is divided by N is 1.
Solved Example

Remainder Theorems

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

Formula Questions

Factors

Number of factors
  • 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.

Number of even and odd factors
  • 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,

    1. Then the number of even factors of N = p (1+q) (1+r) . . .

    2. 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

Sum of factors
  • 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

Formula Questions
Highest power of a number in a Factorial
  • 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.

Formula Questions
Recap of Formulae
  • 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

Shortcuts

Sum of all permutations of n-digits

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)

Formula Questions

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)$$

Formula Questions

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

      Formula

      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

      Formula Questions

      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

      cracku

      Boost your Prep!

      Download App