# Thread: Very tricky and interesting modular question

1. ## Very tricky and interesting modular question

This is a very tricky question:
Find the last three digits of
2008^2007^2006^2005^...^1

If you're having trouble thinking about how the exponents are arranged, just imagine every consecutive number a power of the previous.

Good luck, I know the answer, and will tell you if you get it!

2. Originally Posted by elemental
This is a very tricky question:
Find the last three digits of
2008^2007^2006^2005^...^1

If you're having trouble thinking about how the exponents are arranged, just imagine every consecutive number a power of the previous.

Good luck, I know the answer, and will tell you if you get it!
James Bond +1 ?

3. Originally Posted by elemental
This is a very tricky question:
Find the last three digits of
2008^2007^2006^2005^...^1

If you're having trouble thinking about how the exponents are arranged, just imagine every consecutive number a power of the previous.

Good luck, I know the answer, and will tell you if you get it!
Spoiler:

Preamble: I think there's a more elegant way to write down the same type of reasoning, but this is the first that came to mind.

Combination of Euler's theorem and Chinese remainder theorem.

$2008^{2007^{2006^{\dots^{1}}}} \equiv 8^{2007^{2006^{\dots^{1}}}} \equiv x\ (\text{mod}\ 1000)$

Solve

$8^{2007^{2006^{\dots^{1}}}} \equiv a\ (\text{mod}\ 2^3)$

$8^{2007^{2006^{\dots^{1}}}} \equiv b\ (\text{mod}\ 5^3)$

and then combine with CRT.

Note that $8^{2007^{2006^{\dots^{1}}}} \equiv 0\ (\text{mod}\ 2^3)$

Solve $8^{2007^{2006^{\dots^{1}}}} \equiv b\ (\text{mod}\ 5^3)$

$\gcd(8,5^3) = 1$

Use Euler's theorem

$\varphi(5^3)=100$

Reduce to finding $2007^{2006^{2005^{\dots^{1}}}} \equiv 7^{2006^{2005^{\dots^{1}}}} \equiv c\ (\text{mod}\ 100)$

$\gcd(7,100) = 1$

Use Euler's theorem

$\varphi(100)=40=2^3\cdot5$

$2006^{2005^{2004^{\dots^{1}}}} \equiv 6^{2005^{2004^{\dots^{1}}}} \equiv d\ (\text{mod}\ 40)$

$\gcd(6,40) = 2$

Solve

$6^{2005^{2004^{\dots^{1}}}} \equiv e\ (\text{mod}\ 2^3)$

$6^{2005^{2004^{\dots^{1}}}} \equiv f\ (\text{mod}\ 5)$

Note that $6^{2005^{2004^{\dots^{1}}}} \equiv 0\ (\text{mod}\ 2^3)$

Note that $6^{2005^{2004^{\dots^{1}}}} \equiv 1^{2005^{2004^{\dots^{1}}}} \equiv 1\ (\text{mod}\ 5)$

Now work backwards...

CRT: $2006^{2005^{2004^{\dots^{1}}}} \equiv 16\ (\text{mod}\ 40)$

Euler: $2007^{2006^{2005^{\dots^{1}}}} \equiv 7^{16} \equiv 1\ (\text{mod}\ 100)$

Euler: $2008^{2007^{2006^{\dots^{1}}}} \equiv 8^1\ \equiv 8\ (\text{mod}\ 5^3)$

CRT: $2008^{2007^{2006^{\dots^{1}}}} \equiv 8\ (\text{mod}\ 1000)$

So the answer is 008

Just like Also sprach Zarathustra said!

4. ## Ignore

Originally Posted by elemental
This is a very tricky question:
Find the last three digits of
2008^2007^2006^2005^...^1

If you're having trouble thinking about how the exponents are arranged, just imagine every consecutive number a power of the previous.

Good luck, I know the answer, and will tell you if you get it!
Assuming you meant $2008^{2007^{2006^{2005^{2004...^{1}}}}}$, call it $P$ and let $a=2007^{2006^{2005^{2004...^{1}}}}$ and $b=2006^{2005^{2004...^{1}}}$.

I start with the fact that $2008\equiv 3\equiv -2(mod\ 5)$.

$b=2k$ for some integer $k$, so $a=2007^b=2007^{2k}\equiv 3^{2k}\equiv 9^k\equiv 1(mod\ 4)$.
$a=4t+1$ for some integer $t$, so $(-2)^a=(-2)^{4t+1}=16^t(-2)\equiv-2(mod\ 5)$

Now, $P=2008^a\equiv (-2)^a\equiv(-2)(mod\ 5)$. Also, obviously $P$ is even, hence $P\equiv -2(mod\ 2)$. These two congruences give $P\equiv -2\equiv 8(mod\ 10)$.

The last digit of $2008^{2007^{2006^{2005^{2004...^{1}}}}}$ is $8$.

5. Well done guys, 008 is indeed correct.

6. Challenge questions belong in the Challenege Questions subforum (read the rules at that subforum before posting in it).

7. We wish to find out the remainder when $2006^{2005^{...}}$ is divided by $40$

Let $x$ be $2006^{2005^{...}}$

then

$x \equiv 1 \bmod{5}$ and

$x \equiv 0 \bmod{8}$ so

$\boxed{ x \equiv 16 \bmod{40} }$

Then consider $7^x$ in modulo $100$

it is $7^{40k + 16} \equiv 7^{16 }\bmod{100}$

Let $y = 7^{16 }$ we have

$y \equiv (-1)^{16} \equiv 1 \bmod{4}$ and

$y = 7^{16} = (49)^8 \equiv (-1)^8 \equiv 1 \bmod{25}$ so

$y \equiv 1 \bmod{100}$

Then $8^y$ in modulo $125$

Since $(8,125) = 1$ we have $8^{100} \equiv 1$

Therefore , $8^y = 8^{100k + 1 } \equiv 8 \bmod{125}$

Together with $8^y \equiv 0 \bmod{8}$ we obtain $8^y \equiv 8 \bmod{1000}$

Actually , the answer is exactly $8 \equiv 8^y \equiv (2008)^y \bmod{1000}$