0
$\begingroup$

I remember when I started learning modular arithmetics I found a tetration equation stated as follows

$2^{3^{4^{...^{n}}}} \equiv 1$ (mod $n+1$)

I am wondering how could this be proved, I tried this but I got lost:

$2^{3^{4^{5}}} $ (mod $6$) $ \equiv 2^{3^{4^{5}} mod 5}$(mod $6$)

How can I prove it?

$\endgroup$
  • 8
    $\begingroup$ You need to give a condition for $n$. When $n=3$, $2^3$ is not congruent to $1$ mod $3+1$ $\endgroup$ – TheSimpliFire Aug 30 '18 at 18:08
  • $\begingroup$ I hadn't been given any condition :0 $\endgroup$ – alienflow Aug 30 '18 at 19:51
  • $\begingroup$ Have you tried the power rule? Where this boils down to 2 ^ 3 * 4 *..n. Then you have 2 * 2 * 2... *2 which could probably be boiled down to 2(something n + 1) or the equivalent [needs more though] for which you can get 1(modn + 1). I don't have a lot of time right now but that would be how i go about it. $\endgroup$ – Andrew Scott Evans Mar 11 at 22:47
  • $\begingroup$ @AndrewScottEvans unparenthesized powers don't work that way. $\endgroup$ – Roddy MacPhee 2 days ago
  • $\begingroup$ $2^{3^4}\equiv 2\ne1\pmod5$ $\endgroup$ – Piquito yesterday
1
$\begingroup$

It likely rarely will work as stated in the comments. What we do in cases like this is repeated use of modular arithmetic rules, usually Euler's totient theorem or more useful rules.

basically each power going right to left gets a new modulus. ex.

$$a^{b^{c^{d^e}}}\equiv f \bmod 65536$$

We first mod the base a, by 65536 (see polynomial remainder theorem). We, then take$$b^{c^{d^e}}\equiv g \bmod (\phi(65536)=32768)$$ by taking b mod 32768. and then we take $${c^{d^e}}\equiv h \bmod (\phi(32768)=16384)$$ etc.

In your case, any time n is odd, n+1 will be even and then because $$y\equiv b \bmod m \implies y=mx+b$$ and the distributive law, we can factor out a 2 when we rearrange via subtraction on one side. but 1 doesn't have a 2 as a divisor. We therefore get, that only even n could ever make this congruence true.

$\endgroup$
  • $\begingroup$ I never said it would always work for odd n+1 , just those are the only ones it could work for. oh and you forgot to raise it to add 5 in the power chain. $\endgroup$ – Roddy MacPhee yesterday
  • $\begingroup$ Sorry, my comment was for the OP. $\endgroup$ – Piquito yesterday

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.