1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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 $

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Listing won't help me Sir. I need to find what Integers appear infinitely many times. $\endgroup$ – user567182 Jun 28 '18 at 17:15
  • $\begingroup$ Whatever you wrote, is supposed to be a comment. Not an answer I guess $\endgroup$ – user567182 Jun 28 '18 at 17:16
  • $\begingroup$ @user567182 You obviously didn't try what Ross suggested. If you had, you would quickly have figured out the complete answer. $\endgroup$ – David K Jun 28 '18 at 17:21
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan Jun 28 '18 at 17:21
  • $\begingroup$ With the hint above I didn't even need 20 numbers. The pattern becomes clear very quickly. $\endgroup$ – David K Jun 28 '18 at 17:22
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.