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

Question

It is linked to my previous question, I haven't been given any clue for how to verify this modular equation:

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

How can I find the condition for $n$?

Answer 1

Looking back at your original post, you have presented the equivalence as you remember it. Perhaps the statement in the original was $((2^3)^4)^{...n}\equiv 1 \mod{n+1}$. In that case, the problem has a straightforward solution. The exponentiated number is representable as $(2^k)^n$. Plainly, the only prime factor of this number is $2$. If $n+1$ is prime $p$ other than $2$, then we have $(2^k)^{p-1}\equiv 1 \mod{p}$, which is always true by Fermat's Little Theorem. So one condition which makes the (revised) equivalence true is that $n=p-1$ for all prime $p\neq 2$. Other values of $n$ (such as Carmichael numbers minus $1$) may also work.

Answer 2

$2^d \equiv 1 \mod (n+1)$ iff $n$ is even and $d$ is divisible by the multiplicative order of $2$ mod $(n+1)$. So for the condition to be true, you need the multiplicative order of $2$ mod $(n+1)$ to be a power of $3$. The first few $n$ for which this is the case are $6, 72, 486, 510, 2592, 3408, 18150, 35550, 39366, 71118, 80190, 97686$.