Olive Defence

CDS Mathematics

Number Theory

📐 Number Theory · MC13 CDS Elementary Mathematics

Number Theory in CDS covers the theoretical foundations of the Number System: the division algorithm, prime factorisation theorem, HCF/LCM methods, and logarithm applications. Much of this overlaps with MC01 — but Number Theory asks more conceptual, proof-adjacent questions rather than computation. A solid MC01 + this chapter gives complete arithmetic coverage.

📌 CDS exam focus: (1) Division algorithm: Dividend = Divisor × Quotient + Remainder; (2) Fundamental theorem of arithmetic — unique prime factorisation; (3) HCF/LCM — both methods, and the product relation; (4) Divisibility rules applied conceptually; (5) Logarithm theory — laws and table use; (6) Number of divisors, sum of divisors of a number.

Topics at a Glance

① Division Algorithm

D = d×q + r; 0 ≤ r < d

② Prime Factorisation

Unique representation; FTA

③ HCF & LCM Methods

Prime factorisation; Euclidean algorithm

④ Number of Divisors

Formula from prime factorisation

⑤ Logarithm Theory

Laws, number of digits, change of base

⑥ Divisibility Concepts

Theoretical proofs, even/odd results

1. Division Algorithm

1.1

The Euclidean Division Algorithm & Applications

Foundation for HCF computation and remainder problems

⚡ Division Algorithm

For any integers a (dividend) and b (divisor, b > 0): a = b × q + r where 0 ≤ r < b a = dividend b = divisor q = quotient r = remainder Given any two of {a, b, q, r}, find the fourth. Euclidean Algorithm for HCF: HCF(a, b): divide a by b, get remainder r₁ divide b by r₁, get r₂ continue until remainder = 0 Last non-zero remainder = HCF Example: HCF(48, 18): 48 = 18×2 + 12 18 = 12×1 + 6 12 = 6×2 + 0 → HCF = 6

2. Fundamental Theorem of Arithmetic

2.1

Unique Prime Factorisation & Its Applications

Every composite number has exactly one prime factorisation (order doesn't matter)

📐 Prime Factorisation

Every integer >1 is either prime or a unique product of primes
Example: 360 = 2³×3²×5
Use factor tree or division method
HCF = product of lowest powers of common primes
LCM = product of highest powers of all primes
HCF(a,b) × LCM(a,b) = a × b

📐 Number of Divisors Formula

If n = p₁ᵃ × p₂ᵇ × p₃ᶜ..., then:
Number of divisors = (a+1)(b+1)(c+1)...
Example: 360 = 2³×3²×5¹ → divisors = (3+1)(2+1)(1+1) = 4×3×2 = 24
Sum of divisors: (p₁⁰+p₁¹+...+p₁ᵃ)(p₂⁰+...)...
Perfect square: all exponents must be even
Number of divisors is odd ↔ n is a perfect square

3. HCF & LCM — Deep Dive

3.1

Both Methods Explained with CDS Applications

Word problems require identifying: is this an HCF problem or LCM problem?

⚡ HCF & LCM — Complete Methods

METHOD 1 — PRIME FACTORISATION: HCF: product of COMMON prime factors with LOWEST powers LCM: product of ALL prime factors with HIGHEST powers Example: HCF(12, 18, 24): 12 = 2²×3 18 = 2×3² 24 = 2³×3 HCF = 2¹×3¹ = 6 LCM = 2³×3² = 72 METHOD 2 — EUCLIDEAN ALGORITHM (HCF only): HCF(a,b): Repeatedly: a = bq+r; then a←b, b←r until r=0 GOLDEN RULE (for EXACTLY TWO numbers): HCF × LCM = Product of the two numbers APPLICATIONS: HCF: largest tile to cover a room; largest equal bundle; equal division LCM: events repeating together; smallest number divisible by all NUMBER WITH REMAINDER r WHEN DIVIDED BY a,b,c: Same remainder r: smallest = LCM(a,b,c) + r Different remainders, but (divisor − remainder) same = k: smallest = LCM(a,b,c) − k

4. Logarithm Theory

4.1

Log Laws, Number of Digits & Change of Base

Logarithm is in both MC01 (Number System) and MC13 (Number Theory)

⚡ Logarithm Laws — Complete Reference

DEFINITION: logₐ m = x ⟺ aˣ = m (a>0, a≠1, m>0) LAWS: log(mn) = log m + log n (Product rule) log(m/n) = log m − log n (Quotient rule) log(mⁿ) = n log m (Power rule) log_a(a) = 1 (log of base = 1) log_a(1) = 0 (log of 1 = 0) log_a(m) = log m / log a (Change of base) NUMBER OF DIGITS: Number of digits in N = ⌊log₁₀ N⌋ + 1 KEY VALUES (common log, base 10): log 2 ≈ 0.3010 log 3 ≈ 0.4771 log 5 = 1 − log 2 ≈ 0.6990 log 7 ≈ 0.8451 log 6 = log 2 + log 3 ≈ 0.7781

📋 TOPIC-WISE PYQ

Number Theory — CDS Questions

Q1. The HCF of two numbers is 12 and their LCM is 360. One number is 60. Find the other.

(a) 60 (b) 72 (c) 84 (d) 96

Answer: (b) 72
Other = HCF×LCM/given = 12×360/60 = 4320/60 = 72.

Q2. How many divisors does 360 have?

(a) 18 (b) 20 (c) 24 (d) 30

Answer: (c) 24
360=2³×3²×5¹. Divisors=(3+1)(2+1)(1+1)=4×3×2=24.

Q3. The least number which when divided by 4, 6, 8, 12 leaves a remainder 2 in each case is:

(a) 24 (b) 26 (c) 12 (d) 14

Answer: (b) 26
LCM(4,6,8,12)=24. Required number=24+2=26.

Q4. If log₂ 8 + log₄ 16 = x, find x.

(a) 5 (b) 6 (c) 7 (d) 8

Answer: (a) 5
log₂ 8=log₂ 2³=3. log₄ 16=log₄ 4²=2. x=3+2=5.

Q5. The number of digits in 2¹⁰ is: (log 2 = 0.3010)

(a) 3 (b) 4 (c) 5 (d) 6

Answer: (b) 4
log(2¹⁰)=10×0.3010=3.010. Digits=⌊3.010⌋+1=3+1=4.

🔥 TRICKY QUESTIONS

Number Theory — Classic CDS Traps

🧩 T1. Find the smallest number which when divided by 5, 6, 7, 8 leaves remainders 3, 4, 5, 6 respectively.

Solution: 839.
Divisor − remainder: 5−3=2, 6−4=2, 7−5=2, 8−6=2. Constant difference = 2.
LCM(5,6,7,8)=840. Required number=840−2=838. Check: 838÷5=167 rem 3 ✓, 838÷6=139 rem 4 ✓, 838÷7=119 rem 5 ✓, 838÷8=104 rem 6 ✓.

🧩 T2. Show that the product of three consecutive integers is always divisible by 6.

Solution: Among any 3 consecutive integers, one is divisible by 3 and at least one by 2.
Let the integers be n, n+1, n+2. Their product = n(n+1)(n+2).
Divisible by 2: among any 3 consecutive integers, at least one is even.
Divisible by 3: among any 3 consecutive integers, exactly one is divisible by 3.
Since 2 and 3 are coprime, product is divisible by 2×3=6.

🧩 T3. If log₃ 2 = x, express log₁₂ 96 in terms of x.

Solution: (5x+1)/(2x+1)... let me derive.
log₁₂ 96 = log 96/log 12. log 96=log(2⁵×3)=5log2+log3. log12=log(4×3)=2log2+log3.
If log₃2=x: log2=x·log3. So: (5x·log3+log3)/(2x·log3+log3)=log3(5x+1)/log3(2x+1)=(5x+1)/(2x+1).

📐 Formula Sheet — MC13

Division Algorithm

a = bq + r; 0 ≤ r < b
Given any 3 of {a,b,q,r}, find fourth
Euclidean: HCF via repeated division

HCF & LCM

HCF: lowest powers of common primes
LCM: highest powers of all primes
HCF×LCM=A×B (only 2 numbers)

Number of Divisors

n=p₁ᵃ·p₂ᵇ·p₃ᶜ
Divisors=(a+1)(b+1)(c+1)
Odd count of divisors → perfect square

Logarithm Laws

log(mn)=log m+log n
log(m/n)=log m−log n
log(mⁿ)=n log m
Digits=⌊log N⌋+1

⚡ Quick Revision Booster — MC13

Division Algorithm

D = d×q + r
r is always < d
Euclidean: repeatedly divide

HCF / LCM

HCF×LCM=A×B
LCM always ≥ HCF
HCF divides LCM

Divisors Count

n=2³×3²: (3+1)(2+1)=12
Perfect square → odd # of divisors

Log Values

log2≈0.3010; log3≈0.4771
log5=1−log2≈0.6990
Digits=⌊log N⌋+1

Remainder Problems

Same rem r: LCM+r
Diff−rem constant k: LCM−k

🚨 Traps

HCF×LCM=product only for 2 numbers
1 has exactly 1 divisor; not prime
log(a+b) ≠ log a + log b

✏️ PRACTICE EXERCISE

Test Yourself — MC13

E1. Find HCF and LCM of 36, 48, and 72 using prime factorisation.

(a) HCF=12, LCM=144 (b) HCF=12, LCM=288 (c) HCF=6, LCM=144 (d) HCF=12, LCM=216

💡 36=2²×3²; 48=2⁴×3; 72=2³×3². HCF=lowest powers; LCM=highest powers.

E2. How many divisors does 2⁴×3³×5² have?

(a) 9 (b) 24 (c) 36 (d) 60

💡 (4+1)(3+1)(2+1)=5×4×3.

E3. If log 2=0.3010 and log 3=0.4771, find log 24.

(a) 1.3801 (b) 1.2810 (c) 1.3810 (d) 1.4771

💡 log24=log(8×3)=3log2+log3.

E4. Find the least number that leaves remainder 5 when divided by 8, 10, and 12.

(a) 115 (b) 120 (c) 125 (d) 245

💡 LCM(8,10,12), then add 5.

E5. What is the number of digits in 3²⁰? (log 3 = 0.4771)

(a) 8 (b) 9 (c) 10 (d) 11

💡 log(3²⁰)=20×0.4771. Digits=⌊result⌋+1.

📝 Mock Tests 🎯 Subject Quizzes ✈️ Telegram