Relation between orders of an integer modulo $2^n$ and $2^{n+1}$ How can you prove that for $a$ odd $ \in \lbrack 3; 2^n-3 \rbrack $, ( so $a$ is in $(\mathbb{Z}/2^n\mathbb{Z})^{\times}$ and $a\neq \pm 1$), the order of $a$ in $(\mathbb{Z}/2^{n+1}\mathbb{Z})^{\times}$ is twice the order of $a$ in $(\mathbb{Z}/2^n\mathbb{Z})^{\times}$ ?
This seems true all the time, but I can't find any topic on this.
 A: Suppose $n$ is a positive integer, and $a$ is an odd positive integer such that $1 < a < 2^n-1$.

This implies $n\ge 3$.

Let $s$ be the order of $a$, mod $2^n$, and let $t$ be the order of $a$, mod $2^{n+1}$.

We want to show that $t=2s$.

We have
\begin{align*}
&
a^t\equiv 1\;(\text{mod}\;2^{n+1})
\;\;\;\;\;\;
&&\bigl(\text{since $t$ is the order of $a$, mod $2^{n+1}$}\bigr)
\\[4pt]
\implies\;&
a^t\equiv 1\;(\text{mod}\;2^n)
\\[4pt]
\implies\;&
s{\,\mid\,}t
&&\bigl(\text{since $s$ is the order of $a$, mod $2^n$}\bigr)
\\[4pt]
\end{align*}
and also
\begin{align*}
&
2^n{\,\mid\,}a^s-1
&&\bigl(\text{since $s$ is the order of $a$, mod $2^n$}\bigr)
\\[4pt]
\implies\;&
2^{n+1}{\,\mid\,}(a^s+1)(a^s-1)
&&\bigl(\text{since $a^s+1$ is even}\bigr)
\\[4pt]
\implies\;&
2^{n+1}{\,\mid\,}a^{2s}-1
\\[4pt]
\implies\;&
t{\,\mid\,}2s
&&\bigl(\text{since $t$ is the order of $a$, mod $2^{n+1}$}\bigr)
\\[4pt]
\end{align*}
From $s{\,\mid\,}t$ and $t{\,\mid\,}2s$, it follows that $t=s$ or $t=2s$.

Suppose that $t=s$.

Our goal is to derive a contradiction.

From $1 < a <2^n-1$ we get $s > 1$.

Since $s$ is the order of $a$, mod $2^n$, it follows that $s{\,\mid\,}\phi(2^n)$.

Then since $\phi(2^n)=2^{n-1}$ and $s > 1$, it follows that $s$ is even, so $s=2r$ for some positive integer $r$.

Both $a^r+1$ and $a^r-1$ are even, but only one of them, call it $b$, is a multiple of $4$.

Let $k$ be such that $2^k{\,||\,}b$.

From $2^k{\,||\,}b$, it follows that $2^{k+1}{\,||\,}(a^r+1)(a^r-1)$, so $2^{k+1}{\,||\,}a^s-1$

From $t=s$, it follows that $2^{n+1}{\,\mid\,}a^s-1$, hence $k+1\ge n+1$, so $k\ge n$.

Thus $2^n{\,\mid\,}b$.

Consider two cases . . .

Case $(1)$:$\;b=a^r-1$.

Since $s$ is the order of $a$, mod $2^n$, and $r < s$, it follows that $2^n{\,\not\mid\,}a^r-1$, contrary to $2^n{\,\mid\,}b$.

Case $(2)$:$\;b=a^r+1$.

Since $2^n{\,\mid\,}b$, we get $2^n{\,\mid\,}a^r+1$.

In particular, $4{\,\mid\,}a^r+1$, hence since $a$ is odd, $r$ must be odd.

From $2r=s$ and $s{\,\mid\,}2^{n-1}$, we get $r{\,\mid\,}2^{n-1}$, hence since $r$ is odd, we get $r=1$.

But then $2^n{\,\mid\,}a^r+1$ becomes $2^n{\,\mid\,}a+1$, contrary to $1< a < 2^n-1$.

Thus in both cases, we have a contradiction.

Therefore $t=2s$, as was to be shown.
