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.

Squares are $0$ or $1 \bmod 4$, so $x^2 + y^2 \in \{0, 1, 2\} \bmod 4$ — never $3$. Done in one line; the same idea shows no integer of the form $4k + 3$ is a sum of two squares.

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.