Application of Gauss sums to calculate the exact values of the number of appearances of elements on cycles of linear recurrences

Using Gauss sums, we solve the problem of obtaining the formulas for the exact values $N(z,u)$ of appearances of $z$ among the elements $u(0),u(1),\dots,u(T-1)$ of a linear recurrence sequence (LRS) $u$ generated by an irreducible polynomial of a degree $m$ over a field $P=\operatorname{GF}(q)$ in the case, when the period of $u$ is equal to $T=(q^m-1)/d$, where $d|(p^j+1)$ for some natural number $j$ and $p=\operatorname{char}P$, that is, $p$ is a semiprimitive number modulo $d$. Such a sequence $u$ is obtained from a LRS of the maximal period $q^m-1$ by regular sampling with step $d$.
The results of the article generalize the formulas for $N(z,u)$ which are well-known in the case of prime $q$ or $z=0$. In fact, we give some formulas for $N(z,u)$ in the following cases: 1) $d=2$; 2) $d>2$ and $z=0$; 3) $d>2$, $z\neq0$, and $d=d_1$ or $d_1=1$, where $d_1=((q^m-1)/(q-1), d)$; 4) $d>2$, $z\neq0$, $d_1=2$, and $d/2$ is odd or $(p^{l_1}+1)/(d/2)$ is even, where $l_1$ is the least positive integer such that $(d/2)\mid(p^{l_1}+1)$. Thus, as a corollary, we have a complete solution of the problem in the situation when $d$ is a prime number.