When does this sequence start repeating itself?

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!

-
I am unclear about the meaning of a term. Look for example at the sequence $1,2,3,4,5,1,2,3,4,5,1,2,\dots$. When should this sequence be considered to start repeating itself? – André Nicolas Jun 8 '12 at 17:26
@AndréNicolas: that sequence starts repeating itself on the first term. Actually in the problem they ask us to find the digit before it starts repeating itself, so I will change the statement of the question to "$k \leq n$." – badatmath Jun 8 '12 at 17:30

1
You can find a formula for k in terms of the prime factorization of gcd(b,q) (namely it is just the max of the exponents appearing). Try a few examples with q = 100 and b ≤ 5 to see what will happen. – Jack Schmidt Jun 8 '12 at 17:34

3
@Yuki: I think he is looking for the "burn in" not the "period". A sequence like this has an erratic initial segment, followed by a periodic segment. He is looking for the length of the initial segment. For instance, 2 mod 100 has initial segment [2] and periodic segment [4, 8, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, 76, 52]. He wants an answer like "length of [2] is 1", I think at least. – Jack Schmidt Jun 8 '12 at 17:36

1
@JackPenny: ow... get it! Thanks for clarifying! =p and sorry for that! – Yuki Jun 8 '12 at 17:41
show 2 more comments

3 Answers

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<q$ 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<n$. 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<n$ the sequence starts repeating, as required.

-

Thank you for the answer! – badatmath Jun 8 '12 at 18:29
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$)! – Yuki Jun 8 '12 at 18:36

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.

-

1
Thanks for your answer! Why must there be a $j_0$ such that $b^{j_0} = b^1$? Why can't the repetition be in the later parts of the sequence? – badatmath Jun 8 '12 at 17:56
but you have to also guarantee that $j_0\le n$ (one of the conditions of the question) – Yuki Jun 8 '12 at 17:59
By the Pigeonhole principle (see link). There are at most $q$ values that $b^j$ can have, so for $j_0 > q$ it must have a value appearing twice. – Zachi Evenor Jun 8 '12 at 18:02
Zachi: what about the sequence $2^j\bmod 8$? Note the original question doesn't assume that $(b,q)=1$. Your broad argument guarantees a loop, but it doesn't guarantee a loop starting 'at the start'. – Steven Stadnicki Jun 8 '12 at 18:28
This guarantees there is a burn-in (so "k" exists) but it does not give a very tight bound on k (it proves k ≤ q for any deterministic "markov" sequence, but in fact for this sequence k ≤ log2(q)). – Jack Schmidt Jun 8 '12 at 18:33
show 1 more comment

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 71, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9299483895301819, "perplexity_flag": "head"}