Advanced NT + Abstract: LTE + Orders + Burnside

LTE, odd prime case: if $p \mid a - b$ but $p \nmid a, b$, then $v_p(a^n - b^n) = v_p(a - b) + v_p(n)$. Read it as a conservation law: the base contributes its valuation once, and only the $p$-part of the EXPONENT can add more. The sum form ($a^n + b^n$, $n$ odd, $p \mid a+b$) is the same statement through $b \mapsto -b$. Proof skeleton worth owning: factor $a^n - b^n = (a-b)(a^{n-1} + \cdots + b^{n-1})$, show the second factor is $\equiv n a^{n-1} \pmod{p}$... and induct on $v_p(n)$ via $a^{pm} - b^{pm} = (a^m)^p - (b^m)^p$.

The $p = 2$ case is the famous trap and carries its own formula: for even $n$ and odd $a, b$, $v_2(a^n - b^n) = v_2(a - b) + v_2(a + b) + v_2(n) - 1$ — BOTH $a - b$ and $a + b$ contribute, because $a^2 \equiv b^2 \pmod 8$ for all odd $a, b$. Every LTE write-up must either avoid $p = 2$ visibly or use the even formula; graders know exactly where this body is buried.

Recognition: any 'find all $n$ such that $p^k \mid a^n - 1$', 'show $n \mid$ [exponential expression]', or Zsygmondy-adjacent divisibility. LTE pairs with orders: the order tells you WHICH $n$ make $p$ divide at all ($d \mid n$), and LTE tells you HOW MUCH $p$ divides once it does. That two-step — order for entry, LTE for depth — resolves most exponential-divisibility problems completely.

Pitfall. Applying odd-prime LTE at $p = 2$, or forgetting the hypothesis $p \mid a - b$ (for the difference form) entirely. Check 'does $p$ divide the base combination' FIRST — without it, the order of $a/b$ decides whether $p$ divides at all, and LTE says nothing.

The theorem: $(\mathbb{Z}/p)^*$ is cyclic for every prime $p$ — some $g$ has order exactly $p - 1$, and then $g^0, g^1, \dots, g^{p-2}$ enumerate all nonzero residues. (Cyclicity also holds mod $p^k$ and $2p^k$ for odd $p$, and fails mod $2^k$ for $k \ge 3$ — file the boundary.) The proof idea to own: count elements of each order using $x^d = 1$ having at most $d$ roots in a field, and the divisor-sum identity $\sum_{d \mid n} \varphi(d) = n$ forces exactly $\varphi(p-1)$ generators.

What cyclicity BUYS: every multiplicative question becomes additive in the exponent. 'How many $k$-th powers mod $p$?' — writing $x = g^t$, the $k$-th powers are $g^{kt}$, i.e. exponents in $k\mathbb{Z}/(p-1)$: exactly $\frac{p-1}{\gcd(k, p-1)}$ of them, each with $\gcd(k, p-1)$ preimages. Sums like $\sum_x x^k \pmod p$ collapse the same way: it is a geometric series in $g^k$, equal to $-1$ if $(p-1) \mid k$ and $0$ otherwise — a two-case fact that quietly powers dozens of problems.

Euler's criterion, revisited from Week 17, is the $k = 2$ shadow of all this: squares are the even-exponent half of the cycle. The general habit: whenever a problem quantifies over all nonzero residues mod $p$ with multiplicative structure, INTRODUCE $g$ and translate to exponent arithmetic mod $p - 1$; the translation is lossless and usually decisive.

Pitfall. Translating to exponents and then doing arithmetic mod $p$ instead of mod $p - 1$. Exponents live in $\mathbb{Z}/(p-1)$; residues live in $\mathbb{Z}/p$ — mixing the two moduli is the classic primitive-root error.

Burnside (Cauchy-Frobenius): when a finite group $G$ acts on a set $X$, the number of orbits is $\frac{1}{|G|}\sum_{g \in G} |\mathrm{Fix}(g)|$ — the AVERAGE number of fixed points. 'Necklaces up to rotation', 'colorings of a cube up to rotation', 'distinct configurations up to symmetry': all are orbit counts, and Burnside converts each into a finite checklist — one fixed-point count per group element, where elements of the same TYPE (same cycle structure) contribute identically, so the checklist has as few lines as the group has conjugacy classes.

The fixed-point counts follow one rule: a coloring is fixed by $g$ iff it is constant on every cycle of $g$, so $|\mathrm{Fix}(g)| = c^{(\text{number of cycles of } g)}$ for $c$ colors. For rotations of an $n$-cycle, rotation by $j$ has $\gcd(j, n)$ cycles — hence the necklace formula $\frac{1}{n}\sum_{j} c^{\gcd(j,n)} = \frac{1}{n}\sum_{d \mid n} \varphi(n/d)\, c^{d}$. Dihedral (allow flips) adds the reflection classes: for odd $n$, each reflection has $\frac{n+1}{2}$ cycles; for even $n$, the two reflection types have $\frac{n}{2} + 1$ and $\frac{n}{2}$.

Proof idea worth one read: double-count pairs $(g, x)$ with $gx = x$ — grouping by $g$ gives $\sum |\mathrm{Fix}(g)|$; grouping by $x$ gives $\sum |G_x| = \sum_{\text{orbits}} |G|$ by orbit-stabilizer. Burnside IS orbit-stabilizer plus double counting: two Week 3 ideas wearing a group. If the lemma's statement ever deserts you mid-exam, this derivation rebuilds it in five lines.

Pitfall. Averaging over the wrong group — counting flips as distinct but including reflections in the sum (or vice versa). Write down WHICH symmetries the problem identifies before summing; rotation-only ($C_n$) and rotation-plus-flip ($D_n$) differ, and the problem statement always picks one.