Note that if $\gcd(b,q)=1$, then (by Euler's Theorem) there exists $n_0$ such that $b^{n_0}\equiv1\mod q$, so, in this case, $a_1=a_{n_0+1}$, and $k=1$.
Otherwise, let $m=\gcd(b,q)$. By condition $q<2^n$, we have that $q$ has at most $n-1$ products of $m$, (since $m^n\ge2^n>q$), so if $q$ and $b$ has exactly the same primes in their prime factorization, then $q=lb$ (we can assume $bl$ and then $b^{n-1}\equiv 0\mod q$, so, the sequence starts repeating for $k=n-11,b'=b^{n-1}/m'$. In this case, $\gcd(b,q')=1$, so there exists $n_1$ such that $b^{n_1}\equiv 1\mod q'$, that is
$$
b'b^{n_1}\equiv b'\mod q'
$$
So (by properties of $\textit mod$):
$$
b^{n-1}b^{n_1}\equiv b^{n-1}\mod q
$$
and so, $a_{n-1}=a_{(n-1)+n_1}$, so if we set $k=n-1