# Prove that $P_j(x)$ and $P_k(x)$ are relatively prime for all positive integers $j\neq k$

Let for $$n\ge 1, P_n(x)= 1+2x+3x^2+\cdots + nx^{n-1}$$. Prove that for any distinct positive integers j and k, $$P_j(x)$$ and $$P_k(x)$$ are relatively prime.

The above problem is 2014 Putnam A5. Solutions can be found here. I have the following questions about the solutions:

• In the first solution, how did they compute that $$w^n = nw - n+1$$? I tried using the fact that $$z$$ is not a nonnegative real number and $$P_i(z)=P_j(z)=0,$$ but I wasn't able to deduce this result.
• In the second solution, I can't understand the proof of Corollary 2. In particular, how can one apply lemma 1 to the polynomial $$f(x/R)$$ if $$x/R$$ isn't necessarily a root of $$f$$? Also, even if $$x/R$$ were a root of $$f,$$ it doesn't seem like the resulting coefficients of the polynomial would be increasing, which is a requirement of lemma 1. I'm not sure how they get the bound $$|z|\ge r$$, for similar reasons.

I tried proving a variant of Corollary 2 where $$a_i/a_{i+1}$$ is replaced by $$a_{i+1}/a_i$$ in the definitions of $$r$$ and $$R$$, but even if this corollary holds, it doesn't seem like it's useful for the given problem.

We're given

$$P_n(x) = 1+2x+3x^2+\cdots +nx^{n-1} \tag{1}\label{eq1A}$$

With the first linked solution, there's a complex $$z$$ and integers $$i \neq j$$, with $$P_i(z)=P_j(z)=0$$ and $$w = z^{-1} \neq 0, 1$$. Thus, $$z = w^{-1}$$ so, using \eqref{eq1A} with $$P_i(w^{-1})$$ and multiplying both sides by $$w^{-1}$$, we get

\begin{aligned} 0 & = \color{blue}{1 + 2w^{-1} + 3w^{-2} + \cdots + iw^{-(i-1)}} \\ & = (w^{-1} + 2w^{-2} + 3w^{-3} + \cdots + (i-1)w^{-(i-1)}) + iw^{-i} \\ & = (\color{blue}{1 + 2w^{-1} + \cdots + iw^{-(i-1)}}) - (1 + w^{-1} + \cdots + w^{-(i-1)}) + iw^{-i} \\ & = 0 - \frac{1-w^{-i}}{1-w^{-1}} + iw^{-i} \end{aligned}\tag{2}\label{eq2A}

Using $$n = i + 1$$, this gives

\begin{aligned} \frac{1-w^{-i}}{1-w^{-1}} &= iw^{-i} \\ \frac{w^{i}-1}{1-w^{-1}} & = i \\ w^{i}-1 & = i(1- w^{-1}) \\ w^{i+1}-w & = i(w - 1) \\ w^{i+1} & = (i+1)w - (i + 1 - 1) \\ w^n & = nw - n + 1 \end{aligned}\tag{3}\label{eq3A}

A corresponding result applies for $$P_j(w^{-1})$$. Note another way to get this is to instead use, for $$x \neq 1$$, that

$$f_n(x) = 1 + x + x^2 + \cdots + x^n = \frac{x^{n+1}-1}{x - 1} \tag{4}\label{eq4A}$$

to then get

$$P_n(x) = \frac{df_n(x)}{dx} = \frac{nx^{n+1}-(n+1)x^n+1}{(x-1)^2} \tag{5}\label{eq5A}$$

Regarding Corollary $$2$$ of the second solution, we have

$$f(x) = a_0 + a_{1}x + \cdots + a_{n}x^{n} \tag{6}\label{eq6A}$$

Then the solution says to use $$f(x/R)$$, but it should be $$f(Rx)$$ instead, for this to then become

\begin{aligned} f(Rx) & = a_0 + (Ra_{1})x + \cdots + (R^{n}a_{n})x^{n} \\ g(x) & = b_0 + b_{1}x + \cdots + b_{n}x^{n} \end{aligned}\tag{7}\label{eq7A}

where $$g(x) = f(Rx)$$ and

$$b_i = R^{i}a_i \; \forall \; 0 \le i \le n \tag{8}\label{eq8A}$$

Using $$R = \max\{a_0/a_1,\ldots,a_{n-1}/a_{n}\}$$, and \eqref{eq8A}, we then get for all $$0 \le i \le n-1$$ that

\begin{aligned} R & \ge a_{i}/a_{i+1} \\ Ra_{i+1} & \ge a_{i} \\ R^{i+1}a_{i+1} & \ge R^{i}a_{i} \\ b_{i+1} & \ge b_{i} \end{aligned}\tag{9}\label{eq9A}

Since this meets the conditions of lemma $$1$$, all roots $$z_1$$ of $$g(x)$$ have $$\lvert z_1 \rvert \le 1$$. Thus, with $$f(Rx)$$, all of its corresponding roots $$z = Rz_1$$ have $$\lvert z \rvert = \lvert Rz_1\rvert = R\lvert z_1\rvert \le R$$.

Showing $$r \le \lvert z \rvert$$ can be done similarly, except $$f(rx)$$ should be used instead of $$f(x/r)$$. A similar procedure to \eqref{eq7A} and \eqref{eq8A} gives, with $$x \neq 0$$, that

$$f(rx) = h(x) = c_0 + c_{1}x + \cdots + c_{n}x^{n} = x^{n}(c_0(x^{-1})^{n} + c_1(x^{-1})^{n-1} + \cdots + c_{n}) \tag{10}\label{eq10A}$$

with $$c_{i+1} \le c_{i} \; \forall \; 0 \le i \le n - 1$$. As stated in the solution, the polynomial in reverse using $$\frac{1}{x}$$ gives a set of positive, non-decreasing coefficients, so lemma $$1$$ applies to give that all roots $$\left\lvert \frac{1}{z_1}\right\rvert \le 1 \; \to \; \lvert z_1 \rvert \ge 1$$. Thus, with $$f(rx)$$, we have the roots $$z = rz_1$$, so $$\lvert z\lvert = \lvert rz_1\rvert = r\lvert z_1\rvert \ge r$$.

• Thanks. Could you look at this Dyck path/modular arithmetic problem if you have time? Commented Dec 18, 2022 at 0:34
• @user33096 You're welcome. I've looked at your other problem, but I don't offhand know of anything I can add to what you've already done there so far. Nonetheless, if I think of anything later, I will certainly add a comment and/or answer there then. Commented Dec 18, 2022 at 1:29