Prime Factorization
Prime factorisation writes a number as a product of primes raised to powers: N = p₁^a × p₂^b × …. By the Fundamental Theorem of Arithmetic this form is unique (ignoring order), and it is the master key to most Number System problems. Once you have it, the number of factors is (a+1)(b+1)(c+1)…, because each prime can appear 0 up to its full power independently. The sum of factors multiplies the geometric series for each prime, ∏ (p^(e+1) − 1)/(p − 1). HCF takes the lowest power of each shared prime; LCM takes the highest power of every prime that appears. The highest power of a prime p dividing N! is found by Legendre’s rule — add ⌊N/p⌋ + ⌊N/p²⌋ + …. CAT loves "how many factors / even factors / factors that are perfect squares" — all answered straight from the exponents.
✅ Solved examples
✏️ Practice — try these, take hints as needed
📝 Topic test — 8 questions
Auto-graded with full solutions; saved to your dashboard. Use the calculator and formula sheet (top-right) any time.
Formula Reference Sheet
Primality & factorisation
| Primality test | N is prime if no prime ≤ √N divides N |
|---|---|
| Standard form | N = p₁^a × p₂^b × p₃^c × … |
| Number of factors | (a+1)(b+1)(c+1)… |
| Sum of factors | ∏ (p^(e+1) − 1)/(p − 1) |
| Product of factors | N^(d/2), d = number of factors |
Co-primes & totient
| Euler’s totient | φ(N) = N × ∏ (1 − 1/p) |
|---|---|
| φ of a prime | φ(p) = p − 1 |
| φ of prime power | φ(p^k) = p^k − p^(k−1) |
| Co-prime test | a, b co-prime ⇔ HCF(a, b) = 1 |
| Multiplicativity | φ(mn) = φ(m)φ(n) if HCF(m, n) = 1 |