2
$\begingroup$

I can show that $3^{3^{3^n}}\equiv7\pmod{10}$ since

$3^1\equiv3\pmod{10}$

$3^2\equiv9\pmod{10}$

$3^3\equiv7\pmod{10}$

$3^4\equiv1\pmod{10}$

Thus, it reduces to $3^{(3^{3^n}\mod4)}$. I can then notice that

$3^1\equiv3\pmod4$

$3^2\equiv1\pmod4$

Reducing it down to $3^{(3^{(3^n\mod2)}\mod4)}=3^{(3^1\mod4)}=3^3\equiv7\pmod{10}$

However, this is tedious and not capable of solving the following problem:

$$3^{3^{3^{\dots}}}\pmod{100}$$

where the power tower keeps going up until the value becomes fixed for all further power towers. How would I take this problem?

To clarify a bit, we take the exponents at the top and work our way down. For example,

$$3^{3^3}=3^{27}\ne(3^3)^3$$

For clearer notation, $3^{3^{3^{\dots}}}=3\uparrow(3\uparrow(3\uparrow(\dots(3\uparrow n)\dots)))$, and we take as many $\uparrow$'s required such that for all $n,k\in\mathbb N$ we have

$$3\uparrow(3\uparrow(3\uparrow(\dots(3\uparrow n)\dots)))\equiv3\uparrow(3\uparrow(3\uparrow(\dots(3\uparrow k)\dots)))\pmod{100}$$

In Knuth's up arrow notation.

$\endgroup$
  • $\begingroup$ If I may, I'd like to do this by hand. $\endgroup$ – Simply Beautiful Art Dec 30 '16 at 18:57
  • 3
    $\begingroup$ What means $3^{3^{3\cdots}}$? It is a sequence, a number? The points means "infinite power"? $\endgroup$ – Masacroso Dec 30 '16 at 18:59
  • $\begingroup$ @Masacroso It means 3^(3^(3^...3^n...)), and it goes up as high such that for all $n,k$, 3^(3^(3^...3^n...))$\equiv$ 3^(3^(3^...3^k...))$\pmod{100}$. $\endgroup$ – Simply Beautiful Art Dec 30 '16 at 19:01
8
$\begingroup$

We know that $$3^2 \equiv 1 \pmod{4} \\ 3^{20} \equiv 1 \pmod{25}$$ with the last following from Euler Theorem. Therefore $$3^{20} \equiv 1 \pmod{100}$$

The problem then reduces to finding the powers of $3 \pmod{20}$.

Again $$3^2 \equiv 1 \pmod{4} \\ 3^4 \equiv 1 \pmod{5} \\$$

Therefore $3^4 \equiv 1 \pmod{20}$.

We thus have $$3^{3^{3 ^{...}}} \equiv 3^{3^{3 ^{...}} \pmod{20}} \equiv 3^{3^{3 ^{...} \pmod{4}}} \pmod{100} \equiv 3^{3^{3 }} \pmod{100}\\ \equiv 3^{27}\equiv 3^{7} \pmod{100}$$ which is easy to calculate.

$\endgroup$
  • $\begingroup$ Ah, perfecto! Thank you much. $\endgroup$ – Simply Beautiful Art Dec 30 '16 at 19:07
1
$\begingroup$

As $3\equiv-1\pmod4,3^{2n+1}\equiv-1\equiv3$ for any integer $n\ge0$

So, $3^{3^{3^{\cdots}}}$ can be written as $\displaystyle3^{4k+3}$ or $\displaystyle3^{3^{(4b+3)}}$

Now,$\displaystyle3^{4k+3}=27(10-1)^{2k}=27(1-10)^{2k}$

and $\displaystyle(1-10)^{2k}\equiv1-\binom{2k}110\pmod{10^2}\equiv1-20k$

So, it is sufficient to find $4k+3=3^{(4b+3)}\pmod5$

$\displaystyle4k+3=3^{(4b+3)}=3^3(3^4)^b\equiv2\cdot1^b\pmod5\equiv2$

$\displaystyle\implies4k\equiv-1\pmod5\equiv4\implies k\equiv1$ as $(4,5)=1$

$\displaystyle\implies(1-10)^{2k}\equiv1-20\cdot1\equiv81\pmod{100}$

$\displaystyle\implies3^{3^{(4b+3)}}\equiv27\cdot81\pmod{100}\equiv?$

$\endgroup$
  • $\begingroup$ :D simply elementary. $\endgroup$ – Simply Beautiful Art Jan 14 '17 at 12:49
  • 1
    $\begingroup$ @SimpleArt, Thanks for your feedback. Was trying to generalize the problem! $\endgroup$ – lab bhattacharjee Jan 14 '17 at 14:57

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.