Given the equation $x^{2}+p x+q=0$, we know that $p$ and $q$ are integers, their greatest common divisor is $r(>1)$, and the roots are real. Consider the sum of the $n$-th powers of the roots, where $n$ is a natural number. For which exponents $k$ can we state that the sum is divisible by $r^{k}$?
The conditions of the problem ensure that the sum

$$
s_{n}=x_{1}^{n}+x_{2}^{n}
$$

formed from the roots $x_{1}, x_{2}$ is an integer. Indeed, we will show that $s_{n}$ for any $n$ can be expressed as a finite combination of the sum of the two roots $x_{1}+x_{2}=-p$, the product of the roots $x_{1} x_{2}=q$, and integers, using only addition and multiplication. At the same time, we will examine the problem's question: for a given $n$, by what power of $r$ is $s_{n}$ divisible?

1. For $n=1$, $s_{1}=x_{1}+x_{2}=-p=-r p^{\prime}$, where $p^{\prime}$ is an integer, and generally we cannot say that $s_{1}$ is divisible by a power of $r$ greater than 1.

For $n=2$,

$$
s_{2}=x_{1}^{2}+x_{2}^{2}=\left(x_{1}+x_{2}\right)^{2}-2 x_{1} x_{2}=p^{2}-2 q
$$

here $p^{2}=r^{2} p^{\prime 2}$ and $-2 q=-2 r q^{\prime}$, where $p^{\prime 2}$ and $q^{\prime}$ are integers. Although the first term is divisible by $r^{2}$, the second is only divisible by $r$, so together they generally only ensure divisibility of $s_{2}$ by $r$. (Specifically, for $r=2$, the second term is also divisible by $r^{2}$.)

If $n=3$, then

$$
\begin{gathered}
s_{3}=x_{1}^{3}+x_{2}^{3}=\left(x_{1}+x_{2}\right)\left(x_{1}^{2}+x_{2}^{2}\right)-\left(x_{1}^{2} x_{2}+x_{1} x_{2}^{2}\right)= \\
=-p s_{2}-x_{1} x_{2}\left(x_{1}+x_{2}\right)=-p s_{2}+p q
\end{gathered}
$$

both terms are divisible by the second power of $r$, so $s_{3}$ is as well. Similarly,

$$
\begin{aligned}
s_{4} & =x_{1}^{4}+x_{2}^{4}=\left(x_{1}+x_{2}\right) s_{3}-\left(x_{1}^{3} x_{2}+x_{1} x_{2}^{3}\right)=-p s_{3}-x_{1} x_{2}\left(x_{1}^{2}+x_{2}^{2}\right)= \\
& =-p s_{3}-q s_{2}
\end{aligned}
$$

and considering the second term, we can only state that $s_{4}$ is divisible by $r^{2}$.

Let $e_{n}$ denote the largest exponent for which $s_{n}$ is divisible by $r^{e_{n}}$, so far we have found:

$$
\begin{aligned}
n & =1,2,3,4 \quad \text { for } \\
e_{n} & =1,1,2,2
\end{aligned}
$$

that is, increasing $n$ by 1, $e_{n}$ either remained unchanged or increased by 1: $e_{n}-e_{n-1}=0$ or 1 (if $n \leqq 4$). We can also say this: $e_{n}$ alternately remained or increased, and increasing $n$ by 2, $e_{n}$ always increased by 1. We will generally prove the latter.

2. Since $x_{1}$ and $x_{2}$ are roots of (1), we have

$$
x_{1}^{2}+p x_{1}+q=0 \quad \text { and } \quad x_{2}^{2}+p x_{2}+q=0
$$

Multiplying these by $x_{1}^{n-2}$ and $x_{2}^{n-2}$ respectively, then adding and rearranging,

$$
\begin{gathered}
\left(x_{1}^{n}+x_{2}^{n}\right)+p\left(x_{1}^{n-1}+x_{2}^{n-1}\right)+q\left(x_{1}^{n-2}+x_{2}^{n-2}\right)=0 \\
s_{n}=-p s_{n-1}-q s_{n-2}
\end{gathered}
$$

The first term on the right side is divisible by a power of $r$ one higher than $s_{n-1}$, and the second by a power of $r$ one higher than $s_{n-2}$, that is, in them the base $r$ appears with exponents $\left(e_{n-1}+1\right)$ and $\left(e_{n-2}+1\right)$. If therefore $e_{n-1}=e_{n-2}$, then for $s_{n}$

$$
e_{n}=e_{n-1}+1
$$

and with the same reasoning for

$$
s_{n+1}=-p s_{n}-q s_{n-1} \quad \text { we have } \quad e_{n+1}=e_{n}
$$

that is, in the sequence of exponents, two consecutive equal terms - if there is such a pair - are followed by two equal terms one higher, specifically for $n-1=4$, $e_{5}=e_{6}=3$; if, however, $e_{n-1}=e_{n-2}+1$, then similarly

$$
e_{n}=e_{n-1}, \quad \text { and } \quad e_{n+1}=e_{n}+1
$$

that is, if an exponent in the sequence is followed by one one higher, then the next term equals the last, and the one following that is one higher, specifically for $n-1=5$, $e_{6}=3$ and $e_{7}=4$.

Since for $n \leqq 4$ no other relationship was found between $e_{n-1}$ and $e_{n-2}$, this proves that the observed regularities generally hold, that is, for even $n$, $n=2,4, \ldots, 2 m \ldots$, $e_{n}=1,2, \ldots, m, \ldots$, and for odd $n$, $n=1,3,5, \ldots, 2 m-1$, $e_{n}=1,2, \ldots, m$, that is,

$$
e_{2 m-1}=e_{2 m}=m,
$$

which, using the integer part notation [ ] for numbers, can be summarized as:

$$
e_{n}=\left[\frac{n+1}{2}\right]
$$

that is, $s_{n}$ is divisible by every $r^{k}$ for which

$$
1 \leqq k \leqq e_{n}=\left[\frac{n+1}{2}\right]
$$