Modular arithmetic
Remainders, of negative numbers too, the inverse modulo m, linear congruences, large powers by Fermat's little theorem and systems of congruences.
How to solve it
In modular arithmetic numbers live on a clock face: after $m - 1$ comes $0$ again. Adding, subtracting and multiplying can be done with the remainders straight away — the result is the same. Dividing works only by numbers that have an inverse, that is, coprime to the modulus.
Step by step
- A remainder is a number from $0$ to $m - 1$. For a negative number find the nearest multiple of $m$ below: $-36 = 24 \cdot (-2) + 12$.
- The inverse of $a$ modulo $m$: the Euclidean algorithm for $a$ and $m$, then back-substitution to write $1$ through $a$ and $m$. The coefficient of $a$ is the inverse.
- A congruence $ax + b \equiv c \pmod m$: move $b$ across and multiply both sides by the inverse of $a$.
- A large power modulo a prime $p$: by Fermat's little theorem $a^{p-1} \equiv 1$, so the exponent can be reduced modulo $p - 1$.
Common mistakes
- Giving a negative remainder: $-36 \bmod 24$ is $12$, not $-12$.
- “Dividing” a congruence by a number not coprime to the modulus: $6x \equiv 4 \pmod{10}$ cannot simply be divided by $6$.
- Reducing the exponent modulo $p$ instead of $p - 1$.
- Not checking the inverse: $a \cdot a^{-1}$ must leave the remainder $1$.