Olympiad Number Theory II: Residues, Diophantine Equations & Factorials

Eleven odd primes up to $100$ have $-1$ as a residue — exactly the primes that are sums of two squares (Fermat). Quadratic reciprocity $\left(\tfrac pq\right)\left(\tfrac qp\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$ then decides every $\left(\tfrac ap\right)$ by a Euclid-like descent. Olympiad use: showing an equation like $x^2 + 1 \equiv 0 \pmod p$ has no solution for $p \equiv 3 \pmod 4$ kills whole families of Diophantine equations mod a well-chosen prime.

$x^2 - y^2 = 2025 = 3^4\cdot5^2$: $\tau = 15$, so $7$ solutions (the factorization $45\cdot45$ gives $y = 0$ and is excluded). For even $N$ both factors must be even, so $N \equiv 2 \pmod 4$ has NO solutions — the standard parity obstruction. Every "sum/difference of squares" count is a divisor count in disguise.

The smallest $n$ with at least $30$ trailing zeros is $125$ ($v_5$ leaps from $28$ at $124$ to $31$). Euler plus CRT computes huge powers modulo composites: $2^{100} \equiv 1 \pmod{125}$ and $\equiv 0 \pmod 8$ give $2^{100} \equiv 376 \pmod{1000}$. Wilson's theorem $(p-1)! \equiv -1$ handles factorials modulo primes; pairing each residue with its inverse is the proof.

What is true: $n$ is a sum of two squares iff every prime $\equiv3\pmod4$ appears in $n$ to an even power. The argument behind it shows where the parity comes from: if $q\equiv3\pmod4$ divides $x^2+y^2$, then $q\mid x$ and $q\mid y$ (otherwise $-1\equiv(x/y)^2$ would be a residue mod $q$), so $q^2$ divides $x^2+y^2$ and one can divide out. Primes $\equiv3\pmod4$ are not forbidden; they must come in pairs.

The multiplicative group mod $p$ is cyclic of order $p - 1$ with generator $g$; write $a = g^k$. Then $a^{(p-1)/2} = g^{k(p-1)/2}$, which is $1$ iff $(p - 1) \mid k\tfrac{p-1}{2}$ iff $k$ is even iff $a$ is a square ($a = (g^{k/2})^2$). Since $a^{p-1} = 1$, the value $a^{(p-1)/2}$ is a square root of $1$, hence $\pm1$. $\blacksquare$ The first supplement follows immediately: $(-1)^{(p-1)/2} = 1$ iff $\tfrac{p-1}{2}$ is even iff $p \equiv 1 \pmod 4$.

In the product $1\cdot2\cdots(p-1)$, pair each residue with its multiplicative inverse mod $p$. A residue is its own inverse iff $x^2 \equiv 1$ iff $x \equiv \pm1$ (a polynomial of degree $2$ over a field has at most $2$ roots). All other residues pair off into products $\equiv 1$, leaving $1\cdot(p-1) \equiv -1$. $\blacksquare$ Significance: the converse holds too ($n$ composite $\Rightarrow (n-1)! \equiv 0$ for $n > 4$), so Wilson characterizes primes — and the pairing trick reappears in every "product of all elements of a group" problem.

Step 1 — $(x - y)(x + y) = 720$ with both factors of the SAME parity; since $720$ is even, both must be even.

Step 2 — write $x - y = 2d$, $x + y = 2e$: $de = 180$ with $d < e$.

Step 3 — $180 = 2^2\cdot3^2\cdot5$ has $\tau = 18$ divisors, so $9$ pairs with $d < e$ (no square root since $180$ is not a square).

Step 4 — each gives $x = d + e$, $y = e - d > 0$: nine solutions. The parity step is where most attempts go wrong — an odd-times-even factorization of $720$ gives non-integer $x, y$.

Step 1 — the powers of $2$ mod $7$ cycle: $2, 4, 1, 2, 4, 1, \ldots$ (the order of $2$ mod $7$ is $3$).

Step 2 — so $2^n \bmod 7 \in \{1, 2, 4\}$ and $2^n + 1 \bmod 7 \in \{2, 3, 5\}$ — never $0$. $\blacksquare$

Step 3 — the general principle: $p \mid 2^n + 1$ requires $2^{2n} \equiv 1$ but $2^n \not\equiv 1$, i.e. the order of $2$ mod $p$ is exactly $2\cdot(\text{something dividing } n)$ — an EVEN order. Mod $7$ the order is $3$, odd: impossible. This "order must be even" lemma settles every $a^n + 1$ divisibility question.

Step 1 — Wilson: $(p-1)!\equiv-1\pmod p$.

Step 2 — split the product: the second half is $\tfrac{p+1}2,\dots,p-1$, which modulo $p$ are $-\tfrac{p-1}2,\dots,-1$. So $(p-1)!\equiv\left(\tfrac{p-1}2\right)!\cdot(-1)^{(p-1)/2}\left(\tfrac{p-1}2\right)!$.

Step 3 — $\tfrac{p-1}2$ is even because $p\equiv1\pmod4$, so the sign is $+1$ and $\left(\left(\tfrac{p-1}2\right)!\right)^2\equiv-1$. Example: $p=13$, $6!=720=55\cdot13+5$, and $5^2=25\equiv-1\pmod{13}$.

How to find it. Wilson's product of all residues is the square of the half-product up to the sign $(-1)^{(p-1)/2}$. This gives a constructive proof of the first supplement ($-1$ is a residue for $p\equiv1\pmod4$), which the next problem turns into sums of two squares.

Step 1 — by the previous example there is an integer $c$ with $c^2\equiv-1\pmod p$.

Step 2 — Thue's lemma: let $m=\lfloor\sqrt p\rfloor$, so $m<\sqrt p<m+1$ ($p$ is not a square). Consider the $(m+1)^2>p$ numbers $cx-y$ with $0\le x,y\le m$. By pigeonhole two of them agree mod $p$: $cx_1-y_1\equiv cx_2-y_2$. Put $x=x_1-x_2$, $y=y_1-y_2$; then $cx\equiv y\pmod p$, $|x|,|y|\le m<\sqrt p$, and $(x,y)\ne(0,0)$ (if $x=0$ then $y\equiv0$ and $|y|<p$ force $y=0$, and the two pairs would coincide).

Step 3 — then $y^2\equiv c^2x^2\equiv-x^2$, so $p\mid x^2+y^2$.

Step 4 — size: $0<x^2+y^2<2p$, so $x^2+y^2=p$. Example: $p=13$, $c=5$, $m=3$: $x=1$ gives $cx\equiv5$, too large, but $x=2$ gives $10\equiv-3$, so $(x,y)=(2,-3)$ and $13=2^2+3^2$.

How to find it. "$p$ divides $x^2+y^2$ with $x,y$ small" is the goal, and a square root of $-1$ gives the divisibility for free along the line $y\equiv cx$. Pigeonhole finds a short vector on that line, and "divisible by $p$ and less than $2p$" pins the value.