Integers between $00$ and $99$ Inclusive occur as the last two digits in the decimal expansion of infinitely many $a_i$

Question

Define a sequence $\{a_n\} $ by $$a_1=3$$ and $$a_{i+1}=3^{a_i} \text{ for } i>0.$$

Which Integers between $00$ and $99$ Inclusive occur as the last two digits in the decimal expansion of infinitely many $a_i$?

Attempt By Euler's Totient Function, I know that $$3^{40} \equiv 1 \text{ mod }100$$

Now I want to find what and how the powers of 3 are mod $40$? But I cannot move ahead from here.

Answer 1

$3$ is not a primitive root $\mod 100$. (Most residues are not.) So we don't need $3^{40}\equiv 1$. $3^2 = (10 - 1); 3^{20} = (10-1)^{10}\equiv -10*10 +1\equiv 1 \mod 100$. So $3^{20} \equiv 1 \mod 100$ will do.

So $a_2=3^3 = 27\equiv 7 \mod 20$

$a_3 = 3^{27}\equiv 3^7= (10-1)^3*3 \equiv (30 - 1)*3 \equiv 87\mod 100$ and $a_3 \equiv 7 \mod 20$.

$a_4 = 3^{a_3}\equiv 3^7\equiv 87 \mod 100$.

So $a_n \equiv 87 \mod 100$ for all $n \ge 3$.

Answer 2

Just list them. A spreadsheet makes it easy. Start with $1$, then below it type =MOD(3*up,100) and copy down.

Answer 3

Find the smallest $n$ such that $3^n\equiv 1 \pmod 100$

You are correct that $\phi(100) = 40$ so the $n$ divides $40$

Check $3, 3^2, 3^4, 3^5, 3^{10}, 3^{20}$

Something to think about.

$1^2 \equiv 51^2 \equiv 49^2 \equiv 99^2\equiv 1 \pmod {100}$

Since there are 4 numbers that square to 1, it implies that $a^{20}\equiv 1 \pmod{100}$ for any $a$ coprime with $100$

Answer 4

You are incrementally building a tower of powers, $3^{\large 3^{\large 3^{\large 3 \cdots}}} \bmod 100$. This will quickly find a constant value, since the higher exponents get eliminated by the cycling of the lower exponents through ever-smaller cycles.

$3^k \bmod 100$ cycles for $k$ on some divisor of $\lambda(100)=20$, where $\lambda()$ is the least universal exponent or Carmichael function, always a divisor of Euler's totient for composite numbers.

Then $3^{\large k^m} \bmod 100$ will cycle for $m$ on some divisor of $\lambda(20)=4$, and $3^{\large k^{m^n}} \bmod 100$ will cycle on the parity of $n$ since $\lambda(4)=2$. In this case we already know that $n$ will be odd so the values will be constant from at most $i=4$.

$\bmod 100: \\ a_1 \equiv 3 \\ a_2 \equiv 3^3 \equiv 27 \\ a_3 \equiv 3^{27} \equiv 3^7 \equiv 87 \\ a_4 \equiv 3^{87} \equiv 3^7 \equiv 87 $