Village Development Officer – Quantitative Aptitude
Topic: Number System
Objective – Build a deep, first‑principles understanding of the number system, its properties, and how to apply them to solve problems efficiently.
Target audience – Students preparing for competitive exams (VDO, UPSC, NTA, etc.) who need a solid mathematical foundation.
1. Foundations: Types of Numbers
| Symbol | Meaning | Properties | Example |
|---|---|---|---|
| ℤ | Integers (…, –3, –2, –1, 0, 1, 2, 3, …) | Closed under addition, subtraction, multiplication; not closed under division. | 5 – 7 = –2 |
| ℕ | Natural numbers (1, 2, 3, …) – (0 is often excluded) | Closed under addition, multiplication; not closed under subtraction. | 4 + 5 = 9 |
| ℚ | Rational numbers (p/q, q ≠ 0) | Closed under +, –, ×, ÷. | 1/2 + 1/3 = 5/6 |
| ℝ | Real numbers | All limits of Cauchy sequences of rationals. | √2, π |
| ℂ | Complex numbers (a + bi, i² = –1) | Closed under +, –, ×, ÷; every non‑zero has a multiplicative inverse. | (1+2i)(3–i) = 5+5i |
NT – Number Theory concepts (divisibility, primes, congruences) depend on ℤ.
2. Divisibility – The Core of Number Theory
2.1 Definition
An integer (a) is divisible by an integer (b\neq 0) if there exists an integer (k) such that (a = bk). We write (b|a).
2.2 Basic Properties
- Transitivity: If (a|b) and (b|c) then (a|c).
- Unit divisibility: ±1 divides all integers.
- Zero divisibility: (a|0) for any (a\neq0).
- Prime factorization: Every integer (n>1) can be written uniquely (up to order) as (n = \pm p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}) with distinct primes (p_i).
2.3 Divisibility Tests (Elementary)
- By 2: Last digit even.
- By 3: Sum of digits divisible by 3.
- By 9: Sum of digits divisible by 9.
- By 5: Last digit 0 or 5.
- By 6: Divisible by 2 and 3.
- By 11: Alternating sum of digits divisible by 11.
Edge Cases:
Zero: 0 is divisible by any non‑zero number.
Negative numbers: Divisibility is independent of sign; (b|a) iff (|b||a|).
3. Congruences – Working Modulo (m)
3.1 Definition
(a \equiv b \pmod m) iff (m) divides (a-b).
3.2 Basic Theorems
- Addition/Subtraction: If (a\equiv b) and (c\equiv d) (mod m), then (a+c \equiv b+d), (a-c \equiv b-d).
- Multiplication: (a\equiv b) and (c\equiv d) ⇒ (ac \equiv bd).
- Exponentiation: If (a \equiv b) (mod m), then (a^k \equiv b^k).
- Fermat’s Little Theorem: If (p) is prime and (p∤a), then (a^{p-1} \equiv 1 \pmod p).
- Euler’s Theorem: If (\gcd(a,m)=1), then (a^{\phi(m)} \equiv 1 \pmod m), where (\phi) is Euler’s totient.
3.3 Solving Linear Congruences
Equation (ax \equiv b \pmod m)
- If (\gcd(a,m)=d) divides (b), then there are (d) solutions modulo (m).
- Reduce: divide by (d) → (a' x \equiv b' \pmod{m'}) with (\gcd(a', m')=1).
- Find inverse of (a') modulo (m') using Extended Euclidean Algorithm (EEA).
3.4 Chinese Remainder Theorem (CRT)
If moduli (m_i) are pairwise coprime, then the system
[ x \equiv a_i \pmod{m_i}\quad (i=1,\dots,k) ]
has a unique solution modulo (M = \prod m_i). Construct:
[ x = \sum a_i \cdot M_i \cdot y_i \pmod{M}, ] where (M_i = M/m_i) and (y_i) is the inverse of (M_i) modulo (m_i).
Edge Cases:
Non‑coprime moduli: No unique solution; need consistency checks.
4. Prime Numbers – The Building Blocks
4.1 Definition & Distribution
- Prime: integer (p>1) with only divisors 1 and (p).
- Fundamental Theorem of Arithmetic: Unique factorization.
4.2 Key Results
- Euclid’s Theorem: Infinitely many primes.
- Prime Number Theorem: (\pi(x) \sim \frac{x}{\log x}).
- Bertrand’s Postulate: For (n>1), exists prime (p) with (n < p < 2n).
4.3 Testing Primality (Elementary)
- Trial division up to (\sqrt{n}).
- Sieve of Eratosthenes: Efficient for generating all primes up to (N).
4.4 Applications
- **LC