# how to prove the periodity of an LFSR

everywhere I've searched it says that the minimal period of an LFSR given by a characteristic polynomial $c(x)$ is the least number $r \in \mathbb{N}$ that: $$c(x)|(x^r-1)$$ but how do I prove it's correctness? I've tried o prove it like that: given $c(x)$ the characteristic polynomial and $h(x)$ theinitial state polynomial, I'll denote the minimal period with $\pi$ then: $${h(x) \over c(x)}=G(x)= \sum^\infty_{k=0}a_kx^k=\sum^{\pi -1}_{k=0}a_kx^k(1+x^\pi+x^{2\pi}...)={\sum^{\pi -1}_{k=0}a_kx^k \over 1-x^\pi}$$ and I'm not sure where to go from here

• What have you tried? Note that the answer is already covered by my answer to cs.stackexchange.com/q/49482/755, so this is effectively already answered by that question (I derive the answer to this question in my answer over there), but you said you didn't understand that answer. So, please tell us in the question what you have tried and what you do understand, to make clear your expectations about what level of an answer you're looking for, so people can know what kind of answer will be useful to you. Do you know group theory? finite fields? modular arithmetic? – D.W. Nov 18 '15 at 2:22
• See also cs.stackexchange.com/q/43707/755 for a related topic. – D.W. Nov 18 '15 at 2:24

## 1 Answer

Hint: The LFSR changes its state by multiplying it by $x$ modulo $c(x)$. So if the initial state is $x_0$, the state after $t$ steps is $x_t \equiv x_0 x^t \pmod{c(x)}$. In particular, $x_t = x_0$ if $x_0 (x^t-1) \equiv 0 \pmod{c(x)}$.