0
$\begingroup$

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 !

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ $2^{64}=2^{8^2}$, but $2^{8^2}\not=(2^8)^2$. $\endgroup$ – Barry Cipra Nov 25 '16 at 16:10
  • $\begingroup$ @BarryCipra Indeed you're right I re-edit $\endgroup$ – Maman Nov 25 '16 at 16:13
  • 2
    $\begingroup$ 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}$. $\endgroup$ – Arthur Nov 25 '16 at 16:19
  • $\begingroup$ Further to @BarryCipra 's point, $2^{64} = (2^{32})^2 = ((2^{16})^2)^2 = (((2^8)^2)^2)^2$ $\endgroup$ – Joffan Nov 25 '16 at 16:19
  • $\begingroup$ @Arthur It means that $2$ is not invertible in $(\mathbb{Z}/1000\mathbb{Z})^{\times}$ ? $\endgroup$ – Maman Nov 25 '16 at 16:22
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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$

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

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you, so we can use the Euler-Fermat theorem but with very restrictive conditions ! $\endgroup$ – Maman Nov 25 '16 at 17:14
  • $\begingroup$ So what could be the theorem with this hypothesis ? I tried $6$ and $60$ it fails for instance. $\endgroup$ – Maman Nov 25 '16 at 19:53
  • $\begingroup$ $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$. $\endgroup$ – Joffan Nov 25 '16 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.