Proof $\operatorname{ord}_{2^n}(3)=2^{n-2}$

Question

Trying some values it looks to me it should be true that, for $n$ an integer such that $n\geq 3$:$$\operatorname{ord}_{2^n}(3)=2^{n-2}$$ Is it true? If so how can I prove it? I know that $$3^{2^{n-1}}\equiv 1 \mod 2^n$$by Euler's totient theorem and that the multiplicative order should be a power of two less than or equal to $2^{n-1}$, but how to check it is precisely $2^{n-2}$? Also, is there a general method or some general/noticeable tricks in finding multiplicative orders? Thanks

Answer 1

You could prove by induction that $3^{2^{n-2}}\equiv1\bmod2^n$ for $n\ge 3$.

Base case: for $n=3$, $3^2\equiv1\bmod2^3$.

Now if $2^{n}$ divides $3^{2^{n-2}}-1$, then, since $2$ divides $3^{2^{n-2}}+1$,

$2^{n+1}$ divides $(3^{2^{n-2}}-1)(3^{2^{n-2}}+1)=3^{2^{n-1}}-1.$

But $\gcd(3^{2^{n-2}}-1,3^{2^{n-2}}+1)=2$, so we can't have $2^{n+1}$ dividing $3^{2^{n-2}}-1$.

Answer 2

The order should divide $2^{n-1},$ so lets see what happens for a general $k.$ We would like to see what is the condition for $k$ to be such that $$3^{2^{k}}\equiv 1\pmod {2^n}.$$ Notice that $3=2+1$ and so we have $$3^{2^k}=\sum _{i=0}^{2^k}2^i\binom{2^k}{i}=1+2^{k+1}+2^{k+1}+\cdots + 2^{2^k}$$ Recall that $\nu_2(n!)=n-S_2(n)$ where $\nu _2$ tells us the biggest power of two dividing the argument and $S_2$ gives us the sum of the digits in base $2$ of the argument and so notice that $$\nu _2 \left (\binom{2^k}{i}\right )=2^k-S_2(2^k)-(i-S_2(i)+2^k-i-S_2(2^k-i))=S_2(2^k-i)+S_2(i)-1\leq k$$ and so $$\nu _2(2^i\binom{2^k}{i})\leq i+k.$$

(to be precise, is a good exercise to show that $\nu _2 \left (\binom{2^k}{i}\right )=k-\nu _2(i)$). Notice also that the inequality is equality precisely if $i$ is odd and so $k+1$ is the minimum for odds and for evens the minimum is in $2$ so we can factor out a $2^{k+2}$ to end up with $$3^{2^k}=1+2^{k+2}(1+\text{even})$$ and so the only way for $2^n$ to divide this is if $k\geq n-2.$

Answer 3

If $n>3$, then $2^{n-3}$ is even, so $3^{2^{n-3}}\equiv(4-1)^{2^{n-3}}\equiv1-4\cdot2^{n-3}\equiv1+2^{n-1}\not\equiv1\bmod 2^n$,

but $3^{2^{n-2}}\equiv(4-1)^{2^{n-2}}\equiv1-4\cdot2^{n-2}\equiv1\bmod 2^n$, so ord$_{2^n}(3)=2^{n-2}$.

This also holds for $n=3$, because $3^{2^1}=9\equiv1\bmod2^3=8$, but $3^{2^0}=3\not\equiv1\bmod8$.

A similar argument would show ord$_{2^n}(5)=2^{n-2}$.