Numbers and Sequences: Euclid, Primes, AP and GP
Euclid and primes
Euclid’s division lemma says that for positive integers a and b there exist unique integers q and r with a=bq+r and 0≤r<b. Repeated division gives HCF: divide, replace (a,b) by (b,r), stop when r=0; the last nonzero divisor is HCF. The fundamental theorem of arithmetic says every integer >1 has a unique prime factorisation apart from order. Modular arithmetic writes a≡b (mod n) when n divides a−b; use it for remainders and digit problems.
Sequences
An arithmetic progression (AP) has aₙ=a+(n−1)d and Sₙ=n/2[2a+(n−1)d]. A geometric progression (GP) has aₙ=arⁿ⁻¹ and Sₙ=a(rⁿ−1)/(r−1), r≠1. A series is the sum of a sequence.
Worked example
Find HCF(252,105). 252=105×2+42; 105=42×2+21; 42=21×2+0. Last nonzero remainder is 21, so HCF=21. Check: 252=2²×3²×7 and 105=3×5×7; common factors 3×7=21.
Traps
Using r=b instead of 0≤r<b; stopping at the first remainder; confusing HCF with LCM; applying AP formulas to a GP; and forgetting that a GP is valid only when r≠1 in the sum formula. For three terms in AP, use a−d, a, a+d; for GP, use a/r, a, ar.