# Very tricky and interesting modular question

• Jul 9th 2010, 01:29 PM
elemental
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!
• Jul 9th 2010, 01:57 PM
Also sprach Zarathustra
Quote:

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 ?
• Jul 9th 2010, 03:07 PM
undefined
Quote:

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

Just like Also sprach Zarathustra said!

• Jul 9th 2010, 03:13 PM
melese
Ignore
Quote:

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$.
• Jul 9th 2010, 06:06 PM
elemental
Well done guys, 008 is indeed correct.
• Jul 9th 2010, 08:03 PM
mr fantastic
Challenge questions belong in the Challenege Questions subforum (read the rules at that subforum before posting in it).
• Jul 9th 2010, 08:41 PM
simplependulum
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}$