That is, is it always that $$2^{3^x}\equiv -1\pmod{3^{x+1}}\large?$$

  • 3
    $\begingroup$ Your "that is..." doesn't guarantee that $2$ is a primitive root, it just guarantees that it isn't a quadratic residue. $\endgroup$ – Omnomnomnom Sep 28 '16 at 9:55
  • $\begingroup$ Can you determine the order of $2$ modulo $3^{x+1}$ from $2^2 = 1 + 3$? $\endgroup$ – Daniel Fischer Sep 28 '16 at 10:23

Another way to solve this question is by induction.

►The statement holds for $n=1$ because $2^3=8=9-1\equiv -1\pmod {3^2}$.

►Suppose it is true for $n$, that is $2^{3^n}\equiv-1\pmod{3^{n+1}}$.

►Proof it is true for $n+1$. $$2^{3^n}\equiv-1\pmod{3^{n+1}}\iff2^{3^n}=3^{n+1}M_n-1$$ It follows $$2^{3^{n+1}}=(2^{3^n})^3=(3^{n+1}M_n-1)^3=3^{3n+3}M_n^3-3\cdot3^{2n+2}M_n^2+3\cdot3^{n+1}M_n-1$$ Hence


  • $\begingroup$ It remains the question of the primitive root. The answer is yes. $\endgroup$ – Piquito Sep 29 '16 at 13:23

Euler function: $\varphi$

$\varphi(3^{x+1})=2\cdot 3^x\enspace$ => $\enspace 2^{2\cdot 3^x}\equiv 1 \mod 3^{x+1}\enspace$ (Euler-Fermat)

It follows $\,2^{3^x}\equiv \pm 1 \mod 3^{x+1}$ .

This means $(2^{3^x}-1)(2^{3^x}+1)\equiv 0\mod 3^{x+1}$ .

$2^{3^x}-1=(3-1)^{3^x}-1\equiv -2 \mod 3$

(If this is not clear please have a look to the comment of User user1952009 below.)

It follows that $2^{3^x}-1$ can never devided by $3$.

$=> \enspace$ $2^{3^x}+1\equiv 0\mod 3^{x+1}\enspace$ which has to be proofed

  • $\begingroup$ you should say $2^{2k} \equiv 1 \bmod 3, 2^{2k+1} \equiv 2 \bmod 3 \implies$ at the 5th line $\endgroup$ – reuns Sep 28 '16 at 13:00
  • $\begingroup$ I have assumed that the OP knows this (because of the level of this question) - but thanks, I will give a hint to your useful comment. :-) $\endgroup$ – user90369 Sep 28 '16 at 13:05

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.