Olympiad Number Theory

The order of $a$ mod $n$ divides $\varphi(n)$ and divides any $k$ with $a^k \equiv 1$. Use CRT to compute orders mod composite numbers: $\mathrm{ord}_{1000}(3) = \mathrm{lcm}(\mathrm{ord}_8, \mathrm{ord}_{125}) = \mathrm{lcm}(2, 100) = 100$. A primitive root exists mod $p$, $p^k$, $2p^k$ — and its existence converts multiplicative questions into additive ones on exponents.

For odd prime $p \mid a - b$, $p \nmid ab$: $v_p(a^n - b^n) = v_p(a - b) + v_p(n)$; for $p \mid a + b$ and odd $n$: $v_p(a^n + b^n) = v_p(a + b) + v_p(n)$. The $p = 2$ case adds $v_2(a + b) - 1$ for even $n$. Example: $v_3(2^{243} + 1) = 1 + 5 = 6$. LTE turns "how many times does $p$ divide" into arithmetic.

For a symmetric quadratic Diophantine equation, take the solution with $a + b$ minimal; Vieta gives a second root $a' = kb - a$ that yields a smaller solution unless a boundary case holds — which then proves the required structure. The IMO 1988 classic: $\tfrac{a^2 + b^2}{ab + 1} = k$ forces $k$ to be a perfect square.