Remainders & Remainder Theorems

At a glance 12 formulas

1. 1Division rule$N = dq + r,\quad 0 \le r < d$
2. 2Work with remainders$a \equiv r,\ b \equiv s \Rightarrow ab \equiv rs$$a + b \equiv r + s,\quad a^{n} \equiv r^{n}$
3. 3Negative remainders$a \equiv -1 \pmod d \Rightarrow a^{n} \equiv (-1)^{n}$$\text{a remainder of } {-r} \text{ means } d - r$
4. 4Remainder on a factorIf $N$ leaves $r$ when divided by $d$, and $f$ divides $d$, then $N$ leaves the remainder of $r$ by $f$: 47 by 60 means 11 by 12.
5. 5Digit remaindersRemainder by 9 (or 3) is the digit sum's remainder; by 4 or 8, the last 2 or 3 digits'; by 11, the alternating digit sum's, counted from the units digit.
6. 6Same remainder, many divisors$N = k \cdot \text{LCM}(a, b, c) + r$$\text{same shortfall } g\text{: } N = k \cdot \text{LCM} - g$
7. 7Power that leaves ±1$a^{k} \equiv 1 \Rightarrow a^{n} \equiv a^{\,n \bmod k}$$a^{k} \equiv -1 \Rightarrow a^{2k} \equiv 1$
8. 8Fermat's little theorem$a^{p-1} \equiv 1 \pmod p$$p \text{ prime},\ p \nmid a$
9. 9Sums of powers$(a + b) \mid a^{n} + b^{n} \text{ for odd } n$$(a - b) \mid a^{n} - b^{n} \text{ for every } n$
10. 10Twice the numberIf $N$ leaves $r$ and $2N$ leaves $s$ on division by the same $d$, then $d$ divides $2r - s$, and $d$ is more than $r$.
11. 11Cancel a common factorIf the number and the divisor share a factor $k$, cancel it, find the remainder, then multiply that remainder back by $k$.
12. 12Split the divisorFor a big divisor, split it into co-prime parts, like 7 and 9 for 63, find the remainder by each, then pick the number below the divisor that fits both.