📚 Advanced Study Notes – Number System
(For UPSC EPFO – Quantitative Aptitude – MIT‑style, First Principles)
Why these notes?
The “Number System” section in the UPSC EPFO exam tests a candidate’s understanding of the underlying mathematics that form the backbone of all arithmetic and number‑theoretic problems. The questions range from simple rules of divisibility to problems involving modular arithmetic and binary representation.These notes start from the very foundations, prove the key properties rigorously, and then extend to more advanced concepts that often appear in higher‑level competitive exams. They are written in a clear, structured, and self‑contained manner, with edge cases, pitfalls, and a challenging problem at the end.
1. Foundations – The Building Blocks
| Symbol | Meaning | Example |
|---|---|---|
| ℤ | Set of all integers (…, −2, −1, 0, 1, 2, …) | n ∈ ℤ |
| ℕ | Natural numbers (positive integers, 1, 2, 3, …) | n ∈ ℕ |
| ℚ | Rational numbers (fractions) | p/q, q ≠ 0 |
| ℝ | Real numbers | √2, π, 1/3 |
| ℤ⁺ | Positive integers | 5 |
| ℤ⁻ | Negative integers | −3 |
1.1. The Ring ℤ
The set ℤ, equipped with two binary operations (+, ×), satisfies the ring axioms:
| Axiom | Statement | Proof Sketch |
|---|---|---|
| Associativity | (a + b) + c = a + (b + c) | Holds by definition of integer addition. |
| Commutativity | a + b = b + a, a × b = b × a | Follows from the commutativity of integer addition & multiplication. |
| Distributivity | a × (b + c) = a × b + a × c | Derived from the definition of multiplication as repeated addition. |
| Identity | 0 + a = a, 1 × a = a | 0 and 1 are the additive and multiplicative identities. |
| Inverses | a + (−a) = 0, a ≠ 0 ⇒ a × (1/a) = 1 | Inverses exist only for 0 (additive) and non‑zero integers (multiplicative). |
Why is this important?
The ring structure guarantees that the basic properties of addition and multiplication we use in arithmetic are mathematically sound. It also justifies the use of modular arithmetic and prime factorisation.
2. Prime Numbers & Fundamental Theorem of Arithmetic
2.1 Definition
- Prime: An integer (p > 1) with exactly two positive divisors: 1 and itself.
- Composite: An integer (n > 1) that is not prime (i.e., has a divisor other than 1 and n).
2.2 Fundamental Theorem of Arithmetic (FTA)
Statement: Every integer (n > 1) can be expressed uniquely as a product of primes, up to the order of the factors.
Proof Sketch (by induction):
- Base case: (n = 2) is prime.
- Assume the theorem holds for all integers < n.
- If n is prime, done.
- If n is composite, write (n = a \times b) with 1 < a, b < n.
- By induction, a and b have unique prime decompositions.
- Multiply these decompositions to obtain n’s decomposition.
- Uniqueness follows by the Euclid lemma (if p | ab and p prime, then p|a or p|b).
Edge Cases:
- (n = 1): Not prime or composite; it is the unit of ℤ.
- Negative integers: Their prime factorisation is the same as that of the absolute value; the sign is handled separately.
2.3 Euclid’s Lemma (Key to FTA)
Lemma: If a prime (p) divides a product (ab), then (p) divides at least one of (a) or (b).
Proof (modular): Assume (p \nmid a). Then (\gcd(a,p)=1). By Bézout’s identity, ∃ integers x, y such that (ax + py = 1). Multiply by (b): (abx + pby = b). Since (p | ab) and (p | pby), (p | b).
3. Divisibility Rules & GCD/LCM
3.1 Basic Divisibility Rules
| Divisible by | Condition | Example |
|---|---|---|
| 2 | Last digit even | 124 → 4 |
| 3 | Sum of digits divisible by 3 | 123 → 1+2+3=6 |
| 4 | Last two digits divisible by 4 | 236 → 36 |
| 5 | Last digit 0 or 5 | 145 → 5 |
| 6 | Divisible by 2 and 3 | 312 → even + sum divisible by 3 |
| 8 | Last three digits divisible by 8 | 1232 → 232 |