An isomorphism between linear recurring sequences and algebraic rings. (Q5922389)

Für eine feste natürliche Zahl \(k\) und feste ganze rationale Zahlen \(a_1,\ldots,a_k\) betrachte man alle Folgen ganzer rationaler Zahlen \(u_0, u_1, u_2,\ldots\), kurz \((u_n)\), die der Rekursionsformel \[ u_{n+k}=a_1u_{n+k-1}+\cdots+ a_ku_n\qquad \text{für}\quad n\geqq 0 \] genügen. Ist \(x\) eine Unbestimmte, so läßt sich durch Zusammensetzung der Operationen \[ \begin{alignedat}{2} &(v_n) &+&\;(w_n) = (v_n + w_n),\\ &t(v_n)& =&\;(tv_n) \;\text{für ganzes} \;t,\\ &x(v_n)& =&\;(v_{n+1}) \end{alignedat} \] offenbar zu jedem Polynom \(g(x)\) mit ganzen Koeffizienten die Folge \(g(x)(u_n)\) erklären. Setzt man \[ f (x) = x^k - a_1ix^{k-1}-\cdots- a_n, \] so besteht zwischen den Restklassen des Ringes dieser Polynome nach \(f(x)\) und den Folgen \((u_n)\) eine eineindeutige Zuordnung, bei der allgemein der Restklasse des Polynoms \(h(x)\) die Folge \(h(x)(w_n)\) entspricht, wo \[ w_0 = w_1 = \cdots = w_{k-2} = 0,\qquad w_{k-1}=1 \] ist. Wählt man für \(h(x)\) insbesondere das eindeutig bestimmte Element der Restklasse, dessen Grad kleiner als \(k\) ist, so erhält \(x^{k-1}\) in \(h(x)\) den Koeffizienten \(u_0\). Allgemeiner: Für jedes \(i\geqq 0\) hat in diesem Falle \(x^{k-1}\) in demjenigen Element der \(x^ih(x)\) enthaltenden Restklasse, dessen Grad kleiner als \(k\) ist, den Koeffizienten \(u_i\). Diese Zuordnung verhilft nun zu einer Anzahl von Sätzen über die Teilbarkeitsverhältnisse der einzelnen Glieder der Folge \((u_n)\). Insbesondere interessieren die Periode von \((u_n) \mod m\), d. h. das kleinste \(\tau > 0\), zu dem es ein \(n_0\) mit \[ u_{n+\tau}\equiv u_n\;(\text{mod}\;m) \qquad \text{für} \quad n\geqq n_0 \] gibt (speziell das System der den Potenzen \(m = p^j\) einer festen Primzahl \(p\) entsprechenden Perioden), sowie das kleinste dazu passende \(n_0\) (``numeric'') und mehrere anschließende Begriffe. (III 5 B.)