Two Two Nine Nine Nine

Number Theory Level 3

$\LARGE 2^{999}$

Find the last 2 digits of the number above.

The answer is 88.

2 solutions

Shubham Jalan
Jun 6, 2015

2^1 : 2, 2^2 : 4, 2^4 : 16, 2^8 : 56, 2^16 : 36, 2^32 : 96, 2^64 : 16,

2^4 :2^64:16 (repeats after 60 powers,atleast) So, 2^964:16

2^999 : 2^964 * 2^32 * 2^2 * 2^1 : 16 * 96 * 8 : 36 * 8 : 88

Saud Molaib
Feb 8, 2014

The only way I know how to solve this problem is by listing the first powers of 2 until repetition occurs in the last 2 digits.

$2^{1} = 2$

$2^{2} = 4$

$2^{21} = 2097152$

$2^{22} = 4194304$

It finally repeats! Notice, however, that it does not repeat at $02$ , but instead at $04$ . Because of this, there are $20$ distinct integers that can be in the last 2 digits' place for any power of 2 greater than 1. 999 mod(20)= 19. $2^{19} = 524288$

So the answer is $\boxed{88}$ .

Let's know 3 main points to solve this problem :

when $2^{10}=1024$
when $24^{n}=.........24$ (n is odd number) . However when $24^{n}=.......76$ ( n is even)
when $76^{n} =...........76$ ( it will always come to 76)

So : $2^{999}$ = $(2^{10})^{99}\times 2^{9}=1024^{99}\times 2^{9} =.....24\times 2^{9}=.......24\times 512=.......\boxed{88}$ (here $24^{n}$ while n is odd number)

Sopheak Seng - 7 years, 4 months ago

There is probably a more clever way to do it, but I don't know it!

Saud Molaib - 7 years, 4 months ago

yeah modulo aritmatic is the most efficient way h

Aditya Dutta - 7 years, 3 months ago

Yes, there is a simpler way using Euler's Theorem and basic modular arithmetic. The idea is to compute the residues modulo coprime factors of $100$ that multiply upto $100$ and to note that $\gcd(2,25)=1$ which allows us to use Euler's Theorem.

$2^{999}\equiv\begin{cases}0\pmod{4=2^2}\\ 2^{999~\bmod~\phi(25)}\equiv 2^{999~\bmod~20}\equiv 2^{-1}\equiv 13\pmod{25}\end{cases}$

The second result is computed using Extended Euclidean Algorithm using the following result:

$1=\gcd(2,25)=\color{#3D99F6}{13}\times 2 + (-1)\times 25$

Now, you can simply use Chinese Remainder Theorem or you can list out the possible values using the second congruence result and use the first congruence result to rule out the incorrect answers and get the correct answer as $88$ .

Prasun Biswas - 6 years ago

Would you elaborate the step wher e2^999 is evaluated to 13(mod 25)?

Shubham Jalan - 6 years ago

Are you familiar with Euler's Theorem and modular inverse of an element coprime to modulo?

For the last step, here's a simpler approach. Let $z$ be the modular inverse of $2$ modulo $25$ . Then, we have,

$\mod~25: z\equiv 2^{-1}\implies 2z\equiv 1\overset{\times 13}{\implies} 26z\equiv 13\implies z\equiv 13$

Prasun Biswas - 6 years ago

@Prasun Biswas – Got it:

1) the totient theorem to find period of repetition of modular values

2) Extended Euclidean to find inverse of 2 w.r.t 25

Shubham Jalan - 6 years ago

@Shubham Jalan – There's a bit of a technical flaw in the first point. You don't always get the (smallest) period of repetition by totient function.

For that purpose, we have the Carmichael Lambda Function .

Prasun Biswas - 6 years ago

I used MS Excel and found the pattern of the units and tens digits individually

Kamala Ramakrishnan - 6 years ago

Two Two Nine Nine Nine

The answer is 88.

2 solutions

0 pending reports