Omni-MATH / [color=blue][b]Generalization.[/b] Given two integers p and q and a natural number n≥3 such that p is prime and q is squarefree, and such that p∤q. Find all a∈Z such that the polyn…

[color=blue][b]Generalization.[/b] Given two integers p and q and a natural number n≥3 such that p is prime and q is squarefree, and such that p∤q.
Find all a∈Z such that the polynomial $ f(x) \equal{} x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ can be factored into 2 integral polynomials of degree at least 1.[/color]

[i]Solution.[/i] I hope the following solution is correct. It is more or less a straightforward generalization of [url=http://www.kalva.demon.co.uk/imo/isoln/isoln931.html]IMO 1993 problem 1[/url].

The idea behind is an extension of Eisenstein's criterion for irreducible polynomials:

[color=blue][b]Lemma 1.[/b] Let p be a prime number. If a polynomial $ A\left(x\right) \equal{} a_nx^n \plus{} a_{n \minus{} 1}x^{n \minus{} 1} \plus{} ... \plus{} a_1x \plus{} a_0$ with integer coefficients a_(n), $ a_{n \minus{} 1}$, ..., a₁, a₀ is reducible in Z[x], and the prime p divides the coefficients a₀, a₁, ..., $ a_{n \minus{} 2}$, but does not divide a_(n), and p² does not divide a₀, then p does not divide $ a_{n \minus{} 1}$, and the polynomial A(x) must have a rational root.[/color]

[i]Proof of Lemma 1.[/i] Since the polynomial A(x) is reducible in Z[x], we can write it in the form A(x) = B(x) C(x), where $ B\left(x\right) \equal{} b_ux^u \plus{} ... \plus{} b_1x \plus{} b_0$ and $ C\left(x\right) \equal{} c_vx^v \plus{} ... \plus{} c_1x \plus{} c_0$ are non-constant polynomials with integer coefficients b_(u), ..., b₁, b₀, c_(v), ..., c₁, c₀. Then, for any i, we have $ a_i \equal{} \sum_{k \equal{} 0}^i b_kc_{i \minus{} k}$ (this follows from multiplying out the equation A(x) = B(x) C(x)). Particularly, $ a_0 \equal{} b_0c_0$. But since the integer a₀ is divisible by the prime p, but not by p², this yields that one of the integers b₀ and c₀ is divisible by p, and the other one is not. WLOG assume that b₀ is divisible by p, and c₀ is not.

Not all coefficients b_(u), ..., b₁, b₀ of the polynomial B(x) can be divisible by p (else, $ a_n \equal{} \sum_{k \equal{} 0}^n b_kc_{n \minus{} k}$ would also be divisible by p, what is excluded). Let λ be the least nonnegative integer such that the coefficient b_(λ) is [i]not[/i] divisible by p. Then, all the integers b_(k) with k<λ are divisible by p. Hence, in the sum $ a_{\lambda} \equal{} \sum_{k \equal{} 0}^{\lambda} b_kc_{\lambda \minus{} k}$, all the summands $ b_kc_{\lambda \minus{} k}$ with k<λ are divisible by p, but the summand b_(λ)c₀ (this is the summand for $ k \equal{} \lambda$) is not (since b_(λ) is not divisible by p, and neither is c₀). Hence, the whole sum a_(λ) is not divisible by p. But we know that the coefficients a₀, a₁, ..., $ a_{n \minus{} 2}$ are all divisible by p; hence, a_(λ) must be one of the coefficients $ a_{n \minus{} 1}$ and a_(n). Thus, either $ \lambda \equal{} n \minus{} 1$ or $ \lambda \equal{} n$.

If $ \lambda \equal{} n$, then it follows, since the integer b_(λ) is defined, that the polynomial B(x) has a coefficient b_(n). In other words, the polynomial B(x) has degree n. Since the polynomial A(x) has degree n, too, it follows from A(x) = B(x) C(x) that the polynomial C(x) is a constant. This is a contradiction.

Thus, we must have $ \lambda \equal{} n \minus{} 1$. Hence, the integer $ a_{n \minus{} 1} \equal{} a_{\lambda}$ is not divisible by p. Also, since the integer b_(λ) is defined, it follows that the polynomial B(x) has a coefficient $ b_{n \minus{} 1}$. In other words, the polynomial B(x) has degree $ \geq n \minus{} 1$. Since the polynomial A(x) has degree n and A(x) = B(x) C(x), this yields that the polynomial C(x) has degree ≤1. The degree cannot be 0, since the polynomial C(x) is not constant; thus, the degree is 1. Hence, the polynomial A(x) has a linear factor, i. e. it has a rational root. Lemma 1 is proven.

Now let us solve the problem: The number pq is squarefree (since p is prime and q is squarefree, and since p∤q).

Applying Lemma 1 to the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$, using the prime p, we see that, if this polynomial can be factored into two non-constant integral polynomials, then it must have a rational root. Since it is a monic polynomial with integer coefficients, it thus must have an integer root. If we denote this root by r, then $ r^n \plus{} ar^{n \minus{} 1} \plus{} pq \equal{} 0$, so that $ pq \equal{} \minus{} r^n \minus{} ar^{n \minus{} 1} \equal{} \minus{} \left(r \plus{} a\right) r^{n \minus{} 1}$ is divisible by r² (since n≥3 yields $ n \minus{} 1\geq 2$, so that $ r^{n \minus{} 1}$ is divisible by r²), so that $ r \equal{} 1$ or $ r \equal{} \minus{} 1$ (since pq is squarefree), so that one of the numbers 1 and $ \minus{} 1$ must be a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$.

Hence, we see that, if the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ can be factored into two non-constant integral polynomials, then one of the numbers 1 and $ \minus{} 1$ must be a root of this polynomial. Conversely, if one of the numbers 1 and $ \minus{} 1$ is a root of this polynomial, then it has an integer root and thus can be factored into two non-constant integral polynomials. Hence, in order to solve the problem, it remains to find all integers a such that one of the numbers 1 and $ \minus{} 1$ is a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$. But in fact, 1 is a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ if and only if $ 1^n \plus{} a\cdot 1^{n \minus{} 1} \plus{} pq \equal{} 0$, what is equivalent to $ 1 \plus{} a \plus{} pq \equal{} 0$, i. e. to $ a \equal{} \minus{} 1 \minus{} pq$, and $ \minus{} 1$ is a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ if and only if $ \left( \minus{} 1\right)^n \plus{} a\cdot\left( \minus{} 1\right)^{n \minus{} 1} \plus{} pq \equal{} 0$, what is equivalent to $ a \equal{} 1 \plus{} \left( \minus{} 1\right)^n pq$. So, the two required values of a are $ a \equal{} \minus{} 1 \minus{} pq$ and $ a \equal{} 1 \plus{} \left( \minus{} 1\right)^n pq$.

The problem is thus solved.

[hide="Old version of the solution, not generalizing the problem"]

[i]Old version of the solution (of the original problem, not of the generalization).[/i]

Applying Lemma 1 to the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$, using the prime p, we see that, if this polynomial can be factored into two non-constant integral polynomials, then it must have a rational root. Since it is a monic polynomial with integer coefficients, it thus must have an integer root, and by a well-known theorem, this integer root then must be a divisor of pq. This means that the root is one of the numbers pq, p, q, 1, -pq, -p, -q, -1. Actually, none of the numbers pq, p, q, -pq, -p, -q can be a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ (in fact, every of these numbers is divisible by p or by q, and if an integer root r of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ would be divisible by p, then $ r^n \plus{} ar^{n \minus{} 1}$ would be divisible by $ p^{n \minus{} 1}$, while pq wouldn't be because of n≥3, so $ r^n \plus{} ar^{n \minus{} 1} \plus{} pq$ couldn't be 0, what yields a contradiction, and similarly we obtain a contradiction if an integer root would be divisible by q). Hence, only 1 and -1 remain as possible candidates for integer roots of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$.

Hence, we see that, if the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ can be factored into two non-constant integral polynomials, then one of the numbers 1 and -1 must be a root of this polynomial. Conversely, if one of the numbers 1 and -1 is a root of this polynomial, then it has an integer root and thus can be factored into two non-constant integral polynomials. Hence, in order to solve the problem, it remains to find all integers a such that one of the numbers 1 and -1 is a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$. But in fact, 1 is a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ if and only if $ 1^n \plus{} a\cdot 1^{n \minus{} 1} \plus{} pq \equal{} 0$, what is equivalent to $ 1 \plus{} a \plus{} pq \equal{} 0$, i. e. to a = - 1 - pq, and -1 is a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ if and only if $ \left( \minus{} 1\right)^n \plus{} a\cdot\left( \minus{} 1\right)^{n \minus{} 1} \plus{} pq \equal{} 0$, what is equivalent to $ a \equal{} 1 \plus{} \left( \minus{} 1\right)^n pq$. So, the two required values of a are a = - 1 - pq and $ a \equal{} 1 \plus{} \left( \minus{} 1\right)^n pq$.
[/hide]

  Darij

[color=blue][b]Generalization.[/b] Given two integers $ p$ and $ q$ and a natural number $ n \geq 3$ such that $ p$ is prime and $ q$ is squarefree, and such that $ p\nmid q$.
Find all $ a \in \mathbb{Z}$ such that the polynomial $ f(x) \equal{} x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ can be factored into 2 integral polynomials of degree at least 1.[/color]

[i]Solution.[/i] I hope the following solution is correct. It is more or less a straightforward generalization of [url=http://www.kalva.demon.co.uk/imo/isoln/isoln931.html]IMO 1993 problem 1[/url].

The idea behind is an extension of Eisenstein's criterion for irreducible polynomials:

[color=blue][b]Lemma 1.[/b] Let p be a prime number. If a polynomial $ A\left(x\right) \equal{} a_nx^n \plus{} a_{n \minus{} 1}x^{n \minus{} 1} \plus{} ... \plus{} a_1x \plus{} a_0$ with integer coefficients $ a_n$, $ a_{n \minus{} 1}$, ..., $ a_1$, $ a_0$ is reducible in $ \mathbb{Z}\left[x\right]$, and the prime p divides the coefficients $ a_0$, $ a_1$, ..., $ a_{n \minus{} 2}$, but does not divide $ a_n$, and $ p^2$ does not divide $ a_0$, then p does not divide $ a_{n \minus{} 1}$, and the polynomial A(x) must have a rational root.[/color]

[i]Proof of Lemma 1.[/i] Since the polynomial A(x) is reducible in $ \mathbb{Z}\left[x\right]$, we can write it in the form A(x) = B(x) C(x), where $ B\left(x\right) \equal{} b_ux^u \plus{} ... \plus{} b_1x \plus{} b_0$ and $ C\left(x\right) \equal{} c_vx^v \plus{} ... \plus{} c_1x \plus{} c_0$ are non-constant polynomials with integer coefficients $ b_u$, ..., $ b_1$, $ b_0$, $ c_v$, ..., $ c_1$, $ c_0$. Then, for any i, we have $ a_i \equal{} \sum_{k \equal{} 0}^i b_kc_{i \minus{} k}$ (this follows from multiplying out the equation A(x) = B(x) C(x)). Particularly, $ a_0 \equal{} b_0c_0$. But since the integer $ a_0$ is divisible by the prime p, but not by $ p^2$, this yields that one of the integers $ b_0$ and $ c_0$ is divisible by p, and the other one is not. WLOG assume that $ b_0$ is divisible by p, and $ c_0$ is not.

Not all coefficients $ b_u$, ..., $ b_1$, $ b_0$ of the polynomial B(x) can be divisible by p (else, $ a_n \equal{} \sum_{k \equal{} 0}^n b_kc_{n \minus{} k}$ would also be divisible by p, what is excluded). Let $ \lambda$ be the least nonnegative integer such that the coefficient $ b_{\lambda}$ is [i]not[/i] divisible by p. Then, all the integers $ b_k$ with $ k < \lambda$ are divisible by p. Hence, in the sum $ a_{\lambda} \equal{} \sum_{k \equal{} 0}^{\lambda} b_kc_{\lambda \minus{} k}$, all the summands $ b_kc_{\lambda \minus{} k}$ with $ k < \lambda$ are divisible by p, but the summand $ b_{\lambda}c_0$ (this is the summand for $ k \equal{} \lambda$) is not (since $ b_{\lambda}$ is not divisible by p, and neither is $ c_0$). Hence, the whole sum $ a_{\lambda}$ is not divisible by p. But we know that the coefficients $ a_0$, $ a_1$, ..., $ a_{n \minus{} 2}$ are all divisible by p; hence, $ a_{\lambda}$ must be one of the coefficients $ a_{n \minus{} 1}$ and $ a_n$. Thus, either $ \lambda \equal{} n \minus{} 1$ or $ \lambda \equal{} n$.

If $ \lambda \equal{} n$, then it follows, since the integer $ b_{\lambda}$ is defined, that the polynomial B(x) has a coefficient $ b_n$. In other words, the polynomial B(x) has degree n. Since the polynomial A(x) has degree n, too, it follows from A(x) = B(x) C(x) that the polynomial C(x) is a constant. This is a contradiction.

Thus, we must have $ \lambda \equal{} n \minus{} 1$. Hence, the integer $ a_{n \minus{} 1} \equal{} a_{\lambda}$ is not divisible by p. Also, since the integer $ b_{\lambda}$ is defined, it follows that the polynomial B(x) has a coefficient $ b_{n \minus{} 1}$. In other words, the polynomial B(x) has degree $ \geq n \minus{} 1$. Since the polynomial A(x) has degree n and A(x) = B(x) C(x), this yields that the polynomial C(x) has degree $ \leq 1$. The degree cannot be 0, since the polynomial C(x) is not constant; thus, the degree is 1. Hence, the polynomial A(x) has a linear factor, i. e. it has a rational root. Lemma 1 is proven.

Now let us solve the problem: The number $ pq$ is squarefree (since $ p$ is prime and $ q$ is squarefree, and since $ p\nmid q$).

Applying Lemma 1 to the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$, using the prime p, we see that, if this polynomial can be factored into two non-constant integral polynomials, then it must have a rational root. Since it is a monic polynomial with integer coefficients, it thus must have an integer root. If we denote this root by $ r$, then $ r^n \plus{} ar^{n \minus{} 1} \plus{} pq \equal{} 0$, so that $ pq \equal{} \minus{} r^n \minus{} ar^{n \minus{} 1} \equal{} \minus{} \left(r \plus{} a\right) r^{n \minus{} 1}$ is divisible by $ r^2$ (since $ n\geq 3$ yields $ n \minus{} 1\geq 2$, so that $ r^{n \minus{} 1}$ is divisible by $ r^2$), so that $ r \equal{} 1$ or $ r \equal{} \minus{} 1$ (since $ pq$ is squarefree), so that one of the numbers $ 1$ and $ \minus{} 1$ must be a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$.

Hence, we see that, if the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ can be factored into two non-constant integral polynomials, then one of the numbers $ 1$ and $ \minus{} 1$ must be a root of this polynomial. Conversely, if one of the numbers $ 1$ and $ \minus{} 1$ is a root of this polynomial, then it has an integer root and thus can be factored into two non-constant integral polynomials. Hence, in order to solve the problem, it remains to find all integers a such that one of the numbers $ 1$ and $ \minus{} 1$ is a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$. But in fact, $ 1$ is a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ if and only if $ 1^n \plus{} a\cdot 1^{n \minus{} 1} \plus{} pq \equal{} 0$, what is equivalent to $ 1 \plus{} a \plus{} pq \equal{} 0$, i. e. to $ a \equal{} \minus{} 1 \minus{} pq$, and $ \minus{} 1$ is a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ if and only if $ \left( \minus{} 1\right)^n \plus{} a\cdot\left( \minus{} 1\right)^{n \minus{} 1} \plus{} pq \equal{} 0$, what is equivalent to $ a \equal{} 1 \plus{} \left( \minus{} 1\right)^n pq$. So, the two required values of $ a$ are $ a \equal{} \minus{} 1 \minus{} pq$ and $ a \equal{} 1 \plus{} \left( \minus{} 1\right)^n pq$.

The problem is thus solved.

[hide="Old version of the solution, not generalizing the problem"]

[i]Old version of the solution (of the original problem, not of the generalization).[/i]

Applying Lemma 1 to the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$, using the prime p, we see that, if this polynomial can be factored into two non-constant integral polynomials, then it must have a rational root. Since it is a monic polynomial with integer coefficients, it thus must have an integer root, and by a well-known theorem, this integer root then must be a divisor of pq. This means that the root is one of the numbers pq, p, q, 1, -pq, -p, -q, -1. Actually, none of the numbers pq, p, q, -pq, -p, -q can be a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ (in fact, every of these numbers is divisible by p or by q, and if an integer root r of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ would be divisible by p, then $ r^n \plus{} ar^{n \minus{} 1}$ would be divisible by $ p^{n \minus{} 1}$, while $ pq$ wouldn't be because of $ n\geq 3$, so $ r^n \plus{} ar^{n \minus{} 1} \plus{} pq$ couldn't be 0, what yields a contradiction, and similarly we obtain a contradiction if an integer root would be divisible by q). Hence, only 1 and -1 remain as possible candidates for integer roots of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$.

Hence, we see that, if the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ can be factored into two non-constant integral polynomials, then one of the numbers 1 and -1 must be a root of this polynomial. Conversely, if one of the numbers 1 and -1 is a root of this polynomial, then it has an integer root and thus can be factored into two non-constant integral polynomials. Hence, in order to solve the problem, it remains to find all integers a such that one of the numbers 1 and -1 is a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$. But in fact, 1 is a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ if and only if $ 1^n \plus{} a\cdot 1^{n \minus{} 1} \plus{} pq \equal{} 0$, what is equivalent to $ 1 \plus{} a \plus{} pq \equal{} 0$, i. e. to a = - 1 - pq, and -1 is a root of the polynomial $ x^n \plus{} ax^{n \minus{} 1} \plus{} pq$ if and only if $ \left( \minus{} 1\right)^n \plus{} a\cdot\left( \minus{} 1\right)^{n \minus{} 1} \plus{} pq \equal{} 0$, what is equivalent to $ a \equal{} 1 \plus{} \left( \minus{} 1\right)^n pq$. So, the two required values of a are a = - 1 - pq and $ a \equal{} 1 \plus{} \left( \minus{} 1\right)^n pq$.
[/hide]

  Darij