# Proof of theorem by Lin and Costello

I want to prove the following theorem in LFSR:

If $$f(x)$$ is a polynomial in $$\text{GF}(2)$$ with exponent $$e$$, which means $$f(x) \mid x^e + 1$$.

I want to prove that $$e \le 2^n -1$$.

I had some attempts in special case that $$f(x)$$ is irreducible polynomial: if we get the period as $$p$$ we can easily prove $$e \le p$$ and from $$p \le 2^n - 1$$. We can then conclude the desired result but only for the special case.

Let me explain the proof I know:

For the case $$f(x)$$ is irreducible: $$S_1(x) = \sum_{i=0}^{p-1} s_i x^i$$ and we know: $$G(x) = \frac{S_1(x)}{1 + x^p}$$, $$G(x) = \frac{\emptyset(x)}{f^\ast(x)}$$ from this we know that $$\deg(\emptyset) < \deg(f)$$, $$\frac{\emptyset(x)}{f^\ast(x)} = \frac{S_1(x)}{1 + x^p}$$ so we conclude $$\emptyset(x)(1 + x^p) = f^\ast(x)S_1(x)$$, $$(\emptyset, f) = 1$$ so we have $$f(x) \mid (1 + x^p) \rightarrow e \le p$$

and we thereachieve the desired result.

• Suggestion: if $p(x)$ is not irreducible, then $p(x) = q_1(x) q_2(x) ... q_k(x)$ for some multiset of irreducible polynomials $q_1, q_2, ..., q_k$. Would that help? Commented Apr 24 at 17:19
• you've omitted the definition of $n$, is it the degree of the polynomial? Commented Apr 24 at 17:57
• Yes, sorry I didn't notice. n is the degree of polynomial Commented Apr 24 at 18:04
• poncho I guess your suggestion doesn't help. If you have any opinion I will acclaim Commented Apr 24 at 18:05