1. 我们知道：如果一个有理系数多项式有一个无理根 $a + \sqrt{b}$，那么它的共轭根 $a - \sqrt{b}$ 也一定是这个多项式的根。
2. 对每个 $n = 1, 2, \ldots, 1000$，数 $n + \sqrt{n+1}$ 都是给定多项式的根，因此每个这样的无理根都需配一个共轭根，初步得到 $2 \times 1000 = 2000$ 个根。
3. 但并非所有 $n + \sqrt{n+1}$ 都是无理数：当 $n+1$ 是完全平方数时，$\sqrt{n+1}$ 是整数，此时 $n + \sqrt{n+1}$ 是有理数（其实是整数），它没有共轭根。
4. 满足 $n+1$ 是完全平方数的 $n$ 有多少个？$n+1$ 可取 $2^2, 3^2, \ldots, 31^2$，共 $30$ 个值。
5. 所以要去掉这 $30$ 个不需要配对的根，实际至少需要 $2000 - 30 = 1970$ 个根。
6. 多项式的次数等于其根的个数（重根按重数计，此处均为单根），因此该多项式的最小可能次数是 $\boxed{1970}$。

因为$x^2 + x + 1$是$(x^2 + x + 1)(x - 1) = x^3 - 1,$的因数，所以也是$x(x^3 - 1) = x^4 - x,$的因数，因此$(x^4 - 1)(x^2 - 1)$除以$x^2 + x + 1$的余数与

除以【MATH_1】的余数相同。 这个余数与$1 - x^2 - x + 1 = -x^2 - x + 2 = -(x^2 + x + 1) + 3$除以$x^2 + x + 1,$的余数相同，即$\boxed{3}.$。