Is there a more efficient method to determine the last

Question

three digits of $2^{8064}$ ?

Here's my method

I use two powerful hints :

-The first one consists to take the number $\pmod{1000}$ because we want the last three digits.

-The second one is a powerful theorem from Euler-Gauss which shows that if we have an integer of the form $p_1^{k_1}...p_l^{k_l}$ with $p_1,...,p_l$ prime numbers then for every integer $a$ we have $a^{({p_1}^{k_1}-{p_1}^{k_1-1})...{(p_l^{k_l}-p_l^{k_l-1})}}\equiv 1 \pmod{p_1^{k_1}...p_l^{k_l}}$ and $\gcd(p_1^{k_1}...p_l^{k_l},a)=1$.

Applying these two results I get : $1000=2^3\times5^3$ which means that $2^{4\times 100}\equiv 1 \pmod{1000}\Leftrightarrow 2^{400}\equiv 1 \pmod{1000}$. We find a period for the power of $2$. But the problem is that $\gcd(2,1000)\ne 1$. So it won't work with this theorem and its simple hypothesis.

Now using @Joffan's argument on Carmichael, we have the fact that the order of $2$ is $100$. So $2^{100}\equiv 1 \pmod{1000}$.

So $2^{100\times 80+64} \equiv 2^{64}\equiv (((2^8)^2)^2)^2 \equiv 616 \pmod{1000}$

However, excepting computing it is there a faster method ?

Thanks in advance !

Answer 1

You could also use Exponentiation by Squaring, in which you basically notice that $a^{2n}=(a^2)^n$ and $a^{2n+1}=a*a^{2n}$. With modulo arithmetic, you can also use the identity $ab\mod n=(a\mod n)*(b\mod n)$ You might also get a bonus in speed by using Montgomery Reductions, which just converts the multiplication to an easier form.

Answer 2

How about finding reminder of $2^{8061}$ divided by $125$ and then multiply by 8.

$2^{8061}=2(5-1)^{4030}=2(125m+{4030\choose 2}25-4030*5+1)=125k-40300+2 =125n+702\equiv 77 \pmod{125}$

So reminder you're looking for is $77*8=616$

Answer 3

The result for the order of $2$ modulo $1000$ is valid, but with conditions - since $2^3 \mid 1000$ but $2^4 $ does not, we have that $2^{k+400} \equiv 2^k \bmod 1000$ for $k\ge 3$. The $400$ is Euler's totient $\phi(1000)$; we can actually do better with Carmichael's reduced totient $\lambda(1000)=100$ and get $2^{k+100} \equiv 2^k \bmod 1000$ for $k\ge 3$, although that is not needed on this occasion.

Anyway this validates $2^{8064}\equiv 2^{64} \bmod 1000$, since $64>3$, and then we can used exponentiation-by-squaring on $2^8=256$ to get:

$$\begin{align} 2^8 &\equiv 256 \bmod 1000\\ 2^{16} &\equiv 256^2\equiv 65536 \equiv 536 \bmod 1000\\ 2^{32} &\equiv 536^2\equiv 287296 \equiv 296 \bmod 1000\\ 2^{64} &\equiv 296^2\equiv 87616 \equiv 616 \bmod 1000\\ \end{align}$$

So $616$ are your required final digits of $2^{8064}$