Skip to main content
OlympiadHQ

Browse · MathNet

Print

XVIII OBM

Brazil number theory

Problem

Let be the polynomial . Let denote . Show that there is an integer such that is divisible by for all integers .
Solution
We have . Since is prime, or .

Completing squares, we have By the quadratic reciprocity law, , so is not a quadratic residue modulo . Thus Thus , which means that admits an inverse function.

To finish the problem, fix and consider . Since there are infinite numbers and remainders, there are and such that and . So for each there is a positive integer such that . Choose and we are done.

Techniques

Quadratic residuesQuadratic reciprocityPolynomials mod pPigeonhole principle