BdMO Online Forum

Let $n$ be a positive integer. Prove that there exist integers $b_1, b_2, ... , b_n$ such that for any integer $m$, the number $$(\ldots (((m^2 + b_1)^2 +b_2)^2 + \ldots)^2 + b_{n-1})^2 + b_n$$ is divisible by $2n-1$.

Notice that we can have at most $n$ different quadratic residue modulo $2n-1$. Let $S=\{[a_1],[a_2],\dots,[a_k]\}$ be our complete set of quadratic residue classes modulo $2n-1$. Now we have a algorithm to find the values of $b_i$s.
Now, $m^2\in S$. Let's choose our $b_1$ such that $b_1\equiv-(a_1+a_2)\cdot n\pmod{2n-1}$
Why? See that if we choose $b_1$ in this way, then $(a_1+b)\equiv-(a_2+b)\pmod{2n-1}$ or, $(a_1+b)^2\equiv(a_2+b)^2\pmod{2n-1}$ [Also remark that $n$ is the inverse of $2$ modulo $2n-1$].
By following this method, now the number of possible residue classes the number $(m^2+b_1)^2$ can be in, has decreased by at least one. Now take the set of all possible residue classes of $(m^2+b_1)^2$, let's say $S_1=\{[c_1],[c_2],\dots,[c_l]\}$ and choose $b_2\equiv-(c_1+c_2)\cdot n\pmod{2n-1}$.
By following the same algorithm for $b_3,b_4,\dots,b_{n-1}$, we can always decrease the possible set of residue classes by at least $1$. After choosing $b_1,b_2,\dots,b_{n-1}$, we are left with at most $1$ possible residue class $[r]$ and choosing $b_n\equiv-r\pmod{2n-1}$ will do our job.

We have the following claim.
Claim : For some subset of the quadratic residue set $a^2$ (mod $2n-1$), we can pick $b_i$ such that the number of all possible values of $(a^2 + b_i)^2$ (mod $2n-1$) has decreased by at least $1$.
Proof : Let $m_1, m_2$ be such that $m_1^2$ and $m_2^2$ are not same modulo $2n - 1$ i.e. $ m_1^2 \not \equiv m_2^2$ (mod $2n - 1$). Pick $$b_i \equiv -2^{-1}(m_1^2 + m_2^2)$$ (mod $2n - 1$).
It is easy to check that $(m_1^2 + b_i)^2 \equiv (m_2^2 + b_i)^2$ (mod $2n - 1$), thus prove our claim.

It is easy to verify that there are at most $n$ quadratic residues modulo $2n - 1$. We can pick appropriate $b_i$'s to reach $$(\ldots(((m^2 + b_1)^2 + b_2)^2 + \ldots)^2 + b_{n-1})^2 + b_n \equiv 0$$ (mod $2n - 1$)
for all $m$ and we are done.