9
$\begingroup$

While fooling around with exponential towers I noticed something odd:

$$ 3^{3} \equiv 2\underline{7} \mod 100000 $$ $$ 3^{3^{3}} \equiv 849\underline{87} \mod 100000 $$ $$ 3^{3^{3^{3}}} \equiv 39\underline{387} \mod 100000 $$ $$ 3^{3^{3^{3^{3}}}} \equiv 5\underline{5387} \mod 100000 $$ $$ 3^{3^{3^{3^{3^{3}}}}} \equiv \underline{95387} \mod 100000 $$ $$ \dots$$

It seems that the last digits always converge to a fixed sequence! Is this really true and if yes - can someone think of a proof for this statement?

Any kind of help will be appreciated

$\endgroup$
  • 1
    $\begingroup$ A tower of $n\ge 6$ threes always ends with $95387$, because $3^{3^{\ldots}\pmod{\lambda(100000)}}\equiv 3^{95387\pmod{5000}}\equiv 3^{387}\equiv 3^{9\cdot 43}\equiv 95387\pmod{100000}$ by a bit of calculation. $\endgroup$ – user26486 Feb 22 '15 at 12:18
  • 1
    $\begingroup$ Similarly, any tower of $9$'s of the size of $n\ge 4$ is the same $\pmod{1000}$ (see Robert Israel's comment here). $\endgroup$ – user26486 Feb 22 '15 at 12:21
  • 1
    $\begingroup$ To prove your conjecture it is sufficient to prove the '$\stackrel{\text{?}}\equiv$' in $3^{\underbrace{3^{\ldots}}_{n\text{ threes}}}\equiv k\pmod{10^n}\implies 3^{3^{\underbrace{3^{\ldots}}_{n\text{ threes}}}\pmod{\lambda(10^n)}}\equiv 3^{k\pmod{2^{n-2}5^{n-1}}}\stackrel{\text{?}}\equiv k\pmod{10^n}$ for $n\ge 4$ (only then $\lambda(10^n)=2^{n-2}5^{n-1}$. When $1\le n\le 3$, it is easy to check that it is indeed true, and the equivalences in your question details prove it). $\endgroup$ – user26486 Feb 22 '15 at 12:44
  • $\begingroup$ You could see this question $\endgroup$ – Ross Millikan Feb 22 '15 at 16:18
  • $\begingroup$ A somewhat related answer is mine here. The answer I gave below is fairly similar to that one. $\endgroup$ – Milo Brandt Feb 22 '15 at 16:44
2
$\begingroup$

Yes, they do. To prove this, all we need to know is that exponents are periodic functions mod $n$ with a period of less than $n$. That is to say, for any $b$, there is always some $k<n$ such that, for all large enough $x$ we have: $$b^{x}\equiv b^{x+k}\pmod n.$$ To prove this, we can split into two cases - firstly, if $b$ is coprime to $n$, this follows quickly, because then $k$ can be taken as the multiplicative order of $b$ mod $n$, which must divide $\varphi(n)$ (the order of the multiplicative group mod $n$), which is less than $n$.

If $b$ is not coprime to $n$, then we write, from unique factorization: $$b=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_{c_1}^{\alpha_{c_1}}$$ $$n=p_1^{\beta_1}p_2^{\beta_2}\ldots p_{c_1}^{\beta_{c_1}}q_1^{\kappa_1}q_2^{\kappa_2}\ldots q_{c_2}^{\kappa_{c_2}}$$ where the $p$'s and $q$'s are distinct. Then, if we let $$m_1=p_1^{\beta_1}p_2^{\beta_2}\ldots p_{c_1}^{\beta_{c_1}}$$ $$m_2=q_1^{\kappa_1}q_2^{\kappa_2}\ldots q_{c_2}^{\kappa_{c_2}}$$ we can say that $m_1$ and $m_2$ are coprime and so are $b$ and $m_2$. Notice that $m_2$ can alternatively be defined as the largest divisor of $n$ coprime to $b$. One can go on to show that $b^x\equiv 0 \pmod{m_1}$ for sufficiently large $x$, as for each $p_i$ we have $b^{\beta_i}\equiv 0\pmod{p_i}$. Therefore, for sufficiently large $x$, the function $b^x$ is periodic with period $1$, mod $m_1$. Then, $b$ is coprime to $m_2$ and hence, from before, periodic there with some period less than $m_2$. Using the Chinese Remainder Theorem establishes that the period mod $n=m_1m_2$ is the LCM of the periods mod $m_1$ and $m_2$ and hence is some number less than $m_2$, which is less than $n$.

With this lemma in hand, the rest of the proof is simple; we can set it up as a proof by induction. Obviously, $b^{b^{\ldots}}\pmod 1$ is well-defined (i.e. takes a single value for all large enough towers), since everything integer is equivalent mod $1$. Next, suppose that, for all $n'<n$ we have that $b^{b^{\ldots}}\pmod{n'}$ is well-defined. Then, we can prove it is well-defined for $n$ too, since the value of $b^x$ is determined (for large enough $x$) by knowing $x$ mod some $m<n$. In this case, we have $x=b^{b^{\ldots}}$ and it is clear that, for large enough towers, this satisfies the hypothesis of being a large enough number for $b^x$ to be periodic and further, given the inductive hypothesis, must be well-defined mod $m$. From this, we can conclude that $b^{b^{\ldots}}$ is well-defined mod $n$ for all $b$ and $n$.

$\endgroup$
0
$\begingroup$

This is more of an analysis, rather than a full-proof answer to your question.


In the representation of powers of $3$, each digit repeats periodically as a function of the exponent.

A few examples:

  1. The period of the $1$st digit is $4$:

    • $n\equiv0\pmod{2}\implies3^n\equiv1\pmod{10}$
    • $n\equiv1\pmod{2}\implies3^n\equiv3\pmod{10}$
    • $n\equiv2\pmod{2}\implies3^n\equiv9\pmod{10}$
    • $n\equiv3\pmod{2}\implies3^n\equiv7\pmod{10}$
  2. The period of the $2$nd digit is $20$:

    • $n\equiv 0\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv0\pmod{10}$
    • $n\equiv 1\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv0\pmod{10}$
    • $n\equiv 2\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv0\pmod{10}$
    • $n\equiv 3\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv2\pmod{10}$
    • $n\equiv 4\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv8\pmod{10}$
    • $n\equiv 5\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv4\pmod{10}$
    • $n\equiv 6\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv2\pmod{10}$
    • $n\equiv 7\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv8\pmod{10}$
    • $n\equiv 8\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv6\pmod{10}$
    • $n\equiv 9\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv8\pmod{10}$
    • $n\equiv10\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv4\pmod{10}$
    • $n\equiv11\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv4\pmod{10}$
    • $n\equiv12\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv4\pmod{10}$
    • $n\equiv13\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv2\pmod{10}$
    • $n\equiv14\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv6\pmod{10}$
    • $n\equiv15\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv0\pmod{10}$
    • $n\equiv16\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv2\pmod{10}$
    • $n\equiv17\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv6\pmod{10}$
    • $n\equiv18\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv8\pmod{10}$
    • $n\equiv19\pmod{10}\implies\lfloor\frac{3^n}{10}\rfloor\equiv6\pmod{10}$
  3. The period of the $3$rd digit is $100$...

  4. The period of the $4$th digit is $500$...


Let $Dm_n=\lfloor\frac{3^n}{10^m}\rfloor\bmod{10}$ denote the $m$th digit of $3^n$.

Let $P(m)=4\cdot5^m$ denote the period of the sequence $Dm$.

Note that I am using $m$ as a $0$-based index in the above notations.

The following congruences hold for every exponent in your sequence:

  • $3^{3}\equiv3^{3^{3}}\equiv3^{3^{3^{3}}}\equiv\ldots\equiv 3\pmod{ 4}$
  • $3^{3}\equiv3^{3^{3}}\equiv3^{3^{3^{3}}}\equiv\ldots\equiv 7\pmod{ 20}$
  • $3^{3}\equiv3^{3^{3}}\equiv3^{3^{3^{3}}}\equiv\ldots\equiv 87\pmod{100}$
  • $3^{3}\equiv3^{3^{3}}\equiv3^{3^{3^{3}}}\equiv\ldots\equiv387\pmod{500}$
  • $\ldots$

And in general, $\forall{m}\exists{k}:3^{3}\equiv3^{3^{3}}\equiv3^{3^{3^{3}}}\equiv\ldots\equiv{k}\pmod{P(m)}$.

$\endgroup$

Your Answer

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