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 !

$\endgroup$
14
  • 2
    $\begingroup$ $2^{64}=2^{8^2}$, but $2^{8^2}\not=(2^8)^2$. $\endgroup$ Nov 25, 2016 at 16:10
  • $\begingroup$ @BarryCipra Indeed you're right I re-edit $\endgroup$
    – Maman
    Nov 25, 2016 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, 2016 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, 2016 at 16:19
  • $\begingroup$ @Arthur It means that $2$ is not invertible in $(\mathbb{Z}/1000\mathbb{Z})^{\times}$ ? $\endgroup$
    – Maman
    Nov 25, 2016 at 16:22

3 Answers 3

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$

$\endgroup$
3
  • $\begingroup$ OK then we conclude by CRT it's faster indeed... $\endgroup$
    – Maman
    Nov 25, 2016 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, 2016 at 19:31
  • $\begingroup$ @Joffan true, thank you! $\endgroup$ Nov 25, 2016 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}$

$\endgroup$
3
  • $\begingroup$ Thank you, so we can use the Euler-Fermat theorem but with very restrictive conditions ! $\endgroup$
    – Maman
    Nov 25, 2016 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, 2016 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, 2016 at 20:20
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.

$\endgroup$

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.