Olympiad Number Theory IV: Primitive Roots, Residues & Bounding

The olympiad move: from "$p \mid 2^n - 1$" deduce "$\text{ord}_p(2) \mid n$", intersect with "$\text{ord}_p(2) \mid p - 1$", and get $\text{ord}_p(2)\mid\gcd(n,p-1)$; since $\text{ord}_p(2)>1$ for odd $p$, $n$ and $p-1$ share a prime factor. This single argument shows $n \mid 2^n - 1$ only for $n = 1$: take the least prime $p \mid n$; then $\text{ord}_p(2)$ divides both $n$ and $p - 1$, hence is $1$, so $p \mid 1$.

LTE answers "exactly which power of $p$ divides $a^n - b^n$" in one line, replacing pages of induction. It is the tool for exponential Diophantine equations: compare the $p$-adic valuation of both sides and the equation collapses to a small inequality in $n$.

These facts prove impossibility and produce infinitely-many-primes theorems: infinitely many primes $\equiv 1 \pmod 4$, because $(n!)^2 + 1$ has a prime factor larger than $n$ and every such factor is $1 \bmod 4$. In an equation, look for a factor of the form $x^2 + c$ and ask which primes may divide it.

Size arguments finish what residues start. "$n^4 + 2n^3 + 2n^2 + 2n + 1$ is a square" — it sits strictly between $(n^2 + n)^2$ and $(n^2 + n + 1)^2$ for every $n \ge 1$ (the gaps are $n^2+2n+1$ and $n^2$), so no. The same logic for cubes and for "the product of two consecutive integers is never a perfect power". Write the two bounding expressions explicitly and verify the strict inequalities with the actual difference.

Every nonzero residue is a power of $g$, and $g^s\equiv g^{s'}$ exactly when $s\equiv s'\pmod{p-1}$, so multiplication mod $p$ becomes addition of exponents mod $p-1$. With $x=g^s$ and $a=g^t$, the congruence $x^k\equiv a$ becomes the linear congruence $ks\equiv t\pmod{p-1}$, which is solvable exactly when $e\mid t$, and then has $e$ solutions mod $p-1$. The condition $e\mid t$ is the same as $a^{(p-1)/e}=g^{t(p-1)/e}\equiv1$. For the power sums, as $x$ runs over the nonzero residues, $x^m=g^{sm}$ and the sum is the geometric series $\sum_{s=0}^{p-2}(g^m)^s$: it is $p-1\equiv-1$ if $g^m\equiv1$, i.e. $(p-1)\mid m$, and $\tfrac{g^{m(p-1)}-1}{g^m-1}\equiv0$ otherwise. The clock shows the exponent picture for $p=13$, $g=2$.

Step 1 — $2$ is a primitive root mod $13$: its powers are $1,2,4,8,3,6,12,11,9,5,10,7$, all twelve nonzero residues.

Step 2 — $x=2^s$ gives $x^3=2^{3s}$, and $3s\bmod12$ is a multiple of $3$, so the nonzero cubes are $2^0,2^3,2^6,2^9=1,8,12,5$: there are $\tfrac{12}{\gcd(3,12)}=4$ of them.

Step 3 — $5=2^9$, so $x=2^s$ with $3s\equiv9\pmod{12}$, i.e. $s\equiv3\pmod4$: $s=3,7,11$, giving $x=8,11,7$. Check: $8^3=512=39\cdot13+5$. Three solutions, as $e=\gcd(3,12)=3$ predicts.

Step 4 — mod $101$, $\gcd(3,100)=1$: cubing is a bijection, so every residue is a cube and each has exactly one cube root.

How to find it. Power questions mod $p$ are linear questions about exponents mod $p-1$; the only number that matters is $\gcd(k,p-1)$.

Step 1 — $101$ is prime and the sum runs over all nonzero residues, so the power-sum formula applies with $m=2026$.

Step 2 — $p-1=100$ does not divide $2026$ ($2026=20\cdot100+26$), so the sum is $\equiv0$.

Step 3 — the mechanism, concretely: multiplying every term by $g^{2026}$ for a primitive root $g$ only permutes the terms (as $x$ runs over residues so does $gx$), so the sum $\Sigma$ satisfies $g^{2026}\Sigma\equiv\Sigma$; and $g^{2026}=g^{26}\not\equiv1$ because the order of $g$ is $100$. Hence $\Sigma\equiv0$. The remainder is $0$.

How to find it. A sum over a complete set of nonzero residues is invariant under multiplication by any unit — the "multiply by $g$" trick is the whole proof.

Step 1 — pair $k$ with $p-k$: $\tfrac1k+\tfrac1{p-k}=\tfrac{p}{k(p-k)}$, so $2H=p\sum_{k=1}^{p-1}\tfrac1{k(p-k)}$, where $H$ is the harmonic sum. The denominators are prime to $p$, so it suffices to show $\sum_{k=1}^{p-1}\tfrac1{k(p-k)}\equiv0\pmod p$, computing with inverses mod $p$.

Step 2 — mod $p$, $k(p-k)\equiv-k^2$, so the sum is $\equiv-\sum_{k=1}^{p-1}k^{-2}$.

Step 3 — as $k$ runs over the nonzero residues so does $k^{-1}$, so $\sum k^{-2}\equiv\sum k^2=\tfrac{(p-1)p(2p-1)}{6}$, which is divisible by $p$ because $p\ge5$ does not divide $6$. (This is the power-sum formula with $m=2$ and $(p-1)\nmid2$.)

Step 4 — so $2H=p\cdot(\text{a fraction whose numerator is divisible by }p)$, and since $p$ is odd, $p^2$ divides the numerator of $H$. Check: $p=5$ gives $\tfrac{25}{12}$ and $p=7$ gives $\tfrac{49}{20}$.

How to find it. Harmonic sums mod $p$ become sums of inverses, which are sums of powers in disguise; pairing $k$ with $p-k$ extracts the first factor of $p$, and the power-sum formula supplies the second.

The count $\gcd(k,\varphi(n))$ comes from writing every unit as a power of a primitive root, and there is no primitive root mod $8$: every unit has order $1$ or $2$, so the unit group is not cyclic. Primitive roots exist only mod $1,2,4,p^k$ and $2p^k$ for odd primes $p$. Modulo a composite without one, split with the Chinese remainder theorem and count modulo each prime power separately; mod $2^k$ with $k\ge3$ the units form $\{\pm1\}\times\langle5\rangle$ rather than a cycle.

$q\mid x^2+c$ means $x^2\equiv-c\pmod q$, and $q\nmid x$ (else $q\mid c$), so $-c$ is a nonzero square mod $q$. The supplements $\left(\tfrac{-1}q\right)=(-1)^{(q-1)/2}$ and $\left(\tfrac{\pm2}q\right)$ turn that into congruence conditions on $q$. The third item is multiplicativity mod $4$. The pattern in equations: rearrange so that one side is $y^2+c$ and the other has a factor $\equiv3\pmod4$ (or another forbidden class), and the equation is impossible. The main work is finding the factor, since a factor that is $\equiv3\pmod4$ only for some values of the variable does not suffice.

Step 1 — multiply by $4$ and add $1$: $16xy-4x-4y+1=(4x-1)(4y-1)$, so the equation becomes $(4x-1)(4y-1)=4z^2+1=(2z)^2+1$.

Step 2 — $4x-1\ge3$ and $4x-1\equiv3\pmod4$, so it has a prime factor $q\equiv3\pmod4$.

Step 3 — $q$ divides $(2z)^2+1$, so $-1$ is a quadratic residue mod $q$, impossible for $q\equiv3\pmod4$.

How to find it. Simon's trick in its "multiply by $4$" form produces $(4x-1)(4y-1)$, and the right side becomes a square plus one. Once one side is $u^2+1$ and the other contains a factor $\equiv3\pmod4$, the first supplement ends the problem.

Step 1 — let $p\mid2^n+1$; $p$ is odd. Since $n$ is odd, $2^n=2\cdot\left(2^{(n-1)/2}\right)^2$, so $2\cdot u^2\equiv-1$ with $u=2^{(n-1)/2}$.

Step 2 — multiply by $2$: $(2u)^2\equiv-2\pmod p$, so $-2$ is a quadratic residue mod $p$.

Step 3 — $\left(\tfrac{-2}p\right)=\left(\tfrac{-1}p\right)\left(\tfrac2p\right)=1$ exactly when $p\equiv1$ or $3\pmod8$ (both factors $+1$ for $p\equiv1$, both $-1$ for $p\equiv3$). Examples: $2^9+1=513=3^3\cdot19$ and $2^{11}+1=2049=3\cdot683$, with $19\equiv683\equiv3\pmod8$.

How to find it. An odd power of $2$ is twice a square; that single observation converts divisibility into a residue statement about $-2$.

Step 1 — if $x$ is even, $x^3+7\equiv7\pmod8$, not a square (squares are $0,1,4\bmod8$). So $x$ is odd.

Step 2 — add $1$: $y^2+1=x^3+8=(x+2)(x^2-2x+4)$.

Step 3 — $x^2-2x+4=(x-1)^2+3$. With $x$ odd, $(x-1)^2\equiv0\pmod4$, so this factor is $\equiv3\pmod4$, and it is positive. It therefore has a prime factor $q\equiv3\pmod4$.

Step 4 — $q$ divides $y^2+1$, impossible by the first supplement. No solutions.

How to find it. $7=8-1$: adding $1$ to both sides makes the left a sum of two squares and the right a sum of two cubes, which factors. Then look for the factor whose residue mod $4$ is forced for every odd $x$.

$x+2\equiv3\pmod4$ only when $x\equiv1\pmod4$. For $x=3$, $x+2=5$, and $5$ can perfectly well divide $y^2+1$ (take $y=2$). The argument has proved nothing for half of the odd $x$. The factor to use is the one whose residue is forced for every odd $x$: $(x-1)^2+3\equiv3\pmod4$. Check the claimed congruence on a sample value from each residue class before building on it.