# Is 2 always a primitive root of 3ˣ?

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

• Your "that is..." doesn't guarantee that $2$ is a primitive root, it just guarantees that it isn't a quadratic residue. – Omnomnomnom Sep 28 '16 at 9:55
• Can you determine the order of $2$ modulo $3^{x+1}$ from $2^2 = 1 + 3$? – 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

$$2^{3^{n+1}}=3^{n+2}(3^{2n+1}M_n^3-3^{n+1}M_n^2+M_n)-1\Rightarrow\color{red}{2^{3^{n+1}}\equiv-1\pmod{3^{n+2}}}$$

• It remains the question of the primitive root. The answer is yes. – 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

• you should say $2^{2k} \equiv 1 \bmod 3, 2^{2k+1} \equiv 2 \bmod 3 \implies$ at the 5th line – reuns Sep 28 '16 at 13:00
• 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. :-) – user90369 Sep 28 '16 at 13:05