Number Theory: GCD, LCM & Divisibility for JEE Main

Number theory questions in JEE Main are compact, formula-light, and frequently appear in the integer-answer section where partial marks are unavailable. GCD, LCM, divisibility tests, and modular arithmetic are the recurring themes. Students who know the efficient methods — Euclidean algorithm, prime factorisation shortcuts — answer these in 60 seconds; others spend four minutes on trial division. This guide gives you the efficient methods.

GCD and the Euclidean Algorithm

GCD(a, b) = greatest common divisor = the largest integer dividing both a and b. Euclidean algorithm: GCD(a, b) = GCD(b, a mod b) (applied repeatedly until the remainder is 0). Example: GCD(252, 198). 252 = 1×198 + 54. 198 = 3×54 + 36. 54 = 1×36 + 18. 36 = 2×18 + 0. GCD = 18. This is always faster than prime factorisation for large numbers. LCM(a, b) = a × b / GCD(a, b). For three numbers: GCD(a, b, c) = GCD(GCD(a, b), c); LCM(a, b, c) = LCM(LCM(a, b), c).

Properties: GCD(a, b) × LCM(a, b) = a × b (for two numbers only — does not generalise to three). GCD(a+kb, b) = GCD(a, b) for any integer k. GCD is distributive over LCM and vice versa: GCD(a, LCM(b, c)) = LCM(GCD(a, b), GCD(a, c)). JEE question: "If GCD(a, b) = 12 and LCM(a, b) = 360, find all possible pairs (a, b)." a × b = 12 × 360 = 4320. Both a and b must be multiples of 12: a = 12m, b = 12n where GCD(m, n) = 1 and mn = 30. Factor pairs of 30 with GCD = 1: (1,30), (2,15), (3,10), (5,6). Pairs: (12,360), (24,180), (36,120), (60,72). Take a free number theory mock. See our number systems guide.

Divisibility Rules and Tests

Divisibility by 2: last digit even. By 3: sum of digits divisible by 3. By 4: last two digits divisible by 4. By 5: last digit 0 or 5. By 6: divisible by both 2 and 3. By 7: no simple decimal rule — subtract twice the last digit from the remaining truncated number; if the result is divisible by 7, original is too. By 8: last three digits divisible by 8. By 9: sum of digits divisible by 9. By 11: (sum of digits at odd positions) − (sum of digits at even positions) divisible by 11. By 25: last two digits divisible by 25. JEE uses these in: "how many 4-digit numbers divisible by both 6 and 7 exist?" (divisible by 42 — find count in 1000–9999 range: ⌊9999/42⌋ − ⌊999/42⌋ = 238 − 23 = 215).

Modular Arithmetic in JEE Questions

a ≡ b (mod m) means m | (a − b). Properties: (a + b) mod m = ((a mod m) + (b mod m)) mod m. (ab) mod m = ((a mod m)(b mod m)) mod m. Fermat's Little Theorem: if p is prime and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p). JEE application: find the last two digits of 7^100 (i.e., 7^100 mod 100). Euler's theorem: 7^φ(100) ≡ 1 (mod 100) where φ(100) = 40. 7^40 ≡ 1 (mod 100). 7^100 = 7^(40×2+20) = (7^40)^2 × 7^20 ≡ 1 × 7^20 (mod 100). 7^20 = (7^10)^2. 7^2 = 49, 7^4 = 2401 ≡ 1 (mod 100). 7^20 = (7^4)^5 ≡ 1^5 = 1 (mod 100). So 7^100 ≡ 1 (mod 100) — last two digits 01.

Number of Divisors and Sum of Divisors

If n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ (prime factorisation), then: number of divisors τ(n) = (a₁+1)(a₂+1)…(aₖ+1). Sum of divisors σ(n) = ((p₁^(a₁+1)−1)/(p₁−1)) × ((p₂^(a₂+1)−1)/(p₂−1)) × …. JEE question: "N = 2^3 × 3^2 × 5. Number of divisors = 4×3×2 = 24. Sum of divisors = (1+2+4+8)(1+3+9)(1+5) = 15 × 13 × 6 = 1170." Perfect number (σ(n) = 2n): n = 6, 28, 496. JEE occasionally asks about perfect numbers as a conceptual question. For divisibility applied to permutations and combinations, see our permutations guide and our mathematical induction guide.