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.

How would I be able to simplify

$$2^x\mod 10^9$$

Since there are only $10^9$ possible values mod $10^9$, somewhere the pattern must repeat. I could have a computer program trudge through it, but I'm dealing with storing potentially 10 billion values and I'm guessing there's an easier way. I need to be able to calculate this for values of $x$ as low as $3$ and values too high to be effectively stored. I can't use Euler's Theorem since $\gcd(2,10)\ne1$.

share|improve this question
1  
You don't have to store all ten billion numbers. Since $(a\mod m)\cdot(b\mod m)\mod m=a\cdot b\mod m$, start at $a_0=1$, and repeatedly calculate $a_n=a_{n-1}x\mod m$ until you get $a_n=1$. That way, you only need to store $a_{n-1}$. –  Mario Carneiro Dec 11 '12 at 23:36
    
Also, $10^9$ is one billion. –  Mario Carneiro Dec 11 '12 at 23:37
    
By the way, what do you mean by "simplify"? Since the order of 2 mod $10^9$ is some factor of $10^9$, you can be sure that $2^x=2^{x\mod10^9}$, but is there something else you are after? You can also use addition chains (en.wikipedia.org/wiki/Addition-chain_exponentiation) to simplify the calculation. –  Mario Carneiro Dec 11 '12 at 23:41
    
@MarioCarneiro: You never get $a_n=1$ because a power (higher than the zeroth) of $2$ is never odd. There is a cycle alright, but it's only joined later on -- multiplying by 2 modulo $10^9$ is not injective because $2$ is not coprime with $10^9$. –  Henning Makholm Dec 12 '12 at 0:11
1  
@MarioCarneiro: After $9$ doublings you are at $512$. Since $512 | 10^9$, you will stay on multiples of $512$ forever. That doesn't promise that you will loop there, but it had to be some multiple. –  Ross Millikan Dec 12 '12 at 0:56

3 Answers 3

up vote 2 down vote accepted

The largest power of $2$ that divides $10^9$ is $2^9=512$. From there on we have $$ 2^{9+n} \bmod 10^9 = 2^9\left(2^n \bmod \frac{10^9}{2^9}\right) $$ The sequence $2^n \bmod 5^9$ does satisfy the conditions for Euler's Theorem to apply; we find that it has period $\varphi(5^9)=4\cdot 5^8=1562500$. (Though actually it is not trivial that the period is not some divisor of this -- see Carmichael's theorem).

So we get $$ 2^n \bmod 10^9 = \begin{cases} 2^n \bmod 10^9 & n < 1562509 \\ 2^{((n-9)\bmod 1562500)+9} \bmod 10^9 & n \ge 1562509 \end{cases}$$

share|improve this answer
    
So it looks like I'll need to treat $n<9$ separately, but when my numbers start getting large, I can just store $n\mod 4\times 5^8$. I'm relatively confident I can run with this. Thanks for your help. –  Mike Dec 12 '12 at 4:11

Assuming you're throwing a computer at the problem:

The trick to finding the length of the cycle relatively quickly without using a lot of memory is to compute two sequences: $$ a_n = 2^n\bmod 10^9 \qquad \qquad b_n = 2^{2n} \bmod 10^9 = 4^n \bmod 10^9 $$ Then when you find an $n\ge 1$ such that $a_n=b_n$, you have found a value that is definitely in the cycle, and finding the length of the cycle is then just a matter of iterating from there until you get back to the starting point.

After you have found the period length $N$ you can find the length of the initial part of the sqequence before you enter the cycle by successively calculating $$ a_n = 2^n \bmod 10^9 \qquad \qquad c_n = 2^{N+n} \bmod 10^9 $$ Then the first $n$ such that $a_n=c_n$ is the index where the first repeat of the period starts.

share|improve this answer
    
Actually, if you find $a_n=b_n$ in that first calculation, then $n=kN$, for some $k\in\mathbb N$, but if it is the first time, then $k=1$, i.e. $n=N$, because the initial segment cannot be longer than the cycle. –  Mario Carneiro Dec 12 '12 at 0:32
    
@MarioCarneiro: Is it obvious that the initial segment cannot be longer than the cycle? It is not the case for $2^n \bmod 1024$, for example (cycle length is $1$, but the initial segment contains $10$ values). –  Henning Makholm Dec 12 '12 at 0:35
    
I stand corrected. However, (calling $N'=kN$ the estimated cycle length) you can still go forward with the second part of the calculation without having to know the actual cycle length (since $2^{N'}=2^{kN}=2^N$ for $k\geq1$), and you need only follow up with a recalculation of $N$ as you described if the initial segment is the same as $N'$. –  Mario Carneiro Dec 12 '12 at 0:51

Periodicity with cycle length n at offset m can be expressed by $$ 2^{m+n}-2^m \equiv 0 \pmod {10^9 } \tag 1 $$ Then we can proceed $$ \begin{eqnarray} 2^m ( 2^n - 1 ) &\equiv &0 \pmod{10^9} \tag {2.1} \\ 2^m ( 2^n - 1 ) &= &k \cdot 2^9 \cdot 5^9 & \to m=9 \\ 2^9 ( 2^n - 1 ) &= &k \cdot 2^9 \cdot 5^9 \\ ( 2^n - 1 ) &= &k \cdot 5^9 \tag {2.2} \end{eqnarray}$$ In general we have powers of 5 in $2^n-1$ by $$ \{2^n-1,5\}= \underset{4}{\overset{n}{\sim}} \cdot \left(1+\{n,5 \} \right) \tag 3 $$ where

  • the fraction-like term means 1 if the "numerator" is divisible by the denominator and zero if not
  • the braces expression means the power to which the second argument occurs in the first

So to have the rhs in (3) being at least 9, n must be divisible by 4 and also must contain 5 to the power of 8, so $n = j \cdot 4 \cdot 5^8 $ with any $j \gt 0$ and $$ 2^9(2^{j \cdot 4 \cdot 5^8} -1 )\equiv 0 \pmod {10^9} $$ The cycle-offset is $2^9 = 512$ and the cyclelength is $ 4\cdot 5^8= 1562500$

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.