3
$\begingroup$

Given the sequence $a_j = b^j \mod q$, where $1 < b, q < 2^n$, how can I prove that the sequence starts repeating itself at some term $a_k$ where $k \leq n$?

I have been looking at this problem for hours and am completely stuck on how to do it :/ Any help would be appreciated!

  • 0
    The **period** can be large, there are plenty of cases ($q$ prime, $b$ any of the primitive roots of $q$) where the period is $q-1$, much larger than $n$. "Burn in" length is another matter.2012-06-08

3 Answers 3

3

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 $b since otherwise, we take $b_0=b\mod q$), with $l<2^n$, and then, $b^{n-1}>l$ and then $b^{n-1}\equiv 0\mod q$, so, the sequence starts repeating for $k=n-1. Otherwise, for $p=(n-1)+l$, for any $l\ge0$, we have $ a_p=b^{n-1}b^l\mod q $ Define $m'=\gcd(b^{n-1},q), q'=q/m'>1,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 the sequence starts repeating, as required.

  • 0
    You're welcome. =p But I've missed a detail (Steven Stadnicki example): suppose $q$ not multiple of $b$ (so, you guarantee that q'>1)!2012-06-08
1

Do it by the Pigeonhole principle. The sequence $b^j \bmod q$ can get at most $q$ values, namely $\{0,1,...,q-1\}$. So there is $j_0$ such that $b^{j_0} = b^1$ and it then clear that the sequence starts repeat itself (since e.g. $b^{j_0 + 1} \bmod q = b^{j_0} b^1 = b^1 b^1 = b^2 \bmod q$ and so on). I, of course, assumed that $b > 1$ is an integer.

  • 0
    @StevenSt$a$dnicki I probably missed that two conditions, and saw only that need to proove the existence of a loop.2012-06-08
1

If $\gcd(b,q)=1$, there is repetition from the beginning. Suppose that $\gcd(b,q)=d>1$. Let $q=q'r$, where $\gcd(q',b)=1$. Then any prime that divides $r$ must divide $b$.

Let $e$ be the smallest exponent such that $r$ divides $b^e$. Since $q \lt 2^n$, we have $e \lt n$. The powers of $b$ are periodic modulo $q'$ from the beginning. But they are congruent to $0$ modulo $r$ from $b^e$ on, so they are periodic modulo $q$ from $b^e$ on.