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

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.

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

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$

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

• Listing won't help me Sir. I need to find what Integers appear infinitely many times. – user567182 Jun 28 '18 at 17:15
• Whatever you wrote, is supposed to be a comment. Not an answer I guess – user567182 Jun 28 '18 at 17:16
• @user567182 You obviously didn't try what Ross suggested. If you had, you would quickly have figured out the complete answer. – David K Jun 28 '18 at 17:21
• @user567182: you asked for a way to make the list and I provided one. I don't think there is anything easier than just computing them. There are only $20$ of them, so doing it by hand is also reasonable. The point of doing the mod along the way is to avoid overflow. What you said, that $3^{40} \equiv 1 \pmod {100}$ is enough to show that each one on the list recurs infinitely many times. – Ross Millikan Jun 28 '18 at 17:21
• With the hint above I didn't even need 20 numbers. The pattern becomes clear very quickly. – David K Jun 28 '18 at 17:22

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

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