🔢

Divisibility & Primes

Divisibility rules, prime numbers, GCD, LCM, and the fundamental theorem of arithmetic

Key Concepts
  • Every integer > 1 has a unique prime factorisation
  • GCD and LCM are computed from the prime factorisation
  • The Euclidean algorithm finds the GCD quickly
  • The number of divisors comes from the exponents in the factorisation
Important Formulae
GCD–LCM relation gcd(a,b) × lcm(a,b) = a × b
Number of divisors n = p₁^a · p₂^b ⇒ d(n) = (a+1)(b+1)…
Sum of divisors σ(n) = Π (pᵢ^(aᵢ+1) − 1)/(pᵢ − 1)
Quick Tips
  • To test if n is prime, check divisibility only up to √n.
  • Factor first — most divisibility problems collapse once n is factorised.
Sample Practice Questions

  1. Is 1 a prime number?

    • Yes
    • No
    • Sometimes
    • It depends
    Show answer

    Answer: No

  2. d(n) denotes the number of divisors. For which n is d(n) = 2?

    • n = 1
    • n = 4
    • All primes
    • All even numbers
    Show answer

    Answer: All primes

  3. The remainder when 7^100 is divided by 6 is:

    • 0
    • 1
    • 5
    • 7
    Show answer

    Answer: 1

  4. How many prime numbers are even?

    • 0
    • 1 (only 2)
    • Infinitely many
    • Finite but more than 1
    Show answer

    Answer: 1 (only 2)

Practise more questions →
Practice Questions

Practise PRMO questions on Divisibility & Primes. Answers are revealed after each question.

Start Practice →
Number Theory