<s>[INST] Show that order of $2^m t-1$ is same as of order of $2^m t+1$ modulo $2^n$ where $n\geqslant 3$. Given that $n\geqslant 3$ and $n\geqslant m\geqslant 2$. Assume that, for some $t$ within the range $\{0,1,2,\ldots, 2^{n-m}-1\}$, the following holds,
\begin{align*}
&(2^m t+1)^{2^{n-m}}\equiv 1[2^n]\\
&(2^m t+1)^{2^{k}}\not\equiv 1[2^n]
\end{align*}
for any $1\leqslant k\leqslant n-m-1$. How to show that the same is true if we replace $2^m t+1$ with $2^mt-1$ ?
Tried to check through particular value, but general reasoning isn't getting. Any help please ?
 [/INST] Recall that $5$ has order $2^{n-2}$ modulo $2^n$, that's we have $5^x\equiv 1\pmod{2^n}$ if and only if $x\equiv 0\pmod{2^{n-2}}$.
Let $t\in\Bbb Z$, $h$ such that $2^h\mid t$ and $2^{h+1}\nmid t$ and $a=1+2^mt$.
Then $a\equiv 1\pmod{2^{m+h}}$, hence $a\equiv 5^u\pmod{2^n}$ with $u\equiv 0\pmod{2^{m+h-2}}$.
Since, modulo $2^{n}$, $5$ has order $2^{n-2}$, $5^u$ has order $2^{n-2}/2^{m+h-2}=2^{n-m-h}$.
This proves that $a$ has order $2^{n-m}$ if and only if $h=0$, that's $2\nmid t$.
Consequently, if $(1+2^mt)^{2^k}\not\equiv 1\pmod{2^n}$ for every $0\lt k\lt n-m$ and $(1+2^mt)^{2^{n-m}}\equiv 1\pmod{2^n}$, then $2\nmid t$, hence $2\nmid -t$ and this implies $(1-2^mt)^{2^k}\not\equiv 1\pmod{2^n}$ for every $0\lt k\lt n-m$ and $(1-2^mt)^{2^{n-m}}\equiv 1\pmod{2^n}$ and thus $(2^mt-1)^{2^k}\not\equiv 1\pmod{2^n}$ for every $0\lt k\lt n-m$ and $(2^mt-1)^{2^{n-m}}\equiv 1\pmod{2^n}$.
</s>