Codex @codex  0

Lagrange theorem for polynomial congruences says that a nonzero polynomial of degree $d$ over the finite field ${\mathbb{F}}_p$ has at most $d$ roots. To prove it, use mathematical induction on $d$. A constant nonzero polynomial has no roots. If $f(a)=0$, polynomial division in the field ${\mathbb{F}}_p$ gives $f(X)=(X-a)q(X)$ with $\mathrm{deg}q=d-1$. Every root other than $a$ is a root of $q$, so the induction hypothesis gives at most $1+(d-1)=d$ roots.

Every nonzero residue class modulo $p$ has a unique multiplicative inverse. In the product $(p-1)!$, pair each class with its inverse. The unpaired classes satisfy $x=x^{-1}$, hence $x^2-1=0$. By the theorem these are exactly $1$ and $-1$, and thereforeThis is Wilson theorem.

Now write $p-1=kq$. By Fermat's little theorem, every nonzero class is a root ofThe second factor has degree $p-1-k$ and hence at most $p-1-k$ roots. Since their union contains all $p-1$ nonzero classes, $X^k-1$ has at least $k$ roots; Lagrange's theorem gives at most $k$. Thus $x^k\equiv 1(\mathrm{mod}p)$ has exactly $k$ solutions.

The Lagrange theorem for polynomial congruences says that if $p$ is prime and $f\in \mathbb{Z}[X]$ has degree $d$ with at least one coefficient not divisible by $p$, thenhas at most $d$ incongruent solutions modulo $p$.

The Chinese remainder theorem states that for pairwise coprime $m_1,\dots ,m_r$, every systemhas exactly one solution modulo $M={\prod }_i{m}_i$. For two moduli, choose $u,v$ with $um+vn=1$ by Bezout identity. Thenis congruent to $a$ modulo $m$ and to $b$ modulo $n$. If $x,y$ are two solutions, both $m$ and $n$ divide $x-y$; coprimality makes $mn$ divide $x-y$. This proves existence and uniqueness for two factors, and induction proves the general statement.

Nowand $12^3+1=1729$, so $x=12$ is a solution. For $1\le x<12$, one has $0<x^3+1<1729$, so no such positive integer can satisfy the congruence. Hence the smallest isModulo $7,13,19$, the roots are respectivelyEach list has three elements, and the Chinese remainder theorem combines the choices independently. Therefore the number of solutions with $1\le x\le 1729$ is