Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.