5
$\begingroup$

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$.

  • 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}$.2012-12-11
  • 0
    Also, $10^9$ is one billion.2012-12-11
  • 0
    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 (http://en.wikipedia.org/wiki/Addition-chain_exponentiation) to simplify the calculation.2012-12-11
  • 0
    @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$.2012-12-12
  • 0
    @HenningMakholm Good point. I just checked for this example, and the cycle length is 1562500, with $a_{9}=a_{1562509}=512$ being the first to repeat. Is there anything obvious about 512 that makes this possible?2012-12-12
  • 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.2012-12-12

3 Answers 3

1

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$

3

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.

  • 0
    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.2012-12-12
  • 0
    @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).2012-12-12
  • 0
    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'$.2012-12-12
3

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}$$

  • 0
    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.2012-12-12