Section 31.2

Modular Arithmetic

Remainders, Chinese-remainder puzzles, the Frobenius coin problem, modular exponentiation, casting out nines, card-shuffle periods.

Toolkit

Modular arithmetic reduces a problem to behaviour of residues under addition, multiplication and exponentiation; use it whenever only remainders, final digits, or cyclic structure matter.

$a\equiv b\pmod n \Rightarrow a^k\equiv b^k\pmod n$ ; find the order of a base (smallest $k$ with $a^k\equiv \pm1$ ) to collapse huge exponents.
CRT: a system $x\equiv r_i\pmod{m_i}$ with pairwise coprime $m_i$ has a unique solution mod $\prod m_i$ ; if each $r_i = m_i-1$ , then $x+1$ is divisible by $\operatorname{lcm}(m_i)$ .
Frobenius (two coprime denominations $a,b$ ): largest non-representable integer is $ab-a-b$ ; every residue class mod $a$ has a least representable element that is a multiple of $b$ .
Bezout: if $\gcd(a,b)=1$ , solutions to $ax+by=c$ are $x=x_0+bt,\ y=y_0-at$ for $t\in\mathbb{Z}$ , $t$ chosen to normalise a solution into a required range.
A number $\equiv$ its digit sum mod $9$ (casting out nines) and $\equiv$ alternating digit sum mod $11$ .
$999=27\cdot37$ , so cyclic shifts of 3-digit blocks preserve divisibility by $37$ (and by $27$ , $3$ , $9$ ).
A permutation’s period is the lcm of its cycle lengths; a riffle shuffle acting by $x\mapsto 2x \bmod (n+1)$ has period $\operatorname{ord}_{n+1}(2)$ .

Problems