Newton's Sum is too slow!

Note that $81 = 3^4$ .

Let $f_n (x)$ and $g_n (x) = x^3 f_n \left ( \frac {1}{x} \right )$ be $3^{\text{rd}}$ degree polynomials with integer coefficient such that $f_n (x)$ has zeros $\large p^{3^n}, q^{3^n}, r^{3^n}$ while $g_n (x)$ has zeros $\large p^{-3^n}, q^{-3^n}, r^{-3^n}$ , where $n=0,1,2,3$

So $f_0 (x) = x^3 + 2x^2 + 3x + 1$ . By Vieta's formula, $p+q+r=-2, pq+pr+qr=3, pqr=-1$ . Apply the algebraic identity

$p^3 + q^3 + r^3 - 3pqr = (p+q+r) \left ( (p+q+r)^2 - 3(pq+pr+qr) \right ) \Rightarrow p^3 + q^3 + r^3 = 7$

And $g_0 (x) = x^3 + 3x^2 + 2x + 1 \Rightarrow \frac {1}{p} + \frac {1}{q} + \frac {1}{r} = -3, \Rightarrow \frac {1}{pq} + \frac {1}{pr} + \frac {1}{qr} = 2$

$\left ( \frac {1}{p} \right )^3 + \left ( \frac {1}{q} \right )^3 + \left ( \frac {1}{r} \right )^3 - \frac {3}{pqr} = \left ( \frac {1}{p} + \frac {1}{q} + \frac {1}{r} \right ) \left ( \left ( \frac {1}{p} + \frac {1}{q} + \frac {1}{r} \right )^2 - 3\left ( \frac {1}{pq} + \frac {1}{pr} + \frac {1}{qr} \right ) \right )$

$\large \Rightarrow \frac {1}{p^3} + \frac {1}{q^3} + \frac {1}{r^3} = -12 \Rightarrow \frac {p^3 q^3 + p^3 r^3 + q^3 r^3}{(pqr)^3} = -12 \Rightarrow p^3 q^3 + p^3 r^3 + q^3 r^3 = 12$

$f_1 (x) = x^3 -7x^2 +12x + 1 \Rightarrow g_1 (x) = x^3 + 12x^2 - 7x + 1$

Apply the same method above:

$p^9 + q^9 + r^9 - 3(pqr)^3 = (p^3+q^3+r^3) \left ( (p^3+q^3+r^3)^2 - 3(p^3 q^3 +p^3 r^3 +q^3 r^3) \right )$

$\Rightarrow p^9 + q^9 + r^9 = 88$

$\left ( \frac {1}{p^3} \right )^3 + \left ( \frac {1}{q^3} \right )^3 + \left ( \frac {1}{r^3} \right )^3 - \frac {3}{(pqr)^3} = \left ( \frac {1}{p^3} + \frac {1}{q^3} + \frac {1}{r^3} \right ) \left ( \left ( \frac {1}{p^3} + \frac {1}{q^3} + \frac {1}{r^3} \right )^2 - 3\left ( \frac {1}{p^3 q^3 } + \frac {1}{p^3 r^3} + \frac {1}{q^3 r^3} \right ) \right )$

$\large \Rightarrow \frac {1}{p^9} + \frac {1}{q^9} + \frac {1}{r^9} = -1983 \Rightarrow p^9 q^9 + p^9 r^9 + q^9 r^9 =1983$

$f_2 (x) = x^3 - 88x^2 +1983x + 1 \Rightarrow g_2 (x) = x^3 + 1983x^2 - 88x + 1$

Repeat:

$p^{27} + q^{27} + r^{27} - 3(pqr)^9 = (p^9+q^9+r^9) \left ( (p^9+q^9+r^9)^2 - 3(p^9 q^9 +p^9 r^9 +q^9 r^9) \right )$

$\Rightarrow p^{27} + q^{27} + r^{27} = 157957$

$\left ( \frac {1}{p^9} \right )^3 + \left ( \frac {1}{q^9} \right )^3 + \left ( \frac {1}{r^9} \right )^3 - \frac {3}{(pqr)^9} = \left ( \frac {1}{p^9} + \frac {1}{q^9} + \frac {1}{r^9} \right ) \left ( \left ( \frac {1}{p^9} + \frac {1}{q^9} + \frac {1}{r^9} \right )^2 - 3\left ( \frac {1}{p^9 q^9 } + \frac {1}{p^9 r^9} + \frac {1}{q^9 r^9} \right ) \right )$

$\large \Rightarrow \frac {1}{p^{27}} + \frac {1}{q^{27}} + \frac {1}{r^{27}} = -7798252602 \Rightarrow p^{27} q^{27} + p^{27} r^{27} + q^{27} r^{27} = 7798252602$

$f_3 (x) = x^3 - 157957x^2 + 7798252602x - 1$

Repeat one last time

$p^{81} + q^{81} + r^{81} - 3(pqr)^{27} = (p^{27}+q^{27}+r^{27}) \left ( (p^{27}+q^{27}+r^{27})^2 - 3(p^{27} q^{27} +p^{27} r^{27} +q^{27} r^{27}) \right )$

Modulo $1000$ :

$\begin{aligned} p^{81} + q^{81} + r^{81} & \equiv & 157957 ( 157957^2 - 3 \cdot 7798252602 ) - 3 \\ & \equiv & 957 (957^2 - 3 \cdot 602 ) - 3 \\ & \equiv & -43 (43^2 - 1806 ) - 3 \\ & \equiv & \boxed{148} \\ \end{aligned}$

This solution echos what Pi Han does, but presents it in a cleaner fashion. You will see glimpses of what he does. The main difference is that I use algebra to treat the general approach, and iterate it several times, as opposed to Pi Han who performs the calculations several times.

---

Lemma. Suppose that $\alpha, \beta, \gamma$ are roots to the cubic equation $x^3 + ax^2 + bx + c = 0$ . Then $\alpha^3, \beta^3, \gamma^3$ are roots to the cubic equation $X^3 +(3c +a^3 - 3ab) X^2 + (3c^2 + b^3 - 3abc)X + c^3 = 0.$

Proof of Lemma. Apply Vieta's formula. Observe that
$\alpha^3 + \beta^3 + \gamma^3 = (\alpha + \beta + \gamma)^3 - 3 ( \alpha + \beta + \gamma) ( \alpha \beta + \beta \gamma + \gamma \alpha) + 3 \alpha \beta \gamma$ ,
$\alpha^3 \beta^3 + \beta^3 \gamma^3 + \gamma^3 \alpha^3 = (\alpha\beta + \beta \gamma + \gamma \alpha)^3 - 3 ( \alpha + \beta + \gamma) (\alpha\beta + \beta \gamma + \gamma \alpha) (\alpha \beta \gamma) + 3 ( \alpha \beta \gamma)^2$ ,
$\alpha^3 \beta^3 \gamma^3 = ( \alpha \beta \gamma)^3$ .

Note that Pi Han essentially used these formulas too.

Corollary. We thus get that

$p^3, q^3, r^3$ are roots of $x^3 - 7x^2 + 12x + 1 = 0,$

$p^9, q^9, r^3$ are roots of $x^3 - 88x^2 + 1983x + 1 = 0,$

$p^{27}, q^{27}, r^{27}$ are roots of $x^3 - 157957x^2 + 7798252602 + 1 = 0,$

And finally, $p^{81} + q^{81} + r^{81} = (157957)^3 - 3 \times 157957 \times 7798252602 + 3 \times 1$ .

---

Alternative proof of lemma. (For those who don't like the 'amazing formulas' shown above. Though, this only works well for small degrees, since it is otherwise hard to force out the amazing formulas.)

Observe that $x^3 + c = -ax^2 - bx$ . Cubing both sides, we obtain that

$x^9 + 3x^6c + 3x^3c^2 +c^3 = - a^3 x^6 - 3a^2bx^5 - 3ab^2x^4 - b^3 x^3.$

Every exponent of $x$ is a multiple of 3, with the exception of $- 3a^2bx^5 - 3ab^2x^4$ . Luckily, we can express this as $-3abx^3 ( ax^2 + bx )= -3abx^3 ( - x^3 - c) = 3abx^6 + 3abcx^3$ .

Hence, we have

$x^9 + (3c +a^3 - 3ab) x^6 + (3c^2 + b^3 - 3abc)x + c^3 = 0.$

As such, the cubic equation

$X^3 +(3c +a^3 - 3ab) X^2 + (3c^2 + b^3 - 3abc)X + c^3 = 0.$

would have roots of the form $\alpha^3 , \beta^3 , \gamma^3$ .

The main motive of this solution is to explain the fact that, not only $p^{81} + q^{81} + r^{81}$ , but we can calculate the values of $p_1^{k} + p_2^{k} + p_3^{k} + \ldots + p_n^k$ for any $k \geq 1, k \in \mathbb N$ using a single two step process.

This is a solution which uses Companion Matrix Methods and a heavy computational calculation.

---

Let $P(x) = x^3+2x^2 + 3x+1$ .

Let $Q(x)$ be a polynomial whose roots are $81^{st}$ powers of the roots of $P(x)$ .

We'll use the companion matrix of the polynomial $P(x)$ namely:

$A = \begin{pmatrix} 0 & 0 & -1 \\ 1 & 0 & -3 \\ 0 & 1 & -2 \end{pmatrix}$

for which the characteristic polynomial is $\text{det}(xI-A) = x^3 + 2x^2 + 3x + 1$ . For each integer $k \geq 1$ , the zeroes of the characteristic polynomial of $A^{k}$ are the $k^{th}$ powers of the zeroes of $P(x)$ . Taking this into account, we find that $Q(x) = \text{det}(xI-A^{81})$ . Using Scientific Calculators, we obtain:

$A^{81} = \begin{pmatrix} 141006837910400 & 167222059610375 & -590313054904651 \\ 255868935683901 & 642673016741525 & -1603717105103578 \\ -167222059610375 & 590313054904651 & -537953093067777 \end{pmatrix}$

Thus we have $Q(x)$ as:

$Q(x) = \text{det}(xI-A^{81})$

$= \begin{vmatrix} x-141006837910400 & -167222059610375 & 590313054904651 \\ -255868935683901 & x-642673016741525 & 1603717105103578 \\ 167222059610375 & -590313054904651 & x+537953093067777 \end{vmatrix}$

$= x^3 - 245726761584148x^2 + 474233136361262818167354353553x + 1$

Thus, we know that if $p,q,r$ are the roots of $P(x)$ , then $p^{81}, q^{81}, r^{81}$ are the roots of $Q(x)$ .

Therefore, by Vieta's Formula, the sum of roots of $Q(x)$ or $p^{81} + q^{81} + r^{81}$ equals $245726761584148$ and it's last three digits being $148$ .

---

Since I had no scientific calculators to perform heavy calculations, I preferred Wolfram-Mathematica.

• I did this - Link 1 - to find the value of $A^{81}$ .

• I did this - Link 2 - to find the value of $\text{det}(xI-A^{81})$ .