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$.
Answer
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}$$
No comments:
Post a Comment