remainder when $a_{1000}$ is divided by $1000$

Question

If $a_{1}=7,a_{2}=7^7,a_{3}=7^{7^{7}}.$ Then the remainder when

$a_{1000}$ is divided by $1000$

what i try

$a_{1}=7=1\mod(1000)$ and

$a_{2}=7^7=1^7\mod(1000)=1\mod(1000)$

from using modulo theorem

$a_{3}=7^{7^{7}}=1^7\mod(1000)=1\mod(7)$

can we say that $a_{1000}= 1\mod(1000)$

Help me to solve it please

Answer 1

The idea of this answer is the same as that of lab bhattacharjee's answer. I'm going to explain the steps in detail.

---

To find $a_{1000}=7^{a_{999}}\pmod{1000}$, the following two steps should help :

• The first step is to find the smallest positive integer $b$ such that $7^b\equiv 1\pmod{1000}$.

• The second step is to find $a_{999}\pmod{b}$.

This is because if we know that $a_{999}$ is of the form $mb+c\ (c\lt b)$ from the second step, then we can get$$a_{1000}=7^{a_{999}}=7^{mb+c}=(7^b)^m\cdot 7^c\equiv 1^m\cdot 7^c\equiv 7^c\pmod{1000}$$

---

The fist step is to find the smallest positive integer $b$ such that $7^b\equiv 1\pmod{1000}$.

Let us observe the pattern :

$$7^1=7,\quad 7^2=49,\quad 7^3=343,\quad 7^4=240\color{red}1$$ This means that the rightmost digit of $7^i\ (i=1,2,\cdots)$ is $$7,9,3,1,7,9,3,1,7,9,3,1,\cdots$$ So, we see that $b$ is a multiple of $4$. So, to find $b$, we only need to consider $7^{4k}\pmod{1000}$ where $k\ge 2\in\mathbb Z$.

$$7^{4k}=(7^4)^k=(2400+1)^{k}$$ $$\stackrel{\text{binomial theorem}}=1+2400\binom k1+\underbrace{2400^2\binom k2+\cdots +2400^k\binom kk}_{\text{each term is divisible by $1000$}}$$ $$\equiv 1+2400k\equiv 1+200k\times 12\pmod{1000}$$ So, we see that the smallest positive $k$ such that $7^{4k}\equiv 1\pmod{1000}$ is $5$.

Therefore, it follows that $b=4\times 5=20$.

---

The second step is to find $a_{999}\pmod{20}$.

Since $a_{998}=7^{\text{odd number}}\equiv (-1)^{\text{odd number}}\equiv -1\equiv 3\pmod 4$, there exists an integer $n$ such that $a_{998}=4n+3$.

Now, we get $$a_{999}=7^{a_{998}}=7^{4n+3}=7^3\cdot (7^2)^{2n}=7^3\cdot (50-1)^{2n}$$ $$\stackrel{\text{binomial theorem}}=7^3\bigg(1-\underbrace{\binom{2n}{1}50^1+\binom{2n}{2}50^2-\cdots +\binom{2n}{2n}50^{2n}}_{\text{each term is divisible by $20$}}\bigg)$$ $$\equiv 7^3\cdot 1\equiv 343\equiv 3\pmod{20}$$

---

From the second step, we see that there exists an integer $m$ such that $a_{999}=20m+3$.

Hence, we finally get $$a_{1000}=7^{a_{999}}=7^{20m+3}=(7^{20})^m\cdot 7^3\equiv 1^m\cdot 7^3\equiv \color{red}{343}\pmod{1000}$$

Answer 2

$a_1=7\equiv\color{red}7\bmod 1000$.

$a_2=7^7=823543\equiv543\bmod 1000$.

$7^4=2401\equiv401\bmod1000,$ so $7^{20}=(7^4)^5\equiv401^5=(400+1)^5\equiv1\bmod1000$.

Since $a_2\equiv543\bmod1000,$ $a_2\equiv3\bmod20$. Therefore, $a_3=7^{a_2}\equiv7^3=343\bmod1000$.

Can you take it from here?

Answer 3

$$7^4=(50-1)^2=2401$$

$$7^{4n}=(1+2400)^n\equiv1+2400n\pmod{1000}$$

So, $n$ must be divisible by $5$ to make residue $\equiv1$

$\implies$ord$_{1000}7=20$

We need $a_{999}\pmod{20}$

Again, $a_r,r\ge2$ are of the form $7^{4n+3}$

$7^{4n+3}=7^3(50-1)^{2n}\equiv3(1-50)^{2n}\equiv3(1-\binom{2n}150)\pmod{20}\equiv3$

So for $r\ge2,$ $$a_{r+1}\equiv7^{3\pmod{20}}\pmod{1000}\equiv7^3$$

Answer 4

This can be solved by induction. We want to show that if $a_n \mod 1000 \equiv 343 \Rightarrow a_{n+1} \mod 1000 \equiv 343$

Notice that if $n\ge 1$ then $a_{n+1}=7^{a_n}$ $\left( \text{then obviously } a_{n+1}\mod 1000\equiv 7^{a_n} \right)$. Also notice that powers of 7 modulo 1000 have a cycle of 20 numbers.

$7^{20y+1}\mod 1000 \equiv 7$

$7^{20y+2}\mod 1000 \equiv 49$

$7^{20y+3}\mod 1000 \equiv 343$

$7^{20y+4}\mod 1000 \equiv 401$

$7^{20y+5}\mod 1000 \equiv 807$

$7^{20y+6}\mod 1000 \equiv 649$

$7^{20y+7}\mod 1000 \equiv 543$

$7^{20y+8}\mod 1000 \equiv 801$

$7^{20y+9}\mod 1000 \equiv 607$

$7^{20y+10}\mod 1000 \equiv 249$

$7^{20y+11}\mod 1000 \equiv 743$

$7^{20y+12}\mod 1000 \equiv 201$

$7^{20y+13}\mod 1000 \equiv 407$

$7^{20y+14}\mod 1000 \equiv 849$

$7^{20y+15}\mod 1000 \equiv 943$

$7^{20y+16}\mod 1000 \equiv 601$

$7^{20y+17}\mod 1000 \equiv 207$

$7^{20y+18}\mod 1000 \equiv 449$

$7^{20y+19}\mod 1000 \equiv 143$

$7^{20y}\mod 1000 \equiv 1$

Where $y \in \Bbb{Z}$

So knowing the remainder of $a_n$ mod 20 is sufficient to determine the remainder of $a_{n+1}$ mod 1000. An alternative way of stating $a_{n} \mod 1000 \equiv 343$ is $\exists x\in\Bbb{Z}\space|\space1000x+343=a_n$.

$20(50x+17)+3=a_n\Rightarrow$ $ a_n \mod 20 \equiv 3$

This means that $a_{n+1} \mod 1000 \equiv 343$.

So if $a_n \mod 1000 \equiv 343$ then any $a_k \mod 1000 \equiv 343$ where $k\ge n$.

$a_2=7^7=823543=20(41177)+3$

$a_2 \mod 20 \equiv 3\Rightarrow$ $a_3 \mod 1000 \equiv 343$

Therefore all $a_k \mod 1000 \equiv 343$ where $k\ge 3$. This includes $a_{1000}$.