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.

  • 1
    $\begingroup$ Start by proving $a^m \equiv 1 \bmod 2^n \implies a^{2m} \equiv 1 \bmod 2^{n+1}$. $\endgroup$
    – lhf
    Commented Jun 9, 2021 at 11:00
  • $\begingroup$ Okay, then we know that the order of $a$ divides $2m$ in $(\mathbb{Z}/2^{n+1}\mathbb{Z})^*$, but how are we sure that the order in $(\mathbb{Z}/2^n\mathbb{Z})^*$ is not equal to the order in $(\mathbb{Z}/2^{n+1}\mathbb{Z})^*$ ? $\endgroup$
    – rerouille
    Commented Jun 9, 2021 at 11:24
  • $\begingroup$ You can start by considering the multiplicative group formed by elements that are relatively prime to $2^n$ $\endgroup$
    – Lucius
    Commented Jun 9, 2021 at 12:03
  • $\begingroup$ (btw ($\mathbb{Z}$/$2^n\mathbb{Z}$)* does not form a group under multiplication) $\endgroup$
    – Lucius
    Commented Jun 9, 2021 at 12:09
  • $\begingroup$ Oh I'm sorry, I tend to write $*$ instead of $\times$ but I meant the invertible elements from the beginning $\endgroup$
    – rerouille
    Commented Jun 9, 2021 at 12:35

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .