Remainders by Congruence & Cyclicity

Write $a \equiv b \pmod n$ to mean $n \mid (a-b)$, that is $a$ and $b$ leave the same remainder.

• If $a\equiv a'$ and $b\equiv b'$ then $a+b\equiv a'+b'$, $a-b\equiv a'-b'$ and $ab\equiv a'b'$.
• In particular $a^{k} \equiv (a')^{k}$, which is what licenses reducing the base first.
• Division is NOT allowed in general — you may not cancel a factor from both sides without checking it is coprime to the modulus.
• The final answer must be brought into the range $0$ to $n-1$.

If $a \equiv -1 \pmod n$ — that is, $a = n-1$ or any number one less than a multiple of $n$ — then

• Look for it whenever the base is just under the modulus (17 and 18, 65 and 11 since $65 = 66-1$, $p$ and $p+1$).
• It pairs beautifully with a sum: if $a\equiv-1$ and $b\equiv+1$, then $a^{k}+b^{k}\equiv 0$ for odd $k$.
• Also check $a \equiv +1$, which is even simpler: every power is 1.

Compute $a^{1}, a^{2}, a^{3},\ldots$ modulo $n$ until a value repeats. If $a^{t}\equiv 1$, the cycle length is $t$ and

• Look for a small power that is $\pm 1$; that shortcut usually appears within four or five steps ($3^3 = 27 \equiv -1 \bmod 28$, $2^3 = 8 \equiv 1 \bmod 7$).
• Finding $a^{t}\equiv -1$ is just as useful: the cycle is then $2t$.

Fermat's little theorem. If $p$ is prime and $p \nmid a$, then

• Multiplying by $a$ gives the companion form $a^{p}\equiv a \pmod p$, valid for every $a$ including multiples of $p$.
• It requires the modulus to be prime: $3^{3}-1 = 26$ is not a multiple of 4, so the statement fails at $p=4$.
• It explains why $n^{5}-n$ is always divisible by 5, and $n^{p}-n$ by $p$.

If $a+b \equiv 0 \pmod n$ — that is, $b \equiv -a$ — then for odd $k$,

• Scan the bases for pairs summing to $n$ (or to a multiple of $n$).
• The exponent must be odd; for even $k$ the pair doubles instead of cancelling.
• More generally, reduce every base and look for any structure — equal residues in a difference cancel too, which is why $27^{27}-15^{27}$ is 0 modulo 6.

Given $m \equiv r_1$ and $n \equiv r_2 \pmod d$:

• $m+n \equiv r_1+r_2$;
• $m-n \equiv r_1-r_2$, and if that is negative add $d$;
• $mn \equiv r_1 r_2$;

then reduce into $0$ to $d-1$. Note that $m>n$ does not imply $r_1>r_2$ — the difference's remainder is determined by the residues, not by which number is bigger.