Reducible 1000 degree Polynomials

For an integer $k$ , define $v_2(k)$ as the greatest integer $r$ such that $2^r$ divides $k$ . For example, $v_2(1000)=3$ and $v_2(7)=0$ .

We claim $f_n(x)$ is reducible in integers if and only if $v_2(n)=v_2(1000)$ . We divide our proof into two parts.

Part $1$ : $f_n(x)$ is reducible, if and only if $x^n+1$ and $x^{1000}+1$ have a common factor.

First, we show the only if part. Suppose $f_n(x)=P(x)Q(x)$ , where $P(x)$ and $Q(x)$ are non-constant integer polynomials. First, we know that $P(x)$ and $Q(x)$ have leading coefficients $\pm 1$ . Second, the product of the constant terms of $P(x)$ and $Q(x)$ is $2$ . This means that one of the constant terms has magnitude $1$ . Without loss of generality, let the constant term of $P(x)$ have magnitude $1$ . Then, the product of the roots of $P(x)$ has magnitude $1$ , so $P(x)$ at least one root with magnitude less then or equal to $1$ . Call this root $r$ . Then, $f_n(r)=0$ . However, by the triangle inequality,

$|r^{1000}+r^n| \leq |r^{1000}|+|r^n|=|r|^{1000}+|r|^n \leq 1+1 =2$

Thus, $|f_n(r)| \geq 2-|r^{1000}+r^n| \geq 0$ . Equality holds if and only if $r^{1000}=r^n=-1$ . However, then $r$ is a common root of $x^n+1$ and $x^{1000}+1$ , so the two polynomials must have a common factor.

To show the if part, suppose $x^n+1$ and $x^{1000}+1$ have a common factor. Then, $f_n(x)$ is the sum of the two polynomials so their common factor clearly divides $f_n(x)$ .

Part $2$ : $x^a+1$ and $x^b+1$ have a common factor if and only if $v_2(a)=v_2(b)$ .

First, we show the only if part. Suppose $x^a+1$ and $x^b+1$ have a common factor. Then, they have a common root, $r$ . Then, $r^a=r^b=-1$ Let $k$ be the smallest integer such that $r^k=-1$ . Then, $a$ and $b$ are odd multiples of $k$ . Then, $v_2(k)=v_2(a)$ and $v_2(k)=v_2(b)$ . Thus, $v_2(a)=v_2(b)$ .

To show the if part, suppose $v_2(a)=v_2(b)$ =q. Then, clearly $x^{2^q}+1$ divides both $x^a+1$ and $x^b+1$ .

Thus, we have shown that $f_n(x)$ is reducible in integers if and only if $v_2(n)=v_2(1000)$ . Thus, we want to find all $n$ under $1000$ such that $v_2(n)=3$ . However, this is all $n$ under $1000$ that are odd multiples of $8$ and we can easily verify that there are $\boxed{62}$ of them.

Consider all $n$ of the form $8(2m+1)$ , where $m$ is an non-negative integer. Then $f_{8(2m+1)}(x) = x^{1000} + x^{8(2m+1)} + 2 = (x^{1000}+1)+(x^{8(2m+1)}+1)$ . Since $x^{1000} + 1 = (x^8)^{125}+1 = (x^8+1)(x^{992} - x^{984} + ... + 1)$ and $x^{8(2m+1)} + 1 = (x^8)^{2m+1}+1 = (x^8+1)((x^8)^{2m} - (x^8)^{2m-1} + ... + 1)$ , then $x^8+1$ is a factor of $f_{8(2m+1)}(x)$ . Therefore, $f_{8(2m+1)}(x)$ is reducible for all non-negative integers $m$ . Since $1000 = 8(2\cdot 62 + 1)$ , then $f_n(x)$ is reducible for the $62$ positive integers $n < 1000$ of the form $8(2m+1)$ (corresponding to $m=0, 1, ... , 61$ ).

Now, we shall show that if $f_n(x)$ is reducible, then $n$ must be of the form $8(2m+1)$ .

Let $r$ be any complex root of $f_n(x)$ ; so $r^{1000}+r^n+2=0$ . If $|r| \leq 1$ , then taking the modulus of both sides of the equation $-2 = r^{1000}+r^n$ , we have:

$\begin{array}{cc} 2 &= |r^{1000}+r^n| \\ &\leq |r^{1000}|+|r^n| \\ &=|r|^{1000} + |r|^n \\ &\leq 1 + 1 \\ &= 2 \end{array}$

Therefore, equality holds for both the second and fourth lines. For the second line, equality holds iff $r^{1000} =kr^n$ for some positive real number $k$ . For the fourth line, equality holds iff $|r| = 1$ . Thus, all the roots $r_i$ of $f_n(x)$ must satisfy either: (i) $|r_i| > 1$ , or (ii) $|r_i| = 1$ and $r_i^{1000} = k_ir_i^n$ for some positive real number $k_i$ . For case (ii), $r_i^{1000} = k_ir_i^n \Rightarrow r_i^{1000-n} = k_i$ (since $r_i$ clearly cannot be zero). This means $|k_i| = |r_i^{1000-n}| = |r_i|^{1000-n} = 1^{1000-n} = 1$ . Since $k_i$ is a positive real number, then $k_i = 1$ and $r_i^{1000} = r_i^n$ .

Now suppose that $f_n(x)$ is reducible. Then $f_n(x)$ = $g_n(x)\cdot h_n(x)$ for some non-constant polynomials $g_n(x),h_n(x)$ with integer coefficients. Since $f_n(x)$ is a monic polynomial, then the leading coefficients of $g_n(x)$ and $h_n(x)$ must either both be $1$ or both be $-1$ . Also, $2 = |f_n(0)| = |g_n(0)|\cdot |h_n(0)|$ . Since $2$ is prime, then $(|g_n(0)|,|h_n(0)|) = (1,2)$ or $(2,1)$ . Without loss of generality, we let $|g_n(0)| = 1$ . $g_n(x)$ is a non-constant polynomial, so let us consider its roots $r_1, … , r_j$ , where $j \geq 1$ . Note that these $j$ roots are also roots of the polynomial $f_n(x)$ . Since the leading coefficient of $g_n(x)$ is $\pm 1$ and $g_n(0) = \pm 1$ , then the product of the roots of $g_n(x)$ is also $\pm 1$ . Thus, $|r_1…r_j|=1$ . Since $|r_1|, ..., |r_j|\geq 1$ , we must have $|r_1|=...=|r_j|=1$ . Since this is so, then $r_i^{1000} = r_i^n$ for all $i = 1,…,j$ . Take any of the roots, say $r_1$ since $j \geq 1$ . $r_1$ is a root of $f_n(x)$ , so $r_1^{1000}+r_1^n+2 = 0$ . But $r_1^{1000} = r_1^n$ , so $2r_1^{1000}+2 = 0$ . It follows that $r_1^{1000} = r_1^n = -1$ . Let $arg(r_1)$ be $\theta$ . Then $1000\theta \equiv n\theta \equiv arg(-1) \equiv \pi \pmod{2\pi}$ . So we can write $1000\theta$ and $n\theta$ as $(2p+1)\pi$ and $(2q+1)\pi$ respectively, for some integers $p$ and $q$ . It follows that $\theta = \frac{(2p+1)\pi}{1000} = \frac{(2q+1)\pi}{n}$ , and hence $2q+1 = \frac{n(2p+1)}{1000}$ . Since $2q+1$ is an integer, then we have $1000|n(2p+1)$ . So $8|n(2p+1)$ . $2p+1$ is odd, so we must have $8|n$ . We now write $n = 8u$ for some positive integer $u$ (since $n$ is positive). Substituting this back into $2q+1 = \frac{n(2p+1)}{1000}$ , we have $2q+1 = \frac{u(2p+1)}{125} \Rightarrow 125(2q+1) = u(2p+1)$ . Clearly, the left hand side of the equation is odd, so $u$ must be odd. So $u$ is in the form $2m+1$ , where $m$ is an non-negative integer. Combining these results, we have $n = 8(2m+1)$ for some non-negative integer $m$ .

Therefore, all polynomials $f_n(x)$ where $n$ is not of the form $8(2m+1)$ must be irreducible. So there are exactly $62$ integers $n < 1000$ such that $f_n(x)$ is reducible.

This solution is written together with user Anqi L. (in fact it was mostly written by her) who could not publish the solution because she already published 2 on number theory.

Let us define $v_2(k)$ as the largest multiple of $2$ dividing $k$ . This is definitely routine, motivated in particular by the constant $2$ in the expression $f_n(x) = x^{1000} + x^n + 2$ . To further motivate the solution, one may attempt small cases , in other words for $n < 10$ and one easily gets that $n = 8$ works. Whence, we may conjecture that $f_n(x)$ is reducible iff $v_2(1000) = v_2(n)$ .

However, just proving this is very tedious. With a certain intuition, we can first show that we must have $x^{1000} + 1$ and $x^n + 1$ sharing factors.Then we show that if $x^j+1$ and $x^k + 1$ at least a factor, then $v_2(j) = v_2(k)$ . So:

Step 1: $f_n(x)$ is reducible iff $gcd(x^{1000}+1, x^n+1) > 1$ .

Proof : We will show the if part first. It is considerably trivial. Suppose $gcd(x^{1000}+1, x^n+1) = m$ for some expression $m$ , since $f_n(x) = (x^{1000} + 1) + (x^n + 1 )$ we must have $m \mid f_n(x)$ as desired.

Moving on to the only if part, let us first write $f_n(x) = P(x)Q(x)$ for some polynomials $P(x)$ and $Q(x)$ . Clearly, synthesising the expression $f_n(x)$ , $P(x)$ and $Q(x)$ are either monic or else the leading coefficient is $- 1$ . Also, the product of their constant terms is clearly $2$ . Now this directly goes to show that one of the polynomials have a constant of magnitude $1$ and we may WLOG assume that it is $P(x)$ . Since we have in fact made full use of the coefficients that we are given, it is intuitive in such polynomial problems, to look at the roots . So, trivially, since the product of the roots of $P(x)$ is $1$ , at least $1$ root of $P(x)$ is $\leq 1$ , and suppose that the root is $r$ . Then we have that $f_n(r) = 0$ . When we consider roots, it is also crucial sometimes to involve triangle inequality because we can then consider absolute values of roots to get a contradiction; it is especially important in proving irreducibility. So applying triangle inequality, we get:

$|r^{1000} + r^n| \leq |r^{1000}|+|r^n| = |r|^{1000} + |r|^n \leq 1^{1000} + 1^n = 2$

Remark that this implies: $f_n(r) \geq 2 - |r^{1000} + r^n| \geq 0$ The equality case that we need holds when $r^{1000} = r^n = -1$ , which clearly implies that $r$ is a common root, and the polynomials have to share a common factor. □

Step 2: $gcd(x^j+1,x^k+1) > 1$ holds iff $v_2(j) = v_2(k)$ .

Proof : We sort of mimic the proof for step 1. We will show the easier if case first (for a morale booster). Suppose $v_2(j) = v_2(k) = l$ , then clearly $x^{2^l}$ divides both $x^j+1$ and $x^k+1$ as desired.

Now, we show the only if part. Suppose $gcd(x^j+1,x^k+1) > 1$ . Then again, using a roots analysis, we know that $x^j+1$ and $x^k + 1$ share a common root which we will denote as $q$ . Obviously, $q^j = q^k = -1$ . Now, because we want to show that they have the same exponent of $2$ , we can always divide them by an odd exponent. Formalising the previous sentence, if $p$ is the smallest number such that $q^p = -1$ , obviously both $j \ \text{and}\ k$ are odd multiples of $p$ , so $v_2(p) = v_2(j) = v_2(k)$ as desired. □

So in conclusion, we have shown that in order for $f_n(x)$ to be irreducible, we need to have $v_2(n) = v_2(1000) = 3$ , or stating in words (for ease of counting later), $n$ is an odd multiple of $2^3 = 8$ . Trivially, the total number/answer is: $\lfloor \frac{\frac{1000}{8}}{2} \rfloor = 62$ . (Note that we take floor because $n$ needs to be strictly less than $1000$ . )

Sorry for the long solution. It contains our motivation, inspiration, inklings, etc. and we believe that it will be more instructive this way :)

x^1000+x^n+2 if this polynomial has to be written in terms of two polynomials, then the search would be for a common factor.

Now let us consider x^n+2 for no values of n, except 1, this can be written as a product of polynomials having integer coefficient. That's because the roots of x^n+2 are of the form of 2^(1/n) exp(i (2k+1)*pi/n) where k can go from 0 to n-1.

Except n=1 , 2^(1/n) is never an integer. so considering n=1, we are left with this polynomial x^1000+x+2 . This cannot be further reduced because there is no common factor.

Similarly if we consider the roots of x^1000+k, then it will be k^(1/1000)* exp(i (2m+1) pi/1000) where m can go from 0 to 999. Now the modulus of the roots are |k^(1/1000)| * | exp(i (2m+1) pi/1000) | the last term is always 1. Hence the modulus of the roots are determined by | k^(1/1000) | . Now in order to reduce this to a polynomials having integer coefficients k must be equal to 1 or 10^(1000) .

therefore the above polynomial can be written as a sum of two individual polynomials such as (x^1000+1)+(x^n+1)

Now lets factorize x^1000+1. One thing to notice here is , 1000=2^3*5^3 .

so the factorization of x^1000+1 will yield (1+x^8) (x^32-x^24+x^16-x^8+1) (x^160-x^120+x^80-x^40+1)*(x^800-x^600+x^400-x^200+1)

so the x^n+1 must have a common factor x^8+1. This is possible only when n=8m where m is any odd number between 1 to 123. so total number of odd number that exists between this limit is 62. Hence n can have 62 values of the form 8m (m=1,3,5,7,.....)

The key thing to notice in this solution is x^n+1 can only be factorized to polynomials having integer coefficient is when n is odd. This follows from the fact that only when n is odd, we get one real root as 1.

I owe my thanks to Zhang Lulu for helping with the Latex.

Let us define $v_2(k)$ as the largest multiple of $2$ dividing $k$ . This is definitely routine, motivated in particular by the constant $2$ in the expression $f_n(x) = x^{1000} + x^n + 2$ . To further motivate the solution, one may attempt small cases , in other words for $n < 10$ and one easily gets that $n = 8$ works. This, for those curious, is by the remainder theorem. Whence, we may conjecture that $f_n(x)$ is reducible iff $v_2(1000) = v_2(n)$ .

However, just proving this is very tedious. With a certain intuition, we can first show that we must have $x^{1000} + 1$ and $x^n + 1$ sharing factors.Then we show that if $x^j+1$ and $x^k + 1$ at least a factor, then $v_2(j) = v_2(k)$ . So:

Step 1: $f_n(x)$ is reducible iff $gcd(x^{1000}+1, x^n+1) > 1$ .

Proof : We will show the if part first. It is considerably trivial. Suppose $gcd(x^{1000}+1, x^n+1) = m$ for some expression $m$ , since $f_n(x) = (x^{1000} + 1) + (x^n + 1 )$ we must have $m \mid f_n(x)$ as desired.

Moving on to the only if part, let us first write $f_n(x) = P(x)Q(x)$ for some polynomials $P(x)$ and $Q(x)$ . Clearly, synthesising the expression $f_n(x)$ , $P(x)$ and $Q(x)$ are either monic or else the leading coefficient is $- 1$ . Also, the product of their constant terms is clearly $2$ . Now this directly goes to show that one of the polynomials have a constant of magnitude $1$ and we may WLOG assume that it is $P(x)$ . Since we have in fact made full use of the coefficients that we are given, it is intuitive in such polynomial problems, to look at the roots . So, trivially, since the product of the roots of $P(x)$ is $1$ , at least $1$ root of $P(x)$ is $\leq 1$ , and suppose that the root is $r$ . Then we have that $f_n(r) = 0$ . When we consider roots, it is also crucial sometimes to involve triangle inequality because we can then consider absolute values of roots to get a contradiction; it is especially important in proving irreducibility. So applying triangle inequality, we get:

$|r^1000 + r^n| \leq |r^{1000}|+|r^n| = |r|^{1000} + |r|^n \leq 1^{1000} + 1^n = 2$

Remark that this implies: $f_n(r) \geq 2 - |r^{1000} + r^n| \geq 0$ The equality case that we need holds when $r^1000 = r^n = -1$ , which clearly implies that $gcd(x^{1000} -1 ,x^n - 1) = r$ . □

Step 2: $gcd(x^j+1,x^k+1) > 1$ holds iff $v_2(j) = v_2(k)$ .

Proof : We sort of mimic the proof for step 1. We will show the easier if case first (for a morale booster). Suppose $v_2(j) = v_2(k) = l$ , then clearly $x^{2^l} +1$ divides both $x^j+1$ and $x^k+1$ as desired.

Now, we show the only if part. Suppose $gcd(x^j+1,x^k+1) > 1$ . Then again, using a roots analysis, we know that $x^j+1$ and $x^k + 1$ share a common root which we will denote as $q$ . Obviously, $q^j = q^k = -1$ . Now, because we want to show that they have the same exponent of $2$ , we can always divide them by an odd exponent. Formalising the previous sentence, if $p$ is the smallest number such that $q^p = -1$ , obviously both $j \ \text{and}\ k$ are odd multiples of $p$ , so $v_2(p) = v_2(j) = v_2(k)$ as desired. □

We have reduced the problem to a mere counting exercise, IMHO. Because we have that $f_n(x) \text{is irreducible} ⇔ v_2(n) = v_2(1000) = 3$ . For ease of counting, note that we need only find the number of odd multiples of $2^3 = 8$ . The total number is: $\lfloor \frac{\frac{1000}{8}}{2} \rfloor = \boxed{62}$ (Note that we take floor because $n$ needs to be strictly less than $1000$ )

Suppose $f_n=g\cdot h,$ where $g$ and $h$ have integer coefficients. Because the leading terms get multiplied, the leading coefficients of $g$ and $h$ are $\pm 1.$ Multiplying both polynomials by $-1$ if necessary, we can assume that the leading coefficients are $1$ (that is, $g$ and $h$ are monic). Similarly, the constant terms of $g$ and $h$ multiply to $2.$ Possibly switching the two factors, we can assume that $g(0)=\pm 1$ and $h(0)=\pm 2.$

Lemma 1. Suppose $t$ is any complex root of $f_n.$ Then $|t|\geq 1.$ Moreover, $|t|=1$ if and only if $t^{1000}=t^n=-1.$

Proof. Applying triangle inequality to $-2=t^{1000}+t^n,$ we get $2=|-2|\leq |t^{1000}|+|t^n|=|t|^{1000}+|t|^n$ So if $|t|<1,$ we get a contradiction. If $|t|=1,$ then the triangle inequality is an equality which happens if and only if the summands "line up", that is $t^{1000}=t^n=-1.$

By the Vieta's formula, the product of all roots of $g$ is $\pm 1.$ By the above lemma, this can only happen if all of them have absolute value $1$ , and in this case they all must satisfy the condition $t^{1000}=t^n=-1.$

Lemma 2. For any given positive integer $n<1000,$ the system of equations $t^{1000}=t^n=-1$ has a solution if and only if $n=16m+8$ for some integer $m$ .

Proof. In one direction, if $n=16m+8,$ denote $\gcd(n,1000)$ by $k.$ It is divisible by $8,$ but not by $16.$ Then consider $t$ to be any root of $x^{k}+1.$ Since $t^k=-1$ and $1000/k$ and $n/k$ are odd, $t^{1000}=t^{n}=-1.$

In the other direction, suppose $k=\gcd(n,1000),$ then $k=1000a+nb$ for some integers $a$ and $b.$ So $t^k=(-1)^a\cdot (-1)^b=\pm 1$ . If $1000/k$ is even, this would imply $t^{1000}=(\pm 1)^{1000/k}=1.$ So $1000/k$ is odd, thus $k$ is divisible by $8,$ but not by $16.$ Now if $n/k$ is even, then $(-1)^n=(\pm 1)^{n/k}=1,$ a contradiction. Therefore, $n/k$ is odd, which implies $n/8$ is odd, so $n=16m+8$ .

Lemma 2, together with the discussion above it, prove that $n=16m+8$ is a necessary condition for $f_n$ to be a product of two integer polynomials. In the other direction, if $n=16m+8$ and $k= \gcd(n,1000),$ then one can take $g(x)=x^k+1:$ $f_n(x)=(x^n+1)+(x^{1000}+1)= (x^k+1)\left( (x^{n-k}-x^{n-2k}+...-x^k+1)+ (x^{1000-k}-...+1) \right)$

Finally, to count the number of $n$ , note that $0\leq m \leq 61,$ so the answer is $62.$

It is interesting to note that a polynomial of the form {(x)^2^p x m}+x^n+2 can be factored as: {(x)^2^p + 1}R(x), where R(x) is a non constant polynomial, and there are (floor m/2) irreducible solutions for value of n (i.e., for (floor m/2) no. of values of n, the polynomial can be factored into 2 terms). Hence, {(x)^1000}+x^n +2 = {(x)^2^3 x 125}Q(x), and there are (floor 125/2)= 62 irreducible solutions for value of n( the polynomial can be factored into 2 non constant polynomials for 62 values of n) Note: Degree of Q(x) = 1000-8 =992.

You can find a pattern using the PARI code: for(n=1,999,print(factor(x^1000+x^k+2))). It turns out that every integer that is congruent to 8 modulo 16 is factorizable over Q[x].