Village Development Officer /Quantitative Aptitude

Number system

Arithmetic · free study notes

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

  1. Transitivity: If (a|b) and (b|c) then (a|c).
  2. Unit divisibility: ±1 divides all integers.
  3. Zero divisibility: (a|0) for any (a\neq0).
  4. 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

  1. Addition/Subtraction: If (a\equiv b) and (c\equiv d) (mod m), then (a+c \equiv b+d), (a-c \equiv b-d).
  2. Multiplication: (a\equiv b) and (c\equiv d) ⇒ (ac \equiv bd).
  3. Exponentiation: If (a \equiv b) (mod m), then (a^k \equiv b^k).
  4. Fermat’s Little Theorem: If (p) is prime and (p∤a), then (a^{p-1} \equiv 1 \pmod p).
  5. 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

  1. Euclid’s Theorem: Infinitely many primes.
  2. Prime Number Theorem: (\pi(x) \sim \frac{x}{\log x}).
  3. 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

Your note

Page 1

Doubt hai is topic me?

Free AI teacher se poocho — 24/7, step by step.