# Injective integer polynomial is injective modulo some prime

Let $$Q\in \mathbb{Z}[x]$$ be a polynomial defining an injective function $$\mathbb{Z}\to\mathbb{Z}$$. Does it define an injective function $$\mathbb{Z}/p\mathbb{Z}\to\mathbb{Z}/p\mathbb{Z}$$ for some prime $$p$$?

Consider $$Q(x)=x(2x-1)(3x-1)$$. This gives an injective map $$\mathbb Z\to \mathbb Z$$, because $$n. However, this $$Q$$ is not injective over $$\mathbb Z/p\mathbb Z$$ for any $$p$$ because $$Q(x)=0$$ has three solutions when $$p\geq 5$$ and two solutions when $$p\in \{2,3\}$$.

While the original question has been answered, there is a beautiful result of Fried in On a conjecture of Schur which is relevant to such questions. Suppose $$Q$$ is a polynomial in $${\Bbb Q}[x]$$ such that for infinitely many primes the induced map from $${\Bbb Z}/p{\Bbb Z}$$ to $${\Bbb Z}/p{\Bbb Z}$$ is bijective. Then $$Q$$ must be of the form

(i) $$Q(x) = ax^n + b$$,

or

(ii) $$Q(x) = T_n(x)$$, where $$T_n(x)$$ denotes the $$n$$-th Chebyshev polynomial,

or

(iii) Compositions of functions of this type.

This established an old conjecture of Schur. See also the account Turnwald - On Schur's conjecture, which discusses the history of the problem, and gives a detailed proof, correcting inaccuracies in the earlier literature.

• how does a polynomial with rational coefficients induce a map $\mathbb{Z}/p\mathbb{Z}\to\mathbb{Z}/p\mathbb{Z}$? – user158636 Aug 9 at 19:29
• Just take the primes not dividing denominators of coefficients and reduce. – Lucia Aug 9 at 19:30
• That is to say, part of the quantification is "for infinitely many primes $p$, there is an induced self-map of $\mathbb Z/p\mathbb Z$ and it is bijective". (Of course, the first condition throws away only finitely many primes.) – LSpice Aug 9 at 19:53