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.

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."

Step 1 — $1024 = 2^{10}$, and differences of squares factor repeatedly: $3^{2^{m}} - 1 = \left(3^{2^{m-1}} - 1\right)\left(3^{2^{m-1}} + 1\right)$. Unwinding, $3^{1024} - 1 = (3 - 1)(3 + 1)(3^2 + 1)(3^4 + 1)\cdots(3^{512} + 1)$.

Step 2 — the $2$-adic valuations: $3 - 1 = 2$ contributes $1$, and $3 + 1 = 4$ contributes $2$. For $j \ge 1$, $3^{2^j}$ is an odd square, hence $\equiv 1 \pmod 8$, so $3^{2^j} + 1 \equiv 2 \pmod 8$ contributes exactly $1$; there are nine such factors ($j = 1, \ldots, 9$).

Step 3 — total: $1 + 2 + 9 = 12$. So $k = 12$. In general $v_2\left(3^{2^m} - 1\right) = m + 2$, the $p = 2$ case of lifting the exponent: $v_2(x^n - y^n) = v_2(x - y) + v_2(x + y) + v_2(n) - 1$ for odd $x, y$ and even $n$.

How to find it. An exponent that is a power of $2$ invites repeated difference-of-squares factoring; then each factor's power of $2$ is read off mod $8$. The odd-prime LTE formula from the Proofs section fails at $p = 2$ — this is the corrected version, with the extra $v_2(x + y) - 1$.