Brazilian Math Olympiad

Let $(a_n^{(i)})$ be the sequence of integers obtained by shifting $a_n$ by $i$ positions, i.e., $a_n^{(i)}=a_{n+i}$. Then $$(a_n^{(0)}),(a_n^{(1)}),\dots ,(a_n^{(k)})$$ is a basis for the $k$-dimensional $C$-vector space of sequences $(b_n)$ satisfying $$b_{n+k}=c_{k-1}{b}_{n+k-1}+\cdots +c_0{b}_n(n\ge 0)(\ast )$$ In fact, any non-trivial $C$-linear relation among $(a_n^{(0)},\dots ,a_n^{(k-1)})$ would imply that $k$ is not minimal.

Now let $$f(x)=x^k-c_{k-1}{x}^{k-1}-\cdots -c_0$$ and ${\alpha }_1,\dots ,{\alpha }_k$ be the roots of $f(x)$ (listed with multiplicity). First, observe that all coefficients $c_i$ are rational since they are solutions to the linear system with integer coefficients $$\left(\begin{array}{cccc}{a}_0& a_1& \dots & a_{k-1}\\ a_1& a_2& \dots & a_k\\ ⋮& ⋮& \ddots & ⋮\\ a_{k-1}& a_k& \dots & a_{2k-2}\end{array}\right)\left(\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{k-1}\end{array}\right)=\left(\begin{array}{c}{a}_k\\ a_{k+1}\\ ⋮\\ a_{2k-1}\end{array}\right)$$

$$t_n={\alpha }_1^n+{\alpha }_2^n+\cdots +{\alpha }_k^n(n\ge 0)$$ Then all $t_n\in \mathbb{Q}$ (they are symmetric expression on the roots of $f(x)\in \mathbb{Q}[x]$) and the $t_n$ satisfy $(\ast )$, hence there are $r_i$ such that $$t_n=r_0{a}_n^{(0)}+r_1{a}_n^{(1)}+\cdots +r_{k-1}{a}_n^{(k-1)}$$

To sum up, if $d>0$ is an integer such that $d{r}_i\in \mathbb{Z}$, $i=0,1,\dots ,k-1$, then $$d{t}_n\in \mathbb{Z}$$ for all $n$. Next, we show that this implies that the ${\alpha }_i$ are algebraic integers, which in turn implies that all the $c_i$ are integers, finishing the problem. By Newton's identities, we may write the elementary symmetric polynomials in ${\alpha }^n$ as polynomials with rational coefficients of $$\begin{array}{rl}{t}_n& ={\alpha }_1^n+\cdots +{\alpha }_k^n\\ t_{2n}& ={\alpha }_1^{2n}+\cdots +{\alpha }_k^{2n}\\ & ⋮\\ t_{kn}& ={\alpha }_1^{kn}+\cdots +{\alpha }_k^{kn}\end{array}$$ Therefore the minimal polynomials of ${\alpha }_i^n$ over $\mathbb{Q}$ have coefficients with bounded denominators, independent of $n$ (they depend only on $d$ and $k$). Hence there exists an integer $\Delta >0$ such that $\Delta \cdot {\alpha }_i^n$ are algebraic integers for all $n$. But that implies that the ring $\mathbb{Z}[{\alpha }_i]$ is contained in the finitely generated $\mathbb{Z}$-module $\frac{1}{\Delta }{\mathcal{O}}_{\mathbb{Q}({\alpha }_i)}$, where ${\mathcal{O}}_{\mathbb{Q}({\alpha }_i)}$ is the ring of algebraic integers in the field $\mathbb{Q}({\alpha }_i)$. Therefore $\mathbb{Z}[{\alpha }_i]$ itself is finitely generated as a $\mathbb{Z}$-module (use the fact that $\mathbb{Z}$ is noetherian or that ${\mathcal{O}}_{\mathbb{Q}({\alpha }_i)}$ is a free $\mathbb{Z}$-module, together with the structure theorem of finitely generated modules over a PID). Hence ${\alpha }_i$ is an algebraic integer, as required.

Alternatively, suppose that ${\alpha }_i$ is not an algebraic integer, so that it has prime ideal factorization $$({\alpha }_i)=p_1^{e_1}\dots p_s^{e_s}$$ with $e_i<0$ for some $i$, say $e_1$. Then $$(\Delta {\alpha }_i^n)=(\Delta )\cdot p_1^{n{e}_1}\dots p_s^{n{e}_s}$$ would have a negative $p_1$-exponent for $n$ sufficiently large, contradicting the fact that $\Delta \cdot {\alpha }_i^n$ is an algebraic integer for all $n\ge 0$.