Number System — CAT Quantitative Ability

Number System questions frequently involve numbers too large to compute directly — a 100-digit factorial, a power like $7^{100}$, or a divisor count for a number with dozens of factors. The entire topic is a set of shortcuts that avoid ever computing the large number itself, built on prime factorisation, modular arithmetic and a few counting identities.

1. Factors and divisors

If $N=p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_k}$ is the prime factorisation of $N$, then:

$\text{Number of divisors of }N=(a_1+1)(a_2+1)\cdots (a_k+1)$

$\text{Sum of divisors of }N={\prod }_{i=1}^k\frac{p_i^{a_i+1}-1}{p_i-1}$

For $360=2^3\times 3^2\times 5^1$: number of divisors $=(3+1)(2+1)(1+1)=24$, and sum of divisors $=\frac{2^4-1}{1}\times \frac{3^3-1}{2}\times \frac{5^2-1}{4}=15\times 13\times 6=1170$. Both formulas depend entirely on correct prime factorisation — an arithmetic slip there propagates through the whole computation, so factorising carefully is worth the extra ten seconds.

A number is a perfect square if and only if it has an odd number of divisors — every divisor $d$ of $N$ pairs with $N/d$, and this pairing is perfect except when $d=N/d=\sqrt{N}$, which happens only when $N$ is a perfect square. This converts "how many perfect squares divide $N$'s divisor list" reasoning into a parity check on the divisor count itself, without listing a single divisor.

Euler's totient function $\phi (N)$ counts the integers from $1$ to $N$ that share no common factor with $N$, and for $N=p_1^{a_1}{p}_2^{a_2}\cdots$ it is computed directly from the prime factorisation:

$\phi (N)=N{\prod }_i\left(1-\frac{1}{p_i}\right)$

For $N=36=2^2\times 3^2$: $\phi (36)=36\times \left(1-\frac{1}{2}\right)\times \left(1-\frac{1}{3}\right)=36\times \frac{1}{2}\times \frac{2}{3}=12$ — exactly 12 of the numbers from 1 to 36 share no factor with 36.

2. HCF and LCM

For any two numbers, the product of their HCF and LCM always equals the product of the numbers themselves:

$\text{HCF}(a,b)\times \text{LCM}(a,b)=a\times b$

This identity converts a question that gives HCF and one number (or LCM and one number) directly into the other, without factorising either number. The Euclidean algorithm — repeatedly replacing the larger number with the remainder of dividing it by the smaller, until the remainder is $0$ — finds the HCF of two numbers faster than factorising both, especially when the numbers are large or share no small common factors that are easy to spot by inspection.

Trap. The HCF-LCM product identity holds only for two numbers, not three or more. For three numbers, HCF and LCM must each be computed directly (pairwise HCF repeated, or via prime factorisation), and there is no shortcut product relationship analogous to the two-number case.

HCF and LCM of fractions follow their own direct rule, applied to numerators and denominators separately:

$\text{HCF of fractions}=\frac{\text{HCF of numerators}}{\text{LCM of denominators}},\text{LCM of fractions}=\frac{\text{LCM of numerators}}{\text{HCF of denominators}}$

A recurring word-problem pattern — "find the greatest length that can measure three given lengths exactly" — is simply asking for the HCF of the three lengths, while "find the smallest quantity that is a whole multiple of each of several given quantities" is asking for the LCM; recognising which of the two a word problem wants, before computing anything, is the actual difficulty.

3. Divisibility rules

The rule for 11 is the one candidates most often get wrong by applying it inconsistently: take the digits from the right, alternately adding and subtracting, and check whether the result is a multiple of $11$ (including $0$). For $1331$: alternating sum $=1-3+3-1=0$, a multiple of $11$ — confirming $1331=11^3$.

Divisibility by 7 has no single-glance rule, but a genuinely fast iterative one exists: double the last digit, subtract it from the remaining leading digits, and repeat until a small enough number remains to check by inspection. For $483$: last digit $3$, doubled is $6$; remaining digits $48$, minus $6$ is $42$, which is $7\times 6$ — so $483$ is divisible by $7$.

This is faster than long division once practised, though most CAT questions involving 7 are better handled through the remainder and cyclicity techniques of the next two sections rather than a pure divisibility check.

4. Remainders and congruences

Modular arithmetic (writing $a\equiv b(\mathrm{mod}n)$ when $a$ and $b$ leave the same remainder on division by $n$) lets remainders be computed step by step rather than by dividing an enormous number directly: remainders of a product are the product of the remainders (each reduced mod $n$ as you go), and remainders of a sum are the sum of the remainders.

Fermat's little theorem gives a direct shortcut for remainders modulo a prime $p$: if $p$ does not divide $a$, then $a^{p-1}\equiv 1(\mathrm{mod}p)$. This is why large-exponent remainder questions modulo a prime often reduce to finding the exponent's remainder modulo $p-1$ first, rather than reducing the base's powers one at a time.

A binomial-expansion trick handles remainder questions where the base is one more or one less than the divisor. Writing $23^{24}$ as $(24-1{)}^{24}$ and expanding by the binomial theorem, every term except the last carries a factor of $24$, so $(24-1{)}^{24}\equiv (-1{)}^{24}\equiv 1(\mathrm{mod}24)$ — the whole computation reduces to the sign of $(-1{)}^{24}$, with no actual expansion needed.

A negative remainder is simply converted to the standard positive form by adding the divisor: a computed remainder of $-1$ modulo $24$ is reported as $23$, since remainders are conventionally stated as non-negative and smaller than the divisor.

5. Units digit and cyclicity

The units digit of a power depends only on the units digit of the base, and it repeats in a cycle of length at most 4:

To find the units digit of $N^k$, find the cycle for $N$'s units digit, then reduce $k$ modulo the cycle length (treating a remainder of $0$ as the last position in the cycle, not position $0$). For $3^{58}$: the cycle of $3$ is $3,9,7,1$ (length 4), and $58\mathrm{mod}4=2$, so the units digit is the 2nd entry, $9$.

6. Primes

A number is prime only if it has no factor other than 1 and itself, and testing this requires checking divisibility only up to its square root — if $N$ had a factor greater than $\sqrt{N}$, it would necessarily pair with a factor smaller than $\sqrt{N}$, which would already have been found. This is why primality testing for even a fairly large number is fast: checking $\sqrt{997}\approx 31.6$ means testing divisibility only by primes up to $31$.

Any two consecutive integers are always coprime (their HCF is always 1), since any common factor greater than 1 would have to divide their difference, which is exactly 1. This single fact underlies why consecutive-integer product and sum questions in probability and counting rarely need an explicit HCF computation — coprimality is guaranteed by the setup itself.

6a. Number systems and base conversion

A number written in base $b$ uses digits $0$ through $b-1$, and its value in base 10 is the sum of each digit times the corresponding power of $b$. Converting $(2354{)}_8$ (base 8) to base 10: $2\times 8^3+3\times 8^2+5\times 8^1+4\times 8^0=1024+192+40+4=1260$.

Converting base 10 to another base reverses the process, by repeated division: divide by the target base, record the remainder, and repeat on the quotient until it reaches 0 — the remainders, read from last to first, are the digits of the new base representation. This is the same repeated-division idea used in the Euclidean algorithm, applied to place value instead of to a common factor.

7. Factorials — trailing zeros and prime powers

A trailing zero in $n!$ comes from a factor of $10=2\times 5$, and factors of 5 are always scarcer than factors of 2 in a factorial — so the number of trailing zeros equals the number of times $5$ divides $n!$, computed by Legendre's formula:

$\text{Highest power of prime }p\text{ dividing }n!=\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +\lfloor \frac{n}{p^3}\rfloor +\cdots$

For $100!$: trailing zeros $=\lfloor \frac{100}{5}\rfloor +\lfloor \frac{100}{25}\rfloor +\lfloor \frac{100}{125}\rfloor =20+4+0=24$. The same formula with any prime $p$ gives the highest power of that prime dividing $n!$, not just $p=5$ for trailing zeros.

8. Counting via inclusion-exclusion

For two overlapping conditions, counting "either A or B" by simply adding the counts of A and B double-counts everything satisfying both:

$|A\cup B|=|A|+|B|-|A\cap B|$

To count numbers from 1 to 100 divisible by 2 or 3: $\lfloor \frac{100}{2}\rfloor +\lfloor \frac{100}{3}\rfloor -\lfloor \frac{100}{6}\rfloor =50+33-16=67$. The subtracted term is always the count divisible by the LCM of the two divisors, not their product, which matters once the two conditions share a common factor.

For three conditions, the pattern extends by adding back the triple overlap that gets subtracted out twice:

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|A\cap C|+|A\cap B\cap C|$

Each pairwise and triple intersection is again computed via the LCM of the relevant divisors — counting numbers up to 100 divisible by 2, 3 or 5 needs the individual counts, all three pairwise LCM counts (6, 15, 10), and the count divisible by their overall LCM (30), combined by this alternating pattern.

Worked Examples

Example 1 (divisors — easy). Find the number of divisors and the sum of divisors of 360.

$360=2^3\times 3^2\times 5^1$. Number of divisors $=(3+1)(2+1)(1+1)=24$. Sum of divisors $=\frac{2^4-1}{2-1}\times \frac{3^3-1}{3-1}\times \frac{5^2-1}{5-1}=15\times 13\times 6=1170$.

Example 2 (HCF-LCM — easy). Two numbers have HCF 12 and LCM 72. If one of the numbers is 24, find the other.

Using $\text{HCF}\times \text{LCM}=$ product of the numbers: $12\times 72=24\times x\Rightarrow 864=24x\Rightarrow x=36$.

Example 3 (HCF via Euclid — medium). Find the HCF of 1071 and 462 using the Euclidean algorithm.

$1071=2\times 462+147$. $462=3\times 147+21$. $147=7\times 21+0$. The last non-zero remainder is $21$, so $\text{HCF}(1071,462)=21$.

Example 4 (remainders — hard). Find the remainder when $7^{100}$ is divided by 5.

$7\equiv 2(\mathrm{mod}5)$, so we need $2^{100}\mathrm{mod}5$. The cycle of powers of $2$ mod $5$ is $2,4,3,1$ (length 4, matching Fermat's little theorem since $5-1=4$). $100\mathrm{mod}4=0$, meaning the exponent is an exact multiple of the cycle length, landing on the last (4th) entry: $1$. The remainder is $1$.

Example 5 (units digit — easy). Find the units digit of $3^{58}$.

The cycle of units digits of powers of 3 is $3,9,7,1$ (length 4). $58\mathrm{mod}4=2$, landing on the 2nd entry: $9$.

Example 6 (factorials, trailing zeros — medium). Find the number of trailing zeros in $100!$.

$\lfloor \frac{100}{5}\rfloor +\lfloor \frac{100}{25}\rfloor +\lfloor \frac{100}{125}\rfloor =20+4+0=24$ trailing zeros.

Example 7 (factorials, prime power — hard). Find the highest power of 3 that divides $50!$.

$\lfloor \frac{50}{3}\rfloor +\lfloor \frac{50}{9}\rfloor +\lfloor \frac{50}{27}\rfloor +\lfloor \frac{50}{81}\rfloor =16+5+1+0=22$. So $3^{22}$ divides $50!$, and $3^{23}$ does not.

Example 8 (inclusion-exclusion — medium). How many integers from 1 to 100 are divisible by 2 or 3?

$\lfloor \frac{100}{2}\rfloor +\lfloor \frac{100}{3}\rfloor -\lfloor \frac{100}{6}\rfloor =50+33-16=67$.

Example 9 (base conversion — medium). Convert 300 (base 10) to base 8.

$300÷8=37$ remainder $4$. $37÷8=4$ remainder $5$. $4÷8=0$ remainder $4$. Reading the remainders from last to first: $(454{)}_8$.

Check: $4\times 64+5\times 8+4\times 1=256+40+4=300$, confirming the conversion.

Summary

Number System questions almost always avoid computing the large number itself — through prime factorisation, modular arithmetic, or a counting identity — so the goal is always to find the right shortcut, not to brute-force the arithmetic.

Number and sum of divisors follow directly from prime factorisation: $(a_1+1)(a_2+1)\cdots$ for the count, and the product of $\frac{p^{a+1}-1}{p-1}$ terms for the sum.

HCF × LCM equals the product of the two numbers — for two numbers only, never three or more — and the Euclidean algorithm finds HCF fast without factorising.

Units digits and remainders both repeat in cycles of length at most 4 (mod 10 for units digits; length $p-1$ for remainders modulo a prime $p$, via Fermat's little theorem); reduce the exponent modulo the cycle length, treating an exact multiple as the last position, not position zero.

Trailing zeros in $n!$ and the highest power of any prime dividing $n!$ both use Legendre's formula, summing $\lfloor n/p^k\rfloor$ until the terms vanish.

Inclusion-exclusion for two overlapping conditions subtracts the count divisible by their LCM, not their product, from the sum of the individual counts.