Number Theory

Last two digits of $3^{2026}$: the order of $3$ mod $100$ is $20$, and $2026 \equiv 6$, so $3^6 = 729 \to 29$. Mod $2^k$ ($k \ge 3$) the equation $x^2 \equiv 1$ has FOUR solutions, so $x^2 \equiv 1 \pmod{24}$ has $4\cdot2 = 8$ — a standard trap. Primitive roots exist exactly mod $2, 4, p^k, 2p^k$.

$v_5(1000!) = 200 + 40 + 8 + 1 = 249$. $v_2\binom{2026}{1013}$ is the number of $1$-bits of $1013$. LTE: $v_3(2^{243} + 1) = 1 + 5 = 6$ (the $a^n + b^n$ form for odd $n$). Valuations turn "largest power dividing" into arithmetic, and they are the language of most Putnam number theory write-ups.

Sums over divisors are attacked by swapping the order of summation: $\sum_{n\le N}\tau(n) = \sum_{d\le N}\lfloor N/d\rfloor$. Möbius inversion recovers $f$ from $F(n) = \sum_{d\mid n}f(d)$. Quadratic residues: $\left(\tfrac{-1}{p}\right) = (-1)^{(p-1)/2}$, $\left(\tfrac{2}{p}\right) = 1$ iff $p \equiv \pm1 \pmod 8$, and reciprocity for the rest.

Kummer: count carries adding $50 + 50$ in base $2$. $50 = 110010_2$; doubling a binary number produces one carry per $1$-bit, and $50$ has three $1$-bits: $k = 3$. (Legendre confirms: $v_2(100!) - 2v_2(50!) = 97 - 2\cdot47 = 3$.)

Two lemmas. (i) If $p \nmid n$ then $v_p(a^n - b^n) = v_p(a - b)$: since $a^n - b^n = (a - b)\sum a^{n-1-i}b^i$ and the sum is $\equiv na^{n-1} \not\equiv 0 \pmod p$. (ii) $v_p(a^p - b^p) = v_p(a - b) + 1$: write $a = b + kp^t$ and expand $a^p$ binomially — the terms beyond the first two carry extra factors of $p$, and the $\binom p2$ term supplies exactly one more (this is where $p$ odd is used). Induct on $v_p(n)$, peeling off one factor of $p$ at a time with (ii) and finishing with (i). $\blacksquare$ Significance: LTE is the exact accounting of how a prime divides a difference of powers — it replaces pages of casework in olympiad and Putnam solutions alike.

Sort the fractions $\tfrac1n, \tfrac2n, \ldots, \tfrac nn$ by their reduced denominator $d$ (a divisor of $n$). Exactly $\varphi(d)$ of them reduce to denominator $d$ (the numerators coprime to $d$). Summing over $d$ counts all $n$ fractions. $\blacksquare$ Significance: the argument proves more — that the multiplicative group mod $p$ is cyclic (count elements by order, compare with $\sum\varphi(d) = p - 1$), i.e. primitive roots exist.

Step 1 — $1000 = 8\cdot125$; the order mod $1000$ is the lcm of the orders mod $8$ and mod $125$.

Step 2 — mod $8$: $3^2 = 9 \equiv 1$, order $2$.

Step 3 — mod $125$: $\varphi(125) = 100$, so the order divides $100$; test the maximal proper divisors $50$ and $20$. $3^{20} \equiv 1 + 20\cdot\ldots$ — compute: $3^5 = 243 \equiv -7$, $3^{10} \equiv 49$, $3^{20} \equiv 49^2 = 2401 \equiv 26 \ne 1$; $3^{50} = (3^{10})^5 \equiv 49^5$, and $49^2 \equiv 26$, $49^4 \equiv 26^2 = 676 \equiv 51$, $49^5 \equiv 51\cdot49 = 2499 \equiv -1 \ne 1$. So the order mod $125$ is $100$.

Step 4 — $\mathrm{lcm}(2, 100) = 100$. The method: never search; use $\varphi$ to list candidates and test only the maximal proper divisors.

Step 1 — squeeze between consecutive squares: for $n \ge 1$, $(n + 1)^2 = n^2 + 2n + 1 < n^2 + 3n + 5$ and $(n + 2)^2 = n^2 + 4n + 4 > n^2 + 3n + 5$ iff $n > 1$.

Step 2 — so for $n \ge 2$ the expression lies strictly between two consecutive squares: never a square.

Step 3 — check $n = 1$: $1 + 3 + 5 = 9 = 3^2$ ✓. Answer: only $n = 1$. Bounding by neighboring squares (or cubes) is the first thing to try on "when is this polynomial a perfect power."