Primality
A prime number has exactly two distinct positive divisors: 1 and itself. By that definition 1 is not prime (only one divisor) and 2 is the smallest prime — and the only even prime, because every other even number is divisible by 2 and so has at least three divisors. To test whether N is prime you do NOT need to try every smaller number. If N had two factors both greater than √N their product would exceed N, so at least one factor of any composite N is ≤ √N. The √N test: check divisibility only by primes up to √N. For 113, √113 ≈ 10.6, so test 2, 3, 5, 7 — none divide it, so 113 is prime. Knowing all 25 primes below 100 by heart saves precious seconds in CAT, and the √N idea generalises to counting primes in a range.
✅ 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 |