Injectivity of $x^3+x \bmod n$ Let $$f_n:\mathbb{Z}/n\mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z}, x \mapsto x^3+x \bmod n$$
where $n\in\mathbb{N}$. Now if $f$ is not injective i.e. there exist $a\neq b \in \mathbb{Z}/n\mathbb{Z}$ s.t. $$a^3+a=b^3+b \bmod n \qquad \text{or} \qquad (a-b)(a^2+ab+b^2+1)=0 \bmod n$$
then $f_{kn}$ is also not injective for any integer $k$. How can you show it?
 A: Let $f(x)=x^3+x$. With respect to each and every modulus $n>1$ it gives rise to a function $f_n:\Bbb{Z}_n\to\Bbb{Z}_n$. If $P(n)$ is the predicate: "$f_n$ is not injective", then the question is about proving the implication:
$$P(n)\implies P(kn)\ \text{for all integers $k>1$}.$$
So we assume $P(n)$. In other words, there exist integers $a$ and $b$, $0\le a<b<n$, such that $f(a)\equiv f(b)\pmod n$. Let $m$ be the common remainder modulo $n$.
Let $k>1$. Consider the $2k$ inputs $a_i=a+in$, $b_i=b+in$, $i=0,1,\ldots, k-1$. For all $i$ we have
$$
f(a_i)\equiv f(a)\equiv m\pmod n
$$
as well as
$$f(b_i)\equiv f(b)\equiv m\pmod n.$$
It follows that modulo $kn$ all the outputs $f(a_i), f(b_i)$, $i=0,1,\ldots,k-1$, are among the numbers $m_j=m+jn$, $j=0,1,\ldots,k-1$. This is because any integer congruent to $m$ modulo $n$ is congruent to exactly one of the $m_j$s modulo $kn$.
That is, we have $2k$ pigeons $f(a_i), f(b_i)$, flying into $k$ pigeonholes $m_j$.
By the pigeonhole principle at least two pigeons fly into the same hole. In other words $f_{kn}$ is not injective either.
