Number System
🔒 Log in to trackhigh importance~2 Q in Tier 135 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 up to n
\left\lfloor \dfrac{n}{k} \right\rfloor
Multiples of k from a to b
\left\lfloor \dfrac{b}{k} \right\rfloor - \left\lfloor \dfrac{a-1}{k} \right\rfloor
Inclusion-exclusion
n(A \cup B) = n(A) + n(B) - n(A \cap B)
the overlap holds multiples of the LCM
Sum of first n natural numbers
\dfrac{n(n+1)}{2}
Sum of squares
1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}
Sum of cubes
1^3 + 2^3 + \cdots + n^3 = \left[\dfrac{n(n+1)}{2}\right]^2
First n odd or even numbers
1 + 3 + \cdots + (2n-1) = n^2, \quad 2 + 4 + \cdots + 2n = n(n+1)
Any arithmetic series
S = \dfrac{n}{2}(a + l)
terms times average of first and last
Digit reversal
(10a + b) - (10b + a) = 9(a - b), \quad (10a + b) + (10b + a) = 11(a + b)
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, \ldots\}
Composite divisor
pq \mid N \iff p \mid N \text{ and } q \mid N, \quad \gcd(p, q) = 1
split into co-prime parts only
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}
Repeated block
\overline{abcabc} = \overline{abc} \times 1001 = \overline{abc} \times 7 \times 11 \times 13
Divisibility by seven
N \to \left\lfloor \dfrac{N}{10} \right\rfloor - 2 \times (N \bmod 10)
repeat until small
Remainders & remainder theorem
Division algorithm
N = d \times q + r, \quad 0 \le r < d
Product rule
\mathrm{rem}\left(\dfrac{a \times b}{d}\right) = \mathrm{rem}\left(\dfrac{R_a \times R_b}{d}\right)
same for sums
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}
one-way rule
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}
1 if n even, d - 1 if n odd
Unit digit & cyclicity
Cyclicity rule
\text{unit}(a^n) = \text{unit}(a^r), \quad r = n \bmod 4 \ (r = 0 \Rightarrow r = 4)
Cycles of two, three, seven, eight
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
Last two digits, base ending in one
(10a + 1)^n \text{ ends in } \left[(a \cdot n) \bmod 10\right] 1
Factors, prime factorisation & trailing zeros
Number of factors
d(N) = (a + 1)(b + 1)(c + 1)
Sum of factors
\sigma(N) = (1 + p + \cdots + p^a)(1 + q + \cdots + q^b) \cdots
Even factors
a \times (b + 1)(c + 1)
when 2 has exponent a
Product of all factors
N^{d(N)/2}
Trailing zeros in n factorial
\left\lfloor \dfrac{n}{5} \right\rfloor + \left\lfloor \dfrac{n}{25} \right\rfloor + \left\lfloor \dfrac{n}{125} \right\rfloor + \cdots
Highest power of a prime in n factorial
\sum_{k \ge 1} \left\lfloor \dfrac{n}{p^k} \right\rfloor
Fractions, decimals & recurring decimals
Pure repeating decimal
0.\overline{ab} = \dfrac{ab}{99}
Mixed repeating decimal
0.a\overline{bc} = \dfrac{abc - a}{990}
Terminating test
\dfrac{p}{q} \text{ terminates} \iff q = 2^m \times 5^n
q in lowest terms