Number system and divisibility

In short

The number system is the foundation layer of quantitative aptitude: how integers are classified, how they factorise into primes, and what remainder they leave on division. Divisibility rules, HCF/LCM, unit-digit cyclicity and remainder theorems turn questions that look like heavy computation into two-line mental work. Almost every Indian recruitment test — TCS NQT, Infosys, Wipro NLTH, Capgemini, Accenture, Cognizant, IBPS/SBI PO, SSC CGL, RRB, CAT/XAT — opens with two or three questions from this area, and GATE CS tests the same ideas formally as modular arithmetic and number bases in Discrete Mathematics. On the job the same arithmetic appears in checksum digits (Aadhaar, GSTIN, ISBN, card numbers), hash buckets, cyclic schedules and batch-size calculations.

Explained

Classification of numbers and place value

• Natural numbers (N): 1, 2, 3, … ; whole numbers (W): 0, 1, 2, …; integers (Z): …, −2, −1, 0, 1, 2, …
• Rational (Q): expressible as p/q with integers p, q and q ≠ 0; decimal either terminates or repeats. A fraction p/q in lowest terms terminates only if q has no prime factor other than 2 and 5.
• Irrational: non-terminating, non-repeating — √2, √3, π, e. Real (R) = rational ∪ irrational. Imaginary: √(−1) = i; complex: a + ib.
• Even / odd: divisible by 2 or not. Even ± even = even; odd ± odd = even; odd × odd = odd.
• Prime: exactly two factors (1 and itself). 2 is the only even prime; 1 is neither prime nor composite. There are 25 primes below 100.
• Composite: more than two factors. Co-prime (relatively prime): HCF = 1, e.g. (8, 15) — they need not be prime themselves.
• Twin primes: differ by 2 (11, 13). Perfect number: equals the sum of its proper divisors — 6, 28, 496.
• Place value vs face value: in 48,357 the face value of 8 is 8 but its place value is 8,000. Difference = face value × (place multiplier − 1).
• Primality test: to check whether n is prime, test divisibility only by primes up to √n. For 211, √211 ≈ 14.5, so test 2, 3, 5, 7, 11, 13 — none divides it, so 211 is prime.
• Digit facts: a perfect square ends only in 0, 1, 4, 5, 6 or 9 (never 2, 3, 7, 8) and has an odd number of factors; digit sum of a perfect square reduces to 1, 4, 7 or 9.

Divisibility rules and why they work

• Rules for 3, 9 and 11 come from powers of 10: 10 ≡ 1 (mod 9) so a number ≡ its digit sum (mod 9); 10 ≡ −1 (mod 11) so a number ≡ its alternating digit sum (mod 11).
• Rules for 4, 8, 16, 25, 125 come from the fact that 100 is divisible by 4 and 25, 1000 by 8 and 125, and 10000 by 16 — so only the trailing digits matter.
• 1001 = 7 × 11 × 13, which is why grouping digits in threes from the right and alternately adding/subtracting the groups tests 7, 11 and 13 at once.

• Composite divisors: split into co-prime factors only. 24 = 8 × 3 (co-prime) works; 24 = 4 × 6 does not — 12 passes both 4 and 6 but is not divisible by 24.
• Products of consecutive integers: the product of any r consecutive integers is divisible by r!. So n(n+1) is always even, n(n+1)(n+2) is divisible by 6, and n³ − n is divisible by 6.
• Useful algebraic divisibility: aⁿ − bⁿ is always divisible by (a − b); it is divisible by (a + b) when n is even. aⁿ + bⁿ is divisible by (a + b) when n is odd.

Division algorithm, remainders and successive division

• Division algorithm: Dividend = Divisor × Quotient + Remainder, with 0 ≤ Remainder < Divisor. Every such problem reduces to this identity.
• Negative remainder shortcut: remainder of 29 ÷ 30 can be read as −1, which makes powers easy — 29ⁿ ÷ 30 leaves 29 for odd n and 1 for even n.
• Modular arithmetic: if a ≡ r₁ and b ≡ r₂ (mod m), then a + b ≡ r₁ + r₂ and a × b ≡ r₁ × r₂ (mod m). Reduce first, multiply later — never the other way round.
• Successive division: "divided by 5 leaves 3, the quotient divided by 4 leaves 2" means N = 5(4k + 2) + 3 = 20k + 13; so N ÷ 20 leaves 13. Build from the last division backwards.
• Same remainder on several divisors: N = LCM(d₁, d₂, …)k + r. If the remainders differ but each falls short of its divisor by the same amount c, then N = LCM·k − c.
• Chinese Remainder idea: for co-prime moduli, a system such as N ≡ 2 (mod 3), N ≡ 3 (mod 5) has a unique solution modulo 15 — here N = 8, so N = 15k + 8.
• Number bases (GATE): a numeral (dₙ…d₁d₀) in base b equals Σ dᵢbⁱ. Convert decimal → base b by repeated division, reading remainders bottom-up: 173 = 1010 1101₂ = AD₁₆ (10 × 16 + 13 = 173). Binary → hex by grouping four bits from the right.

Factors, HCF and LCM

• Prime factorisation (Fundamental Theorem of Arithmetic): every integer > 1 has a unique prime factorisation, N = p₁^a · p₂^b · p₃^c …
• HCF (GCD): product of common primes to the lowest power — largest number dividing all. LCM: all primes to the highest power — smallest number divisible by all.
• Euclid's algorithm: HCF(a, b) = HCF(b, a mod b), repeated until the remainder is 0 — the standard method for large numbers and the one coded in interviews.
• Classic HCF applications: largest number that divides a, b, c leaving remainders r₁, r₂, r₃ = HCF(a − r₁, b − r₂, c − r₃); largest number leaving the same remainder = HCF of the pairwise differences; largest square tile for a floor; maximum identical kits from different stocks.
• Classic LCM applications: bells/traffic signals ringing together, two gear wheels meeting again, least number of sweets divisible among groups, cyclic shift rosters.
• Fractions: HCF of fractions = HCF(numerators)/LCM(denominators); LCM of fractions = LCM(numerators)/HCF(denominators). Example: HCF(2/3, 8/9, 16/81) = 2/81.

Unit digits, cyclicity and powers

• The last digit of aⁿ depends only on the last digit of a and on n modulo the cycle length.
• Cycle length 1: 0, 1, 5, 6 (the digit repeats). Cycle length 2: 4 and 9 (4, 6 and 9, 1). Cycle length 4: 2, 3, 7, 8.
• Working rule for 2, 3, 7, 8: divide the exponent by 4; use the remainder (a remainder of 0 means use exponent 4).
• Last two digits: for numbers ending in 1, the last two digits of (…a1)ⁿ are (last digit of a × n) followed by 1. For others, use 7⁴ = 2401 ≡ 01, 2¹⁰ = 1024 ≡ 24, 3⁴ = 81, etc. (mod 100).
• Number of digits in a large power: digits = ⌊log₁₀ x⌋ + 1. For 2²⁰, 20 × 0.30103 = 6.02 → 7 digits (1,048,576).

Factorials, trailing zeros and the highest power of a prime

• Legendre's formula: the highest power of a prime p in n! = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + … (stop when the term is 0).
• Trailing zeros of n! = highest power of 5 in n! (5s are scarcer than 2s). In a general product, count min(power of 2, power of 5).
• For a composite divisor, factorise first: the highest power of 6 in n! is governed by the power of 3; the highest power of 8 is ⌊(power of 2)/3⌋.
• n! is divisible by every integer up to n, so for n ≥ 5 it ends in 0; 0! = 1! = 1.

Remainder theorems for powers

• Euler's totient: φ(N) = N(1 − 1/p₁)(1 − 1/p₂)… counts integers below N that are co-prime to N. Euler's theorem: if HCF(a, N) = 1 then a^φ(N) ≡ 1 (mod N).
• Fermat's little theorem: for prime p and HCF(a, p) = 1, a^p−1 ≡ 1 (mod p); equivalently a^p ≡ a (mod p).
• Wilson's theorem: (p − 1)! ≡ −1 (mod p) for prime p; so 16! ÷ 17 leaves remainder 16.
• Binomial/remainder trick: write the base as (multiple of divisor ± small number). 102⁵⁰ ÷ 101 → (101 + 1)⁵⁰ ≡ 1⁵⁰ = 1.
• Limitation: Euler's and Fermat's theorems need the base and modulus co-prime. For 10¹⁰⁰ ÷ 8, use powers of 2 directly (remainder 0), not φ.

Key points

• Division algorithm - Dividend = Divisor × Quotient + Remainder, 0 ≤ R < Divisor; every remainder question reduces to it.
• Prime test - check divisibility only by primes up to √n; 25 primes lie below 100; 2 is the only even prime.
• Co-prime - HCF = 1; a composite divisibility test must split the divisor into co-prime parts.
• 3 and 9 - digit-sum rules, because 10 ≡ 1 (mod 9). 11 - alternating digit sum, because 10 ≡ −1 (mod 11).
• 4, 8, 16, 25, 125 - decided by the last two, three or four digits only.
• 7 and 13 - iterate: subtract twice the last digit (7) or add four times it (13); or use 1001 = 7 × 11 × 13 with three-digit groups.
• Number of factors - d(N) = (a+1)(b+1)(c+1) from N = p^a q^b r^c; odd only for perfect squares.
• HCF × LCM = product - true for exactly two numbers, not for three or more.
• HCF applications - largest divisor, equal grouping, largest tile; LCM applications - simultaneous events, smallest common quantity.
• Cyclicity - unit digits repeat with period 4 for 2, 3, 7, 8; period 2 for 4, 9; period 1 for 0, 1, 5, 6.
• Legendre's formula - highest power of prime p in n! = Σ ⌊n/pⁱ⌋; trailing zeros of n! = power of 5.
• Euler's theorem - a^φ(N) ≡ 1 (mod N) when HCF(a, N) = 1; φ(N) = N∏(1 − 1/p).
• Fermat's little theorem - a^p−1 ≡ 1 (mod p) for prime p; the fastest route for prime divisors.
• Negative remainders - treat a remainder of d − 1 as −1; it collapses alternating-sign power problems instantly.
• Consecutive integers - the product of r consecutive integers is divisible by r!; n³ − n is always divisible by 6.
• aⁿ − bⁿ - always divisible by (a − b); by (a + b) too when n is even; aⁿ + bⁿ divisible by (a + b) when n is odd.
• Base b - value = Σ dᵢbⁱ; convert by repeated division and read remainders in reverse.
• Digit count - ⌊log₁₀ x⌋ + 1 digits.

Formulas and examples

Example 1 - unit digit of 7⁹⁵ + 3⁵⁸ + 4³³

• 7 has cycle 4: 95 ÷ 4 leaves 3 → unit digit of 7³ = 343 → 3.
• 3 has cycle 4: 58 ÷ 4 leaves 2 → unit digit of 3² = 9 → 9.
• 4 has cycle 2: odd power → 4.
• Sum of unit digits = 3 + 9 + 4 = 16 → the answer's unit digit is 6.

Example 2 - the full factor profile of 1080

• 1080 = 2³ × 3³ × 5¹.
• Number of factors = (3+1)(3+1)(1+1) = 32.
• Sum of factors = (1+2+4+8)(1+3+9+27)(1+5) = 15 × 40 × 6 = 3,600.
• Odd factors: ignore the 2s → (3+1)(1+1) = 8; even factors = 32 − 8 = 24.
• Ways to write 1080 as a product of two factors = 32/2 = 16; as a product of two co-prime factors = 2³⁻¹ = 4 (1 × 1080, 8 × 135, 27 × 40, 5 × 216).
• Product of all 32 factors = 1080¹⁶.
• φ(1080) = 1080 × ½ × ⅔ × ⅘ = 288 numbers below 1080 are co-prime to it.

Example 3 - five remainder problems

• 2¹⁰⁰ ÷ 7: 2³ = 8 ≡ 1 (mod 7); 100 = 3 × 33 + 1, so 2¹⁰⁰ ≡ 2¹ = 2.
• 17²³ ÷ 9: 17 ≡ −1 (mod 9), so (−1)²³ = −1 ≡ 8.
• 3¹⁰⁰ ÷ 13 (Fermat, φ(13) = 12): 100 = 12 × 8 + 4, so 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 81 − 78 = 3.
• 2⁸⁹ ÷ 89 (89 is prime): 2⁸⁸ ≡ 1, so 2⁸⁹ ≡ 2.
• Last two digits of 7⁸¹: 7⁴ = 2401 ≡ 01 (mod 100), 81 = 4 × 20 + 1 → 07.

Example 4 - HCF and LCM word problems

• *Largest number that divides 1,657 and 2,037 leaving remainders 6 and 5:* subtract the remainders → HCF(1,651, 2,037 − 5 = 2,032). 1,651 = 13 × 127 and 2,032 = 16 × 127, so the answer is 127.
• *Smallest number that leaves remainder 3 on division by 5, 6, 7 and 8 and is exactly divisible by 9:* LCM(5, 6, 7, 8) = 840, so N = 840k + 3. For divisibility by 9, 840 ≡ 3 (mod 9) → 3k + 3 ≡ 0 (mod 9) → k + 1 ≡ 0 (mod 3) → k = 2. N = 1,683 (1,683 = 9 × 187, and 1,683 ÷ 7 = 240 remainder 3 ✓).
• *Cross-check on two numbers:* HCF(72, 120) = 24, LCM = 360, and 24 × 360 = 8,640 = 72 × 120 ✓. For three numbers 72, 120, 192: HCF = 2³ × 3 = 24, LCM = 2⁶ × 3² × 5 = 2,880 — and 24 × 2,880 ≠ 72 × 120 × 192, which is why the product rule must not be extended.

Example 5 - factorials and bases

• Trailing zeros in 100!: ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24.
• Highest power of 3 in 50!: ⌊50/3⌋ + ⌊50/9⌋ + ⌊50/27⌋ = 16 + 5 + 1 = 22.
• Highest power of 7 in 100!: 14 + 2 = 16.
• Highest power of 8 in 50!: power of 2 = 25 + 12 + 6 + 3 + 1 = 47, so ⌊47/3⌋ = 15.
• Convert 173 to binary: 173 = 128 + 32 + 8 + 4 + 1 → 1010 1101₂; grouping as 1010 1101 gives AD₁₆.

Where it is used

• Campus aptitude rounds: TCS NQT, Infosys, Wipro, Capgemini, Accenture, Cognizant and Zoho start with unit-digit, remainder and HCF/LCM questions; these are the cheapest marks in the paper.
• Government and banking exams: SSC CGL/CHSL, IBPS and SBI PO/Clerk, RRB NTPC and RBI Grade B all carry a fixed quota of number-system questions.
• Software and coding interviews: GCD by Euclid's algorithm, Sieve of Eratosthenes for primes, modular exponentiation, "count trailing zeros in n!" and "check Armstrong/perfect number" are standard first-round coding problems at Indian product and service firms.
• Identity and payment checksums: Aadhaar uses a Verhoeff check digit, GSTIN a weighted modulo-36 check character, ISBN-13 a modulo-10 weighted sum, and card numbers the Luhn (mod 10) algorithm — all validity tests built on modular arithmetic.
• Operations and planning: LCM fixes maintenance and shift cycles (a machine serviced every 6 days and another every 8 days coincide every 24 days); HCF fixes the largest common pack or tile size in manufacturing and civil work.
• Cryptography and hashing: RSA rests on prime factorisation and Euler's theorem; hash tables use prime moduli to spread keys, which is why interviewers ask why bucket counts are prime.

Interview questions

• Q: Why is 1 neither prime nor composite? A: A prime has exactly two distinct factors and a composite more than two; 1 has only one factor, so it fits neither definition — and treating it as prime would break unique prime factorisation.
• Q: How do you test whether a number is prime quickly? A: Trial-divide by primes up to √n only, because any factor larger than √n must pair with one smaller than √n.
• Q: A number is divisible by 4 and by 6 — must it be divisible by 24? A: No. 4 and 6 are not co-prime; 12 passes both tests but is not a multiple of 24. Only co-prime factors can be combined.
• Q: Why does the digit-sum rule work for 9 but not for 7? A: Because 10 ≡ 1 (mod 9), so every power of 10 contributes its digit unchanged; modulo 7 the powers of 10 cycle through 1, 3, 2, 6, 4, 5, so plain digit sums carry no information.
• Q: Find the remainder of 2¹⁰⁰ ÷ 7 in your head. A: 2³ ≡ 1 (mod 7) and 100 = 3 × 33 + 1, so the remainder is 2.
• Q: How many zeros does 100! end with, and why count 5s and not 2s? A: 24 zeros — a zero needs a 2 and a 5, and factorials contain far more 2s than 5s, so the 5s are the binding constraint.
• Q: Why does HCF × LCM = product fail for three numbers? A: The identity relies on each prime's exponents splitting into just a minimum and a maximum; with three or more numbers the middle exponents are left out, so the equality breaks.
• Q: When can Euler's theorem not be used for a remainder? A: When the base and the modulus share a factor — the theorem needs HCF(a, N) = 1; otherwise reduce via prime powers or the Chinese Remainder Theorem.
• Q: What is the largest number dividing 1,657 and 2,037 leaving remainders 6 and 5? A: HCF(1,651, 2,032) = 127.
• Q: How many factors does a perfect square have, and why is that useful? A: An odd number, because every exponent in its prime factorisation is even, so (a+1) is odd for each prime — a quick way to spot or rule out perfect squares.
• Q: Prove that n³ − n is divisible by 6 for every integer n. A: n³ − n = (n−1)n(n+1), a product of three consecutive integers, which always contains a multiple of 2 and a multiple of 3, hence is divisible by 6.
• Q: How would you code GCD without recursion? A: Loop the Euclidean step — while b ≠ 0, set (a, b) = (b, a mod b) — and return a; it runs in O(log min(a, b)).

Common mistakes

• Splitting a composite divisor into non-co-prime factors (24 as 4 × 6 instead of 8 × 3) and declaring a wrong number divisible.
• Extending HCF × LCM = product to three or more numbers.
• Forgetting to subtract the remainders before taking the HCF in "largest divisor leaving remainder r" problems, or to add r back at the end in LCM problems.
• Using the exponent itself instead of exponent mod 4 for unit digits — and treating a remainder of 0 as power 0 rather than power 4.
• In Legendre's formula, stopping at ⌊n/p⌋ and missing the higher terms ⌊n/p²⌋, ⌊n/p³⌋ — the usual cause of a wrong trailing-zero count.
• Applying Euler's or Fermat's theorem when base and modulus are not co-prime, or taking φ(N) = N − 1 for a composite N (that holds only for a prime, where φ(p) = p − 1).
• Reading successive division forwards instead of building the number backwards from the last quotient, and treating 1 as prime or 0! as 0.

Related topics

Simplification and approximation · Squares, cubes, roots and surds · Problems on ages and numbers · Algebra: linear and quadratic equations · Progressions and logarithms · Permutations and combinations