# 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.

• Start by proving $a^m \equiv 1 \bmod 2^n \implies a^{2m} \equiv 1 \bmod 2^{n+1}$.
– lhf
Commented Jun 9, 2021 at 11:00
• 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})^*$ ? Commented Jun 9, 2021 at 11:24
• You can start by considering the multiplicative group formed by elements that are relatively prime to $2^n$ Commented Jun 9, 2021 at 12:03
• (btw ($\mathbb{Z}$/$2^n\mathbb{Z}$)* does not form a group under multiplication) Commented Jun 9, 2021 at 12:09
• Oh I'm sorry, I tend to write $*$ instead of $\times$ but I meant the invertible elements from the beginning Commented Jun 9, 2021 at 12:35

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.