While reading A course of Mathematical Cryptography by Baumslag et al., I have trouble understanding parts of the proof of Theorem 2.3.3, namely the necessary condition :
Let $n\in\mathbb{N}$ with $n=2^m,m\geq1$ and let $a,b\in\mathbb{Z}$ such that $f:\mathbb{Z}_n\to\mathbb{Z}_n, x\to\overline{a}x+\overline{b}$ is a linear congruence generator. Further let $s\in\{0,1,\dots,n-1\}$ be given and $x_0=\overline{s},x_1=f(x_0),\dots.$ Then the sequence $x_0,x_1,\dots$ is periodic with the maximal period length $n=2^m$ if the following holds:
- $a$ is odd.
- If $m\geq2$ then $a\equiv1\mod{4}.$
- $b$ is odd and $\overline{b}\neq\overline{0}.$
The proof goes as follow for $m\geq2$ and thus $n\geq 4$:
Assume (1), (2) and (3) are satisfied.We show that we obtain maximal period lenth $n = 2^m$ for $x_0=\overline{0}$ which proves the theorem.
Let $x_0=\overline{0}.$ We obtain recursively $$x_k = (\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})\overline{b}$$ for $k\geq1.$ Since $b$ is odd we have
$$x_k=\overline{0}\iff(\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})=\overline{0}.$$
We write $k = 2^rt$ with $r\geq0$ and $t$ odd. Then
$$\overline{0}=(\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})=(\overline{1}+\overline{a}+\dots+\overline{a}^{2^r-1})(\overline{1}+\overline{a}^{2^r}+(\overline{a}^{2^r})^2+\dots+(\overline{a}^{2^r})^{t-1}).$$
The second factor is congruent to 1 modulo 2 and hence
$$2^m|(1+a+\dots+a^{k-1})\iff2^m|(1+a+\dots+a^{2^r-1}).$$
The integer $1+a+\dots+a^{2^r-1}$ is divisible by $2^r$ since it is a sum of $2^r$ odd numbers but not divisible by $2^{r+1}.$ It follows that $r\geq m\iff2^m|k.$ Therefore $x_k=\overline{0}$ occurs for $k\geq1$ for the first time when $k=n=2^m$.
I don't follow the very last part in italic (from "The integer..."). I will be glad if someone could enlighten me.
