# Is there a more efficient method to determine the last

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 ?

• $2^{64}=2^{8^2}$, but $2^{8^2}\not=(2^8)^2$. – Barry Cipra Nov 25 '16 at 16:10
• @BarryCipra Indeed you're right I re-edit – Maman Nov 25 '16 at 16:13
• Be careful using Euler's theorem here! $2$ and $1000$ aren't coprime, so Euler's theorem is not applicable at all. You need to use the Chinese reminder theorem first. More to the point, $2^4 \not \equiv 1 \pmod{10}$. – Arthur Nov 25 '16 at 16:19
• Further to @BarryCipra 's point, $2^{64} = (2^{32})^2 = ((2^{16})^2)^2 = (((2^8)^2)^2)^2$ – Joffan Nov 25 '16 at 16:19
• @Arthur It means that $2$ is not invertible in $(\mathbb{Z}/1000\mathbb{Z})^{\times}$ ? – Maman Nov 25 '16 at 16:22

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.

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$

• OK then we conclude by CRT it's faster indeed... – Maman Nov 25 '16 at 16:48
• Nice. Note that we straightforwardly have $2^{4061}\equiv 2^{61} \bmod 125$ by Euler for smaller numbers. – Joffan Nov 25 '16 at 19:31
• @Joffan true, thank you! – Djura Marinkov Nov 25 '16 at 20:45

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

• Thank you, so we can use the Euler-Fermat theorem but with very restrictive conditions ! – Maman Nov 25 '16 at 17:14
• So what could be the theorem with this hypothesis ? I tried $6$ and $60$ it fails for instance. – Maman Nov 25 '16 at 19:53
• $6$ is not prime, of course, so you need to look at the component prime powers there. So we need to get to a power of $2$ to saturate factors of $2$. $\phi(60) =16$ , $\lambda(60) = 4$ so we should find that $6^{k+4} \equiv 6^{k} \bmod 60$ for all $\fbox{$k\ge 2$}$. Successive powers of $6, \bmod 60$: $6,36, 36, 36, 36, 36, \ldots$ so the assertion is true. A perhaps-confusing factor is that although the order of $6$ divides $\lambda(60)$, in this case it is: $1$. – Joffan Nov 25 '16 at 20:20