Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 1I (Number Theory)

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