Rajasthan Police Sub‑Inspector (SI) – Quantitative Aptitude
Topic: Number System
Level: Advanced / MIT‑style
Goal: Master the fundamentals of number systems, understand their properties from first principles, and solve challenging problems that test edge cases and deeper theory.
1. Preliminaries
| Symbol | Meaning | Example |
|---|---|---|
| ℕ | Set of positive integers (1, 2, 3, …) | ℕ = {1,2,3,…} |
| ℤ | Set of integers (…, −2, −1, 0, 1, 2, …) | ℤ = … |
| ℚ | Set of rational numbers | 1/2, 3/4 |
| ℝ | Set of real numbers | 1.5, π |
| ℂ | Set of complex numbers | 3 + 4i |
| ℤₙ | Ring of integers modulo n | ℤ₃ = {0,1,2} |
Why study number systems?
• They are the language of all quantitative reasoning.
• Many aptitude problems hinge on number‑theoretic properties.
• Understanding modular arithmetic, prime factorizations, and base conversions sharpens logical thinking.
2. Positional Number Systems
A positional system represents a number as a sum of digits times powers of a base (b) (usually an integer (b \ge 2)).
2.1 Formal Definition
For a base (b) and a digit string (d_k d_{k-1}\dots d_1 d_0) where each (d_i \in {0,1,\dots,b-1}),
[ N = \sum_{i=0}^{k} d_i , b^i . ]
The value of the most significant digit is (d_k b^k); the least significant digit is (d_0 b^0 = d_0).
2.2 Converting Between Bases
Integer to Base (b) (repeated division)
- Divide (N) by (b).
- Record the remainder (r).
- Replace (N) by the quotient.
- Repeat until (N=0).
- The base‑(b) representation is the remainders read in reverse.
Base (b) to Integer (evaluation)
[ N = \sum_{i=0}^{k} d_i,b^i . ]
Edge Cases
- Zero: Always represented as
0in any base. - Negative Numbers: Use two’s complement for binary or sign–magnitude for decimal.
- Non‑integer Bases: Allowed (e.g., base (\sqrt{2})) but rarely used in aptitude.
2.3 Properties
| Property | Explanation | Example |
|---|---|---|
| Least Significant Digit (LSD) | Determines divisibility by the base. | In base 10, a number ends in 5 → divisible by 5. |
| Parity | The LSD in base 2 gives the parity (even/odd). | 1101₂ ends in 1 → odd. |
| Sum of Digits Rule | For base (b), sum of digits mod ((b-1)) equals the number mod ((b-1)). | (123_{10}) → (1+2+3=6); (123 \mod 9 = 6). |
| Divisibility by (b-1) | A number divisible by (b-1) iff the sum of its digits is divisible by (b-1). | (123_{10}) divisible by 9? Sum=6 → No. |
3. Modular Arithmetic
Modular arithmetic (congruence) is indispensable for number‑system problems.
3.1 Basic Definitions
- (a \equiv b \pmod{m}) iff (m) divides (a-b).
- The set of residue classes modulo (m) is (\mathbb{Z}_m = {0,1,\dots,m-1}).
3.2 Key Theorems
| Theorem | Statement | Usage |
|---|---|---|
| Chinese Remainder Theorem (CRT) | If (m_1, m_2, \dots, m_k) are pairwise coprime, the system (x \equiv a_i \pmod{m_i}) has a unique solution modulo (M=m_1m_2\dots m_k). | Solving simultaneous congruences. |
| Fermat’s Little Theorem (FLT) | If (p) prime and (p\nmid a), then (a^{p-1}\equiv1\pmod p). | Simplifying large exponents. |
| Euler’s Theorem | If (\gcd(a,n)=1), then (a^{\phi(n)} \equiv 1 \pmod n). | Generalization of FLT. |
| Wilson’s Theorem | For prime (p), ((p-1)! \equiv -1 \pmod p). | Checking primality. |
3.3 Practical Tricks
-
Divisibility Checks
- By 3 or 9: Sum of digits.
- By 11: Alternating sum of digits.
- By 8: Last three digits.
- By 7: Double the last digit, subtract from the remaining truncated number, repeat.
-
Modular Exponentiation
Use repeated squaring to compute (a^b \bmod m) efficiently.
Example: (3^{100} \bmod 13). -
Finding Multiplicative Inverses
Solve (ax \equiv 1 \pmod m) using the extended Euclidean algorithm.
4. Prime Numbers & Factorization
4.1 Prime Basics
- A prime (p) is an integer (>1) with no positive divisors other than 1 and (p).
- Fundamental Theorem of Arithmetic: Every integer (n>1) can be written uniquely (up to order) as a product of primes.
4.2 Divisibility and Least Prime Factors
- Sieve of Eratosthenes: Efficiently generate all primes up to (N).
- Least Prime Factor (LPF): For any composite (n), (LPF(n)) ≤ (\sqrt{n}).
- Edge Case: For (n