Formula sheet · Algebra - Number Theory

Number System & Number Theory Formula Sheet

All QA formula sheets

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

FormulaWhen 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 11Quick 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 isTesting 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 factorsProduct of all positive divisors.
If \(N = 2^a \times M\) with \(M\) odd: odd factors \(=\) number of factors of \(M\); even factors \(=\) total \(-\) oddCounting 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

FormulaWhen 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

FormulaWhen to use
Remainder of a sum or product \(=\) remainder of the sum or product of the individual remaindersBreaking 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 1Factorials 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 oddSpotting factors of expressions like \(17^{20} - 1\).

Factorials

FormulaWhen 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 resultHighest power of a composite number in \(n!\).

Last-digit cycles

Last digit of baseCycle of last digitsLast digit of baseCycle of last digits
22, 4, 8, 677, 9, 3, 1
33, 9, 7, 188, 4, 2, 6
44, 699, 1
0, 1, 5, 6Always 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.

Practise Algebra - Number Theory →