Number System
🔒 Log in to trackhigh importance~2 Q in Tier 133 formulas⚡ 18 shortcuts6 subtopics
Every formula in this topic, grouped by subtopic. Print it and pin it above your desk.
Number types, place value & counting
Multiples of k from 1 to n
\left\lfloor \frac{n}{k} \right\rfloor
Multiples of k from a to b
\left\lfloor \frac{b}{k} \right\rfloor - \left\lfloor \frac{a-1}{k} \right\rfloor
Inclusion–exclusion
n(A \cup B) = n(A) + n(B) - n(A \cap B)
A ∩ B = multiples of LCM
Sum of first n natural numbers
\frac{n(n+1)}{2}
Sum of squares
1^2+2^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}
Sum of cubes
1^3+2^3+\cdots+n^3 = \left[\frac{n(n+1)}{2}\right]^2
First n odd / even numbers
1+3+\cdots+(2n-1) = n^2,\quad 2+4+\cdots+2n = n(n+1)
AP: terms and sum
n = \frac{l-a}{d}+1,\quad S = \frac{n}{2}(a+l)
Divisibility rules
Divisibility by 11
\left(\sum \text{odd-place digits}\right) - \left(\sum \text{even-place digits}\right) \in \{0, \pm 11, \pm 22, \dots\}
Composite divisor
pq \mid N \iff p \mid N \text{ and } q \mid N, \quad \gcd(p,q)=1
Difference of powers
(a-b) \mid (a^n - b^n) \text{ for all } n
Difference of even powers
(a+b) \mid (a^n - b^n) \text{ when } n \text{ is even}
Sum of odd powers
(a+b) \mid (a^n + b^n) \text{ when } n \text{ is odd}
abcabc form
\overline{abcabc} = \overline{abc} \times 1001 = \overline{abc} \times 7 \times 11 \times 13
Remainders & remainder theorem
Division algorithm
N = d \times q + r,\quad 0 \le r < d
Product rule
\text{Rem}\left(\frac{a \times b}{d}\right) = \text{Rem}\left(\frac{R_a \times R_b}{d}\right)
Fermat's little theorem
a^{p-1} \equiv 1 \pmod{p},\quad p \text{ prime},\ \gcd(a,p)=1
Divisor-multiple rule
N \equiv r \pmod{D},\ d \mid D \ \Rightarrow\ N \equiv r \pmod{d}
Base one more than divisor
(ad+1)^n \equiv 1 \pmod{d}
Base one less than divisor
(ad-1)^n \equiv (-1)^n \pmod{d}
remainder 1 if n even, d − 1 if n odd
Unit digit & cyclicity
Cyclicity rule
\text{u.d.}(a^n) = \text{u.d.}(a^{r}),\ r = n \bmod 4,\ (r = 0 \Rightarrow r = 4)
Cycles of 2, 3, 7, 8
2:\,2,4,8,6 \quad 3:\,3,9,7,1 \quad 7:\,7,9,3,1 \quad 8:\,8,4,2,6
Factorials
n! \equiv 0 \pmod{10} \text{ for } n \ge 5
Factors, prime factorisation & trailing zeros
Number of factors
d(N) = (a+1)(b+1)(c+1)
Sum of factors
\sigma(N) = \frac{p^{a+1}-1}{p-1} \cdot \frac{q^{b+1}-1}{q-1} \cdot \frac{r^{c+1}-1}{r-1}
Even factors
a \cdot (b+1)(c+1)
when p = 2 with exponent a
Product of all factors
N^{d(N)/2}
Trailing zeros in n!
\left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{25} \right\rfloor + \left\lfloor \frac{n}{125} \right\rfloor + \cdots
Highest power of prime p in n!
\sum_{k \ge 1} \left\lfloor \frac{n}{p^k} \right\rfloor
Fractions, decimals & recurring decimals
Pure recurring
0.\overline{ab} = \frac{ab}{99},\quad 0.\overline{abc} = \frac{abc}{999}
Mixed recurring
0.a\overline{bc} = \frac{abc - a}{990}
Terminating test
\frac{p}{q} \text{ (lowest terms) terminates} \iff q = 2^m \, 5^n
Cross-multiplication
\frac{a}{b} > \frac{c}{d} \iff ad > bc \quad (b, d > 0)