Number System & Number Theory Formula Sheet
Number System is tested in almost every CAT paper through factors, remainders, last digits and factorials. Learn prime factorisation well: nearly every formula below starts from \(N = p^a q^b r^c\), where \(p, q, r\) are distinct primes.
Divisibility and factors
| Formula | When to use |
|---|---|
| Divisible by 2, 4, 8 if the last 1, 2, 3 digits are; by 3 or 9 if the digit sum is; by 11 if (sum of odd-place digits) \(-\) (sum of even-place digits) is a multiple of 11 | Quick divisibility checks. |
| Since \(1001 = 7 \times 11 \times 13\): split the number into groups of three digits from the right; it is divisible by 7, 11 or 13 if the alternating sum of the groups is | Testing 7 and 13 on large numbers. |
| \(N\) is divisible by \(mn\) if it is divisible by both \(m\) and \(n\), provided \(\gcd(m, n) = 1\) | Divisibility by 12, 15, 72 and so on: test \(4 \times 3\), \(3 \times 5\), \(8 \times 9\). |
| Number of factors of \(N\): \((a + 1)(b + 1)(c + 1)\) | Counting all positive divisors. |
| Sum of factors: \(\dfrac{p^{a+1} - 1}{p - 1} \times \dfrac{q^{b+1} - 1}{q - 1} \times \dfrac{r^{c+1} - 1}{r - 1}\) | Adding all positive divisors. |
| Product of factors: \(N^{d/2}\), where \(d\) is the number of factors | Product of all positive divisors. |
| If \(N = 2^a \times M\) with \(M\) odd: odd factors \(=\) number of factors of \(M\); even factors \(=\) total \(-\) odd | Counting odd or even divisors. |
| Ways to write \(N\) as a product of two factors (order ignored): \(\dfrac{d}{2}\) if \(N\) is not a perfect square, \(\dfrac{d + 1}{2}\) if it is. As a product of two coprime factors: \(2^{k-1}\), where \(k\) is the number of distinct primes | "In how many ways can N be written as a product" questions. |
HCF and LCM
| Formula | When to use |
|---|---|
| \(\text{HCF}(a, b) \times \text{LCM}(a, b) = a \times b\) | Finding one of the four values from the other three. Two numbers only. |
| HCF of fractions \(= \dfrac{\text{HCF of numerators}}{\text{LCM of denominators}}\); LCM of fractions \(= \dfrac{\text{LCM of numerators}}{\text{HCF of denominators}}\) | Fractions in lowest terms. |
| Largest number that divides \(a, b, c\) leaving the same remainder: \(\text{HCF}(|a - b|, |b - c|)\) | "Same remainder" questions. |
| Numbers leaving remainder \(r\) when divided by each of \(m, n, k\) (with \(r\) less than each divisor): \(t \times \text{LCM}(m, n, k) + r\), for integers \(t \ge 0\) | "Same remainder each time" from the dividend side. The smallest such number above \(r\) is \(\text{LCM} + r\). |
Remainders
| Formula | When to use |
|---|---|
| Remainder of a sum or product \(=\) remainder of the sum or product of the individual remainders | Breaking a large expression into small pieces. Negative remainders such as \(-1\) are allowed. |
| Fermat: if \(p\) is prime and \(p\) does not divide \(a\), then \(a^{p-1}\) leaves remainder 1 when divided by \(p\) | Large powers divided by a prime. |
| Euler: if \(\gcd(a, n) = 1\), then \(a^{\phi(n)}\) leaves remainder 1 when divided by \(n\), where \(\phi(n) = n\left(1 - \frac{1}{p}\right)\left(1 - \frac{1}{q}\right)\cdots\) over the distinct primes of \(n\) | Large powers divided by a composite number. |
| Wilson: if \(p\) is prime, \((p - 1)!\) leaves remainder \(p - 1\) when divided by \(p\); also \((p - 2)!\) leaves remainder 1 | Factorials divided by a prime. |
| \(a^n - b^n\) is divisible by \(a - b\) for every positive integer \(n\), and by \(a + b\) when \(n\) is even; \(a^n + b^n\) is divisible by \(a + b\) when \(n\) is odd | Spotting factors of expressions like \(17^{20} - 1\). |
Factorials
| Formula | When to use |
|---|---|
| Highest power of a prime \(p\) in \(n!\): \(\left\lfloor \dfrac{n}{p} \right\rfloor + \left\lfloor \dfrac{n}{p^2} \right\rfloor + \left\lfloor \dfrac{n}{p^3} \right\rfloor + \cdots\) | Largest \(k\) such that \(p^k\) divides \(n!\). |
| Trailing zeros of \(n!\): \(\left\lfloor \dfrac{n}{5} \right\rfloor + \left\lfloor \dfrac{n}{25} \right\rfloor + \left\lfloor \dfrac{n}{125} \right\rfloor + \cdots\) | Number of zeros at the end of a factorial (fives are scarcer than twos). |
| For a composite base such as \(12 = 2^2 \times 3\): find the power of each prime in \(n!\), divide by its exponent in the base, take the floor, and use the smallest result | Highest power of a composite number in \(n!\). |
Last-digit cycles
| Last digit of base | Cycle of last digits | Last digit of base | Cycle of last digits |
|---|---|---|---|
| 2 | 2, 4, 8, 6 | 7 | 7, 9, 3, 1 |
| 3 | 3, 9, 7, 1 | 8 | 8, 4, 2, 6 |
| 4 | 4, 6 | 9 | 9, 1 |
| 0, 1, 5, 6 | Always the same digit |
Shortcuts and traps
- Using the cycle: for an exponent \(n \ge 1\), find the remainder of \(n\) divided by 4; a remainder of 0 means take the 4th term. So \(7^{100}\) ends in 1.
- Use \(-1\): \(2^{100}\) divided by 3: since \(2\) leaves \(-1\), the remainder is \((-1)^{100} = 1\).
- Coprime condition: Fermat and Euler fail if the base shares a factor with the divisor. Split the divisor into coprime parts first.
- HCF \(\times\) LCM: the product rule works for two numbers only, never for three.
- 1 is special: 1 is neither prime nor composite, and it is counted among the factors of every number.