Problem 1352

1. Factorization and Prime Factorization:
We start by factoring the given polynomial:
$$n^6 + 31n^4 - 900 = (n^2 - 5)(n^2 + 6)(n^2 + 30)$$
Next, we note the prime factorizations:
$$2009 = 7^2 \cdot 41, \quad 2010 = 2 \cdot 3 \cdot 5 \cdot 67, \quad 2011 \text{ is a prime}$$
Therefore,
$$2009 \cdot 2010 \cdot 2011 = 2 \cdot 3 \cdot 5 \cdot 7^2 \cdot 41 \cdot 67 \cdot 2011$$

2. **Handling Divisibility by $2 \cdot 3 \cdot 5$:**
We choose $n \equiv 0 \pmod{30}$. This ensures that $n$ is divisible by $2, 3,$ and $5$.

3. **Handling Divisibility by $7^2$:**
We need $n$ such that $n^2 + 6 \equiv 0 \pmod{49}$. This implies:
$$n^2 \equiv -6 \pmod{49}$$
We find that $n \equiv 22 \pmod{49}$ works because:
$$22^2 = 484 \equiv -6 \pmod{49}$$

4. **Handling Divisibility by $41, 67, 2011$:**
We need to show that for each prime $p \in \{41, 67, 2011\}$, at least one of $5, -6, -30$ is a quadratic residue modulo $p$.

- Suppose $(\frac{5}{p}) = (\frac{-6}{p}) = (\frac{-30}{p}) = -1$. This leads to a contradiction because:
$$\left( \frac{-30}{p} \right) = \left( \frac{5}{p} \right) \left( \frac{-6}{p} \right) = (-1)(-1) = 1$$
Hence, at least one of $5, -6, -30$ must be a quadratic residue modulo $p$.

5. Chinese Remainder Theorem:
Let $n_1, n_2, n_3$ be such that:
$$n_1^2 \in \{5, -6, -30\} \pmod{41}, \quad n_2^2 \in \{5, -6, -30\} \pmod{67}, \quad n_3^2 \in \{5, -6, -30\} \pmod{2011}$$
We now choose $n$ such that:
$$n \equiv 0 \pmod{30}, \quad n \equiv 22 \pmod{49}, \quad n \equiv n_1 \pmod{41}, \quad n \equiv n_2 \pmod{67}, \quad n \equiv n_3 \pmod{2011}$$
By the Chinese Remainder Theorem, such an $n$ exists.

$\blacksquare$