exponentiation and modular arithmetic 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$.
 A: 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.
A: 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}$$
A: 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$
