I need help proving the following theorem. I found it many books but on every single one it says that they omit the proof because it is in every good textbook.
THM Let $c(x)$ be a connection (characteristic) polynomial of an LFSR of length $n$. Then $c(x)$ is primitive polynomial iff every non-zero initial state of an LFSR produces a pseudorandom sequence of length $2^n-1$.
Definition: A primitive polynomial $f(x)$ is an irreducible polynomial of degree $n$ in $\mathbb F_{2^n}[x]$ with the property that each root of $f$ is a generator of $\mathbb F_{2^n}^\times$, the multiplicative group of $\mathbb F_{2^n}$.
Let $\alpha$ denote a root of the primitive polynomial $$f(x) = f_0 + f_1x + \cdots + f_n x^n = 1 + f_1 x + \cdots + f_{n-1}x^{n-1} + x^n$$ Consider any initial nonzero loading $(s_0, s_1, \ldots, s_{n-1})$ of the linear feedback shift register (LFSR). Note that the $s_i \in \mathbb F_2$ and at least one $s_i$ is nonzero. The first output bit from the register is $s_0$ while the first bit fed back into the register is $$s_n = s_0 + f_{n-1}s_1 + f_{n-2}s_2 + \cdots + f_1s_{n-1}. \tag{1}$$ The next shift register contents are $(s_1, s_2, \ldots, s_n)$. More generally, the contents of the shift register are $(s_m, s_{m+1}, \ldots, s_{m+n-1})$, the bit $s_m$ is the output, the bit $$s_{m+n} = s_m + f_{n-1}s_{m+1} + f_{n-2}s_{m+2} + \cdots + f_1s_{m+n-1}\tag{2}$$ is fed back into the register thus making the contents $(s_{m+1}, s_{m+w}, \ldots, s_{m+n})$.
Now, since $\alpha$ is a root of $f(x)$, we have that for any nonzero $\beta \in \mathbb F_{2^n}$ $$0= \beta f(\alpha) = \sum_{k=0}^n f_k \beta \alpha^k$$ Since the conjugates $\alpha^2$, $\alpha^{2^2}, \cdots,\alpha^{2^i},\cdots, \alpha^{2^{n-1}}$ of $\alpha$ also are roots of $f(x)$, we have similarly (using $\beta^{2^i}$ with $\alpha^{2^i}$) that $$\begin{align} 0 &= \beta^{2^i}f\left(\alpha^{2^i}\right) = \sum_{k=0}^n f_k \beta^{2^i} \left(\alpha^{2^i}\right)^k = \sum_{k=0}^n f_k \beta^{2^i} \left(\alpha^k\right)^{2^i} = \sum_{k=0}^n f_k \left(\beta\alpha^k\right)^{2^i}, & 0 \leq i \leq n-1. \end{align}$$ Adding these $n$ equations and remembering that the trace of $y$: $\operatorname{Tr}(y) = \sum_{i=0}^{n-1} y^{2^i}$ is a homomorphism from $\mathbb F_{2^n}$ to $\mathbb F_2$, we have that $$\sum_{k=0}^n f_k \operatorname{Tr}(\beta\alpha^k) = \operatorname{Tr}(\beta) + f_1\operatorname{Tr}(\beta\alpha) + \cdots + f_{n-1}\operatorname{Tr}(\beta\alpha^{n-1}) + \operatorname{Tr}(\beta\alpha^n) = 0 \tag{3}$$ where the $\operatorname{Tr}(\beta\alpha^k) \in \mathbb F_2$. Now, for each $\beta \in \mathbb F_{2^n}$, $(\operatorname{Tr}(\beta), \operatorname{Tr}(\beta\alpha), \ldots, \operatorname{Tr}(\beta\alpha^{n-1}))$ is the representation of $\beta$ with respect to the dual of the standard polynomial basis $\{1, \alpha, \alpha^2, \ldots, \alpha^{n-1}\}$. Thus, the initial nonzero loading $(s_0, s_1, \ldots, s_{n-1})$ of the shift register can be viewed as the dual-basis representation of some nonzero $\beta \in \mathbb F_{2^n}$. Comparing $(1)$ and $(3)$, we see that the next shift-register contents are $$(s_1, \ldots, s_{n-1}, s_n) = (\operatorname{Tr}(\beta\alpha), \operatorname{Tr}(\beta\alpha^2), \ldots, \operatorname{Tr}(\beta\alpha^{n})) = (\operatorname{Tr}(\beta\alpha), \operatorname{Tr}((\beta\alpha)\cdot\alpha), \ldots, \operatorname{Tr}((\beta\alpha)\cdot\alpha^{n-1})),$$ that is, the representation of $\beta\alpha$ with respect to the dual of the standard polynomial basis.
OK, that shows that $f(x)$ being a primitive polynomial gives an output sequence of period $2^n-1$. The proof in the reverse direction is left for you as an exercise.