2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you justify your first sentence? $2^{3^4}=2^{(3^4)}\neq (2^3)^4$ $\endgroup$ – Mike Earnest Aug 31 '18 at 18:36
  • $\begingroup$ @Mike Earnest You are absolutely correct. I read the problem as I have indicated in my edited answer, which was an error on my part. I imagine that the equivalence that alienflow remembers is as I have presented it in my revisions, or else the problem is beyond the simple statement as he remembers it. $\endgroup$ – Keith Backman Aug 31 '18 at 18:53

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.