Episode 8 — Aptitude and Reasoning / 8.6 — Number System
8.6.a Number System -- Concepts and Formulas
1. Classification of Numbers
Understanding the hierarchy of numbers is essential. Here is how different sets of numbers relate to each other.
Venn Diagram (Text Representation)
+---------------------------------------------------------------+
| REAL NUMBERS |
| |
| +---------------------------------------------------+ |
| | RATIONAL NUMBERS | |
| | | |
| | +-------------------------------------------+ | |
| | | INTEGERS | | |
| | | | | |
| | | +-----------------------------------+ | | |
| | | | WHOLE NUMBERS | | | |
| | | | | | | |
| | | | +---------------------------+ | | | |
| | | | | NATURAL NUMBERS | | | | |
| | | | | {1, 2, 3, 4, ...} | | | | |
| | | | +---------------------------+ | | | |
| | | | | | | |
| | | | + {0} | | | |
| | | +-----------------------------------+ | | |
| | | | | |
| | | + {..., -3, -2, -1} | | |
| | +-------------------------------------------+ | |
| | | |
| | + Fractions and terminating/repeating decimals | |
| | (1/2, 0.75, 0.333..., -2/7, etc.) | |
| +---------------------------------------------------+ |
| |
| + IRRATIONAL NUMBERS |
| (sqrt(2), sqrt(3), pi, e, non-repeating decimals) |
+---------------------------------------------------------------+
1.1 Natural Numbers
The counting numbers starting from 1.
N = {1, 2, 3, 4, 5, 6, ...}
- Smallest natural number: 1
- There is no largest natural number (the set is infinite).
1.2 Whole Numbers
Natural numbers plus zero.
W = {0, 1, 2, 3, 4, 5, ...}
- Smallest whole number: 0
- Every natural number is a whole number, but 0 is a whole number and NOT a natural number.
1.3 Integers
Whole numbers plus negative numbers.
Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}
- Integers include positive integers, negative integers, and zero.
- Zero is neither positive nor negative.
1.4 Rational Numbers
Any number that can be expressed as p/q, where p and q are integers and q is not equal to 0.
Q = { p/q | p, q are integers, q != 0 }
Examples:
3/4 = 0.75 (terminating decimal)
1/3 = 0.3333... (repeating decimal)
-7/2 = -3.5 (terminating decimal)
5 = 5/1 (every integer is rational)
Key property: Every rational number, when expressed as a decimal, either terminates or repeats.
1.5 Irrational Numbers
Numbers that CANNOT be expressed as p/q. Their decimal expansion is non-terminating and non-repeating.
Examples:
sqrt(2) = 1.41421356... (never terminates, never repeats)
sqrt(3) = 1.73205080...
pi = 3.14159265...
e = 2.71828182...
Key property: The square root of any non-perfect-square natural number is irrational.
sqrt(2), sqrt(3), sqrt(5), sqrt(6), sqrt(7), sqrt(8), sqrt(10), ... --> all irrational
sqrt(4) = 2, sqrt(9) = 3, sqrt(16) = 4 --> rational (perfect squares)
1.6 Real Numbers
The union of rational and irrational numbers. Every point on the number line is a real number.
R = Q ∪ Q' (where Q' is the set of irrational numbers)
2. Prime Numbers and Composite Numbers
2.1 Prime Numbers
A number greater than 1 that has exactly two distinct factors: 1 and itself.
Prime numbers up to 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97
Total prime numbers up to 100: 25
Important facts:
- 2 is the only even prime number.
- 1 is neither prime nor composite.
- Every prime number greater than 3 can be expressed as
6k + 1or6k - 1(but not every number of that form is prime).
2.2 Composite Numbers
A number greater than 1 that has more than two factors.
Examples: 4, 6, 8, 9, 10, 12, 14, 15, ...
4 --> factors: 1, 2, 4 (3 factors)
12 --> factors: 1, 2, 3, 4, 6, 12 (6 factors)
- The smallest composite number is 4.
- Every composite number can be expressed as a product of primes (Fundamental Theorem of Arithmetic).
2.3 Co-prime Numbers (Relatively Prime)
Two numbers are co-prime if their HCF (GCD) is 1. They share no common factor other than 1.
Examples of co-prime pairs:
(8, 15) --> HCF = 1 (co-prime)
(14, 25) --> HCF = 1 (co-prime)
(12, 18) --> HCF = 6 (NOT co-prime)
Key facts:
- Two consecutive numbers are always co-prime: (n, n+1).
- Two prime numbers are always co-prime: (3, 7), (11, 13).
- Co-prime numbers need not be prime themselves: (8, 15) are co-prime but neither is prime.
2.4 Twin Primes
Pairs of primes that differ by 2.
(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)
3. Even and Odd Numbers
3.1 Definitions
Even number: divisible by 2 --> ..., -4, -2, 0, 2, 4, 6, 8, ...
Odd number: not divisible by 2 --> ..., -3, -1, 1, 3, 5, 7, 9, ...
Note: 0 is an even number.
3.2 Properties of Even and Odd Numbers
Addition / Subtraction:
Even + Even = Even e.g., 4 + 6 = 10
Odd + Odd = Even e.g., 3 + 5 = 8
Even + Odd = Odd e.g., 4 + 3 = 7
Multiplication:
Even x Even = Even e.g., 4 x 6 = 24
Odd x Odd = Odd e.g., 3 x 5 = 15
Even x Odd = Even e.g., 4 x 3 = 12
Key takeaway for multiplication: If ANY factor is even, the product is even. The product of numbers is odd ONLY if ALL factors are odd.
4. Divisibility Rules
Divisibility rules let you check if a number is divisible by another without performing full division.
4.1 Divisibility by 2
A number is divisible by 2 if its last digit is 0, 2, 4, 6, or 8.
Example: 4,578 --> last digit is 8 (even) --> divisible by 2
Example: 3,271 --> last digit is 1 (odd) --> NOT divisible by 2
4.2 Divisibility by 3
A number is divisible by 3 if the sum of its digits is divisible by 3.
Example: 8,241 --> 8 + 2 + 4 + 1 = 15 --> 15/3 = 5 --> divisible by 3
Example: 5,174 --> 5 + 1 + 7 + 4 = 17 --> 17/3 = 5 remainder 2 --> NOT divisible by 3
4.3 Divisibility by 4
A number is divisible by 4 if its last two digits form a number divisible by 4.
Example: 7,324 --> last two digits = 24 --> 24/4 = 6 --> divisible by 4
Example: 8,135 --> last two digits = 35 --> 35/4 = 8 remainder 3 --> NOT divisible by 4
4.4 Divisibility by 5
A number is divisible by 5 if its last digit is 0 or 5.
Example: 6,230 --> last digit = 0 --> divisible by 5
Example: 4,785 --> last digit = 5 --> divisible by 5
4.5 Divisibility by 6
A number is divisible by 6 if it is divisible by both 2 and 3.
Example: 4,326 --> last digit = 6 (even, so divisible by 2)
--> 4 + 3 + 2 + 6 = 15 (divisible by 3)
--> divisible by 6
4.6 Divisibility by 7
Method: Double the last digit and subtract from the remaining number. If the result is divisible by 7, the original is too.
Example: 371
Step 1: Last digit = 1, double it = 2
Step 2: Remaining number = 37
Step 3: 37 - 2 = 35
Step 4: 35 / 7 = 5 --> divisible by 7
Example: 905
Step 1: Last digit = 5, double it = 10
Step 2: Remaining number = 90
Step 3: 90 - 10 = 80
Step 4: 80 / 7 = 11 remainder 3 --> NOT divisible by 7
4.7 Divisibility by 8
A number is divisible by 8 if its last three digits form a number divisible by 8.
Example: 53,104 --> last three digits = 104 --> 104/8 = 13 --> divisible by 8
Example: 41,230 --> last three digits = 230 --> 230/8 = 28.75 --> NOT divisible by 8
4.8 Divisibility by 9
A number is divisible by 9 if the sum of its digits is divisible by 9.
Example: 8,127 --> 8 + 1 + 2 + 7 = 18 --> 18/9 = 2 --> divisible by 9
Example: 5,234 --> 5 + 2 + 3 + 4 = 14 --> 14/9 = 1 remainder 5 --> NOT divisible by 9
4.9 Divisibility by 10
A number is divisible by 10 if its last digit is 0.
Example: 7,350 --> last digit = 0 --> divisible by 10
4.10 Divisibility by 11
A number is divisible by 11 if the difference between the sum of digits at odd positions and the sum of digits at even positions is 0 or a multiple of 11.
Example: 85,294
Positions (from left): 8(1st) 5(2nd) 2(3rd) 9(4th) 4(5th)
Sum of odd-position digits = 8 + 2 + 4 = 14
Sum of even-position digits = 5 + 9 = 14
Difference = 14 - 14 = 0 --> divisible by 11
Example: 76,341
Sum of odd-position digits = 7 + 3 + 1 = 11
Sum of even-position digits = 6 + 4 = 10
Difference = 11 - 10 = 1 --> NOT divisible by 11
Summary Table
| Divisor | Rule |
|---|---|
| 2 | Last digit is even (0, 2, 4, 6, 8) |
| 3 | Sum of digits divisible by 3 |
| 4 | Last 2 digits divisible by 4 |
| 5 | Last digit is 0 or 5 |
| 6 | Divisible by both 2 and 3 |
| 7 | Double last digit, subtract from rest; check if result is divisible by 7 |
| 8 | Last 3 digits divisible by 8 |
| 9 | Sum of digits divisible by 9 |
| 10 | Last digit is 0 |
| 11 | (Sum of odd-place digits) - (Sum of even-place digits) = 0 or multiple of 11 |
5. Factors and Multiples
5.1 Definition
- Factor (Divisor): A number
ais a factor ofbifb / aleaves no remainder. - Multiple: A number
bis a multiple ofaifb = a x kfor some integerk.
Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
Multiples of 6: 6, 12, 18, 24, 30, 36, ...
5.2 Prime Factorization
Every composite number can be expressed as a product of prime factors. This is the Fundamental Theorem of Arithmetic.
Example: Find the prime factorization of 360.
360 = 2 x 180
= 2 x 2 x 90
= 2 x 2 x 2 x 45
= 2 x 2 x 2 x 3 x 15
= 2 x 2 x 2 x 3 x 3 x 5
360 = 2^3 x 3^2 x 5^1
5.3 Number of Factors Formula
If a number N has the prime factorization:
N = p1^a x p2^b x p3^c x ...
Then the total number of factors of N is:
Number of factors = (a + 1)(b + 1)(c + 1) ...
Example:
360 = 2^3 x 3^2 x 5^1
Number of factors = (3+1)(2+1)(1+1)
= 4 x 3 x 2
= 24
So 360 has 24 factors.
5.4 Sum of Factors Formula
Sum of factors = [(p1^(a+1) - 1)/(p1 - 1)] x [(p2^(b+1) - 1)/(p2 - 1)] x ...
Example:
N = 360 = 2^3 x 3^2 x 5^1
Sum of factors = [(2^4 - 1)/(2 - 1)] x [(3^3 - 1)/(3 - 1)] x [(5^2 - 1)/(5 - 1)]
= [(16 - 1)/1] x [(27 - 1)/2] x [(25 - 1)/4]
= 15 x 13 x 6
= 1170
5.5 Product of All Factors
Product of all factors of N = N^(d/2)
where d = total number of factors
Example:
N = 12, factors = {1, 2, 3, 4, 6, 12}, d = 6
Product = 12^(6/2) = 12^3 = 1728
Verification: 1 x 2 x 3 x 4 x 6 x 12 = 1728 ✓
5.6 Number of Even and Odd Factors
For N = 2^a x p2^b x p3^c x ... (where p2, p3, ... are odd primes):
Number of odd factors = (b+1)(c+1)... [ignore the power of 2]
Number of even factors = Total factors - Odd factors
= a x (b+1)(c+1)...
Example:
360 = 2^3 x 3^2 x 5^1
Odd factors = (2+1)(1+1) = 3 x 2 = 6
Even factors = 24 - 6 = 18
The 6 odd factors: 1, 3, 5, 9, 15, 45
5.7 Perfect Squares and Number of Factors
A number is a perfect square if all exponents in its prime factorization are even.
Key property: A perfect square always has an odd number of factors.
36 = 2^2 x 3^2
Number of factors = (2+1)(2+1) = 9 (odd)
Factors: 1, 2, 3, 4, 6, 9, 12, 18, 36
Conversely, a non-perfect-square always has an even number of factors.
6. Place Value and Face Value
6.1 Face Value
The face value of a digit is the digit itself, regardless of its position.
In the number 5,832:
Face value of 5 = 5
Face value of 8 = 8
Face value of 3 = 3
Face value of 2 = 2
6.2 Place Value
The place value of a digit depends on its position in the number.
In the number 5,832:
Place value of 5 = 5 x 1000 = 5000
Place value of 8 = 8 x 100 = 800
Place value of 3 = 3 x 10 = 30
Place value of 2 = 2 x 1 = 2
6.3 Key Difference
In the number 4,073:
Face value of 7 = 7
Place value of 7 = 70
Difference = 70 - 7 = 63
7. Unit Digit Patterns (Cyclicity)
The unit digit of powers follows a repeating cycle. This is crucial for finding the unit digit of large powers.
7.1 Unit Digit Cycles
Digit | Cycle of unit digits (for powers 1, 2, 3, 4, ...) | Cycle length
------+-----------------------------------------------------+--------------
0 | 0, 0, 0, 0, ... | 1
1 | 1, 1, 1, 1, ... | 1
2 | 2, 4, 8, 6, 2, 4, 8, 6, ... | 4
3 | 3, 9, 7, 1, 3, 9, 7, 1, ... | 4
4 | 4, 6, 4, 6, ... | 2
5 | 5, 5, 5, 5, ... | 1
6 | 6, 6, 6, 6, ... | 1
7 | 7, 9, 3, 1, 7, 9, 3, 1, ... | 4
8 | 8, 4, 2, 6, 8, 4, 2, 6, ... | 4
9 | 9, 1, 9, 1, ... | 2
7.2 How to Find the Unit Digit of a^n
Step 1: Look at the unit digit of a.
Step 2: Find the cycle length for that digit.
Step 3: Find the remainder when n is divided by the cycle length.
Step 4: The unit digit corresponds to that position in the cycle.
(If remainder = 0, take the LAST digit in the cycle.)
Example: Find the unit digit of 7^253
Step 1: Unit digit of 7 is 7.
Step 2: Cycle of 7: {7, 9, 3, 1}, cycle length = 4.
Step 3: 253 / 4 = 63 remainder 1.
Step 4: 1st position in cycle = 7.
Unit digit of 7^253 = 7
Example: Find the unit digit of 3^84
Step 1: Unit digit of 3 is 3.
Step 2: Cycle of 3: {3, 9, 7, 1}, cycle length = 4.
Step 3: 84 / 4 = 21 remainder 0.
Step 4: Remainder 0 --> take the LAST in cycle = 1.
Unit digit of 3^84 = 1
8. Remainder Theorems
8.1 Basic Remainder Concept
Dividend = Divisor x Quotient + Remainder
a = bq + r where 0 <= r < b
8.2 Properties of Remainders
Property 1: Remainder of (a + b) / n = [Rem(a/n) + Rem(b/n)] mod n
Property 2: Remainder of (a - b) / n = [Rem(a/n) - Rem(b/n)] mod n
Property 3: Remainder of (a x b) / n = [Rem(a/n) x Rem(b/n)] mod n
Property 4: Remainder of (a^k) / n = [Rem(a/n)]^k mod n
Example: Remainder when 47 x 53 is divided by 7
Rem(47/7) = 5 (47 = 7 x 6 + 5)
Rem(53/7) = 4 (53 = 7 x 7 + 4)
Rem(47 x 53 / 7) = Rem(5 x 4 / 7) = Rem(20 / 7) = 6
8.3 Fermat's Little Theorem
If p is a prime and a is not divisible by p, then:
a^(p-1) mod p = 1
Example: Remainder when 2^50 is divided by 7
By Fermat's theorem: 2^6 mod 7 = 1 (since 7 is prime, p-1 = 6)
2^50 = 2^(6x8) x 2^2 = (2^6)^8 x 4
Remainder = 1^8 x 4 = 4
So remainder of 2^50 / 7 = 4
8.4 Euler's Theorem
If a and n are co-prime, then:
a^phi(n) mod n = 1
where phi(n) = Euler's totient function
= n x (1 - 1/p1) x (1 - 1/p2) x (1 - 1/p3) x ...
(p1, p2, p3 are the distinct prime factors of n)
Example: Find phi(12)
12 = 2^2 x 3^1
phi(12) = 12 x (1 - 1/2) x (1 - 1/3)
= 12 x 1/2 x 2/3
= 4
The 4 numbers less than 12 and co-prime to 12: {1, 5, 7, 11}
8.5 Wilson's Theorem
If p is a prime number, then:
(p - 1)! mod p = p - 1
Equivalently: (p - 1)! + 1 is divisible by p
Example:
p = 5: (5-1)! = 24, and 24 mod 5 = 4 = (5-1) ✓
p = 7: (7-1)! = 720, and 720 mod 7 = 6 = (7-1) ✓
9. Important Number Properties and Formulas
9.1 Sum of First n Natural Numbers
Sum = n(n + 1) / 2
Example: Sum of first 100 natural numbers = 100 x 101 / 2 = 5050
9.2 Sum of Squares of First n Natural Numbers
Sum = n(n + 1)(2n + 1) / 6
Example: Sum of squares of first 10 = 10 x 11 x 21 / 6 = 385
9.3 Sum of Cubes of First n Natural Numbers
Sum = [n(n + 1) / 2]^2
Note: The sum of cubes equals the square of the sum of first n natural numbers.
9.4 Number of Primes (Approximation)
The number of primes less than or equal to N is approximately:
pi(N) ≈ N / ln(N)
9.5 Divisor Function Summary
Let N = p1^a1 x p2^a2 x ... x pk^ak
Number of factors: d(N) = (a1+1)(a2+1)...(ak+1)
Sum of factors: sigma(N) = product of [(pi^(ai+1) - 1)/(pi - 1)]
Number of ways to express
N as product of 2 factors: d(N)/2 if N is not a perfect square
(d(N)+1)/2 if N is a perfect square
10. Special Numbers
10.1 Perfect Numbers
A number is perfect if the sum of its proper divisors (excluding itself) equals the number.
6: 1 + 2 + 3 = 6 ✓
28: 1 + 2 + 4 + 7 + 14 = 28 ✓
496, 8128 are the next perfect numbers.
10.2 Amicable Numbers
Two numbers are amicable if the sum of proper divisors of each equals the other.
220 and 284:
Sum of proper divisors of 220 = 284
Sum of proper divisors of 284 = 220
10.3 Armstrong Numbers (Narcissistic Numbers)
An n-digit number is an Armstrong number if the sum of its digits each raised to the nth power equals the number itself.
153 = 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153 ✓
370 = 3^3 + 7^3 + 0^3 = 27 + 343 + 0 = 370 ✓
371 = 3^3 + 7^3 + 1^3 = 27 + 343 + 1 = 371 ✓
11. Counting Formulas
11.1 Numbers in a Range
Count of integers from a to b (inclusive) = b - a + 1
Example: How many integers from 15 to 85?
Answer: 85 - 15 + 1 = 71
11.2 Even/Odd Numbers in a Range
Even numbers from 1 to n:
If n is even: n/2
If n is odd: (n-1)/2
Odd numbers from 1 to n:
If n is even: n/2
If n is odd: (n+1)/2
11.3 Numbers Divisible by k in a Range
Count of multiples of k from 1 to n = floor(n / k)
Count of multiples of k from a to b = floor(b/k) - floor((a-1)/k)
Example: How many multiples of 7 from 1 to 100?
floor(100 / 7) = 14
12. Concept of Highest Power of a Prime in n!
To find the highest power of a prime p that divides n!:
Highest power = floor(n/p) + floor(n/p^2) + floor(n/p^3) + ...
(continue until p^k > n)
Example: Highest power of 3 in 100!
floor(100/3) = 33
floor(100/9) = 11
floor(100/27) = 3
floor(100/81) = 1
Total = 33 + 11 + 3 + 1 = 48
So 3^48 divides 100! but 3^49 does not.
Example: Number of trailing zeros in 100!
Trailing zeros come from factors of 10 = 2 x 5. Since factors of 2 are always more than factors of 5, count the highest power of 5.
floor(100/5) = 20
floor(100/25) = 4
floor(100/125) = 0
Trailing zeros = 20 + 4 = 24
Summary
| Concept | Key Formula |
|---|---|
| Number of factors | (a+1)(b+1)(c+1)... |
| Sum of factors | Product of [(p^(a+1)-1)/(p-1)] |
| Product of factors | N^(d/2) |
| Even factors | a(b+1)(c+1)... |
| Odd factors | (b+1)(c+1)... |
| Unit digit of a^n | Use cyclicity (cycle length 1, 2, or 4) |
| Remainder of (axb)/n | [Rem(a/n) x Rem(b/n)] mod n |
| Fermat's little theorem | a^(p-1) mod p = 1 |
| Euler's theorem | a^phi(n) mod n = 1 |
| Trailing zeros in n! | Sum of floor(n/5^k) |
| Highest power of p in n! | Sum of floor(n/p^k) |
| Sum of 1 to n | n(n+1)/2 |
| Sum of squares | n(n+1)(2n+1)/6 |
| Sum of cubes | [n(n+1)/2]^2 |