Reducible Polynomials

Notice that $f_{n,m}(x)=\frac{x^{n+1}-1}{x-1}+\frac{x^{m+1}-1}{x-1}=\frac{x^{n+1}+x^{m+1}-2}{x-1}$

Lemma 1. Suppose $x$ is a complex root of the polynomial $x^{n+1}+x^{m+1}-2$ . Then either $|x|>1$ or $x^{n+1}=x^{m+1}=1.$

Proof. If $|x|\leq 1$ then $|x^{n+1}|\leq 1$ and $|x^{m+1}|\leq 1$ . By the triangle inequality, $|x^{n+1}+x^{m+1}|\leq 2$ with equality only if $|x|=1$ and $x^{n+1}=x^{m+1}.$ Moreover, $x^{n+1}+x^{m+1}=2$ only if both $x^{n+1}$ and $x^{m+1}$ are equal to $1$ .

Lemma 2. $f_{n.m}(x)$ can be written as a product of two polynomials with integer coefficients if and only if $\gcd(n+1,m+1)>1.$

Proof. "if": Suppose $\gcd(n+1,m+1)=d>1.$ Then $x^d-1$ divides both $x^{n+1}-1$ and $x^{m+1}-1$ . Therefore, $x^{d-1}+...+1=\frac{x^d-1}{x-1}$ divides $f_{n,m}(x).$

"only if": Suppose $f_{n.m}=g(x)h(x),$ where $g$ and $h$ are non-constant polynomials with integer coefficients. Clearly, the product of the leading coefficients of $g$ and $h$ is $1$ , so the leading coefficients of $g$ and $h$ are $\pm 1.$ If $\gcd(n+1,m+1)=1,$ then Lemma 1 implies that all complex roots of $f_{n,m}(x)(x-1)$ are either $1$ or have absolute value strictly greater than $1$ . So, because $f(1)=n+m+2\neq 0,$ all complex roots of $f_{n,m}$ have absolute value strictly greater than $1$ . Now we look at the free terms of $g$ and $h$ . Because their product is $2$ , one of them must be $\pm 1$ . But then the product of all roots of this polynomial (with multiplicities) has absolute value $1$ , a contradiction.

To complete the problem, using Lemma 2, we need to calculate the number of pairs $(n,m)$ with $0\leq m < n\leq 25$ , such that $\gcd(n+1,m+1) > 1.$ Equivalently, we are looking for the number of pairs of integers $(a,b),$ such that $1\leq b < a\leq 26$ and $\gcd(a,b) > 1.$ There are many ways to do it, we will do it by counting the number of pairs with $d \mid \gcd(a,b)$ , and using the inclusion and exclusion principle.

First, note that if $d\mid a$ and $d\mid b,$ then $b\geq d$ and $a\geq 2d.$ Because $a\leq 26,$ we only need to consider $d\leq 13.$ If $\gcd(a,b)>1,$ there is a prime $p=2,3,5,7,11,$ or $13$ such that $p \mid \gcd(a,b).$

Note that $d\mid \gcd(a,b)$ if and only if $a=da_1$ and $b=db_1$ . Here $1\leq b_1<a_1\leq \frac{26}{d}$ . So the number of such pairs is $\frac{k(k-1)}{2},$ where $k=\lfloor \frac{26}{d}\rfloor ,$ the largest integer less than or equal to $\frac{26}{d}.$ In particular, for $d=2$ the number of pairs with $2\mid \gcd(a,b)$ is $\frac{13\cdot 12}{2}=78.$ For $d=3$ the number is $\frac{8\cdot 7}{2}=28.$ For $d=5$ it is $10$ , for $d=7$ it is $3,$ for $d=11$ and $d=13$ it is $1.$ If we just add these numbers, we will count twice the pairs with $\gcd(a,b)$ divisible by two primes. Note that no pairs have $\gcd(a,b)$ divisible by three primes, because all products of three primes are at least $2\cdot 3 \cdot 5 =30.$ The only products of two primes that are not too big are $6$ and $10$ , with $6$ and $1$ pairs respectively. So, the final answer is $(78+28+10+3+1+1)-(6+1)=114.$

$f_{n,m} (x) = (x^n + x^{n-1} + ... + 1) + (x^m + x^{m-1} + ... + 1)$

$(x-1)(x^n + x^{n-1} + ... + 1) = x^{n+1}-1$

If gcd(n+1, m+1) = d > 1, we can re-write n+1 = ad and m+1=bd.

Then we get:

$(x-1)(x^n + x^{n-1} + ... + 1) = x^{ad}-1$

$(x-1)(x^n + ... + 1) = (x^d - 1)(x^{(a-1)d} + x^{(a-2)d} + ... + x^d + 1)$

$(x-1)(x^n + ... + 1) = (x-1)(x^{d-1} + ... + 1)(x^{(a-1)d} + ... + 1)$

Therefore, we have $(x^n + x^{n-1} + ... + 1)=(x^{d-1} + ... + 1)(x^{(a-1)d} + ... + 1)$ and $(x^m + x^{m-1} + ... + 1)=(x^{d-1} + ... + 1)(x^{(b-1)d} + ... + 1)$ , and thus $f_{n,m} (x) = (x^{d-1} + ... + 1)[(x^{(a-1)d} + ... + 1)+(x^{(b-1)d} + ... + 1)]$ is reducible.

Conversely, if gcd(n+1,m+1)=1, we arrive at $f_{n,m} (x) = \frac{x^{n+1} + x^{m+1} - 2}{x-1}$ , which is irreducible.

A simple checking of all possible (n,m) gives us 114 pairs of integers.

Let n + 1 = a , and m+1 = b

Observe that if the polynomial equates to (x^a + x^b - 2)/(x-1).

Observe that if gcd(a,b) = d, x^d - 1 is a factor of both (x^a - 1) and (x^b - 1). Thus if d > 1, b>= degree of (x^d-1)/(x-1) >= 1, and the original polynomial is reducible.

Brute force shows that all cases where a and b are coprime in the range (1,26) are irreducible. This gives us the answer of 114