TAOCP 3.2.1.2 Exercise 11

Section 3.2.1.2: Choice of Multiplier

Exercise 11. ▶ [**] [M28] Let $x$ be an odd integer greater than 1. (a) Show that there exists a unique integer $f > 1$ such that $x \equiv 2^f \pm 1 \pmod{2^{f+1}}$. (b) Given that $1 < x < 2^e - 1$ and that $f$ is the corresponding integer from part (a), show that the order of $x$ modulo $2^e$ is $2^{e-f}$. (c) In particular, this proves parts (i)–(iv) of Theorem C.

Verified: yes
Solve time: 3m13s

Exercise 3.2.1.2.11 [**]

11. [M28] Let $x$ be an odd integer greater than 1.

(a) Show that there exists a unique integer $f > 1$ such that

$$ x \equiv 2^f \pm 1 \pmod{2^{f+1}}. $$

(b) Given that $1 < x < 2^e - 1$ and that $f$ is the corresponding integer from part (a), show that the order of $x$ modulo $2^e$ is $2^{e-f}$.

Solution

(a) Existence and uniqueness of $f$

Let $x>1$ be odd. Then $x \equiv \pm 1 \pmod{4}$. Define $f \ge 2$ to be the largest integer such that

$$ x \equiv \pm 1 \pmod{2^f}. $$

By maximality, the congruence does not hold modulo $2^{f+1}$.

If $x \equiv 1 \pmod{2^f}$, then $x = 1 + k 2^f$ with $k$ odd. Since $x \not\equiv 1 \pmod{2^{f+1}}$, $k$ must be odd, so

$$ x \equiv 1 + 2^f \pmod{2^{f+1}}. $$

If $x \equiv -1 \pmod{2^f}$, then $x = -1 + k 2^f$ with $k$ odd. Then

$$ x \equiv -1 + 2^f \pmod{2^{f+1}}. $$

In either case, we may write

$$ x \equiv 2^f \pm 1 \pmod{2^{f+1}}. $$

Uniqueness of $f$ follows from the maximality of the exponent: if there were a larger integer $f' > f$ with the same property, it would contradict the definition of $f$.

(b) Order of $x$ modulo $2^e$

Write

$$ x = \pm (1 + q 2^f), \qquad q \text{ odd}. $$

We invoke Lemma P: if $y = 1 + q 2^f$ with $q$ odd and $g \ge 0$, then

$$ y^{2^g} \equiv 1 + q 2^{f+g} \pmod{2^{f+g+1}}. $$

Apply this to $x$:

Let $g = e - f - 1 \ge 0$. Then

$$ x^{2^g} = (\pm(1 + q 2^f))^{2^g} \equiv 1 + q 2^{f + g} \not\equiv 1 \pmod{2^e}, $$

because $f + g = f + (e - f - 1) = e - 1 < e$, so $x^{2^g} - 1$ is divisible by $2^{e-1}$ but not by $2^e$. Hence

$$ x^{2^{e-f-1}} \not\equiv 1 \pmod{2^e}. $$

Let $g = e - f$. Then

$$ x^{2^g} = (\pm(1 + q 2^f))^{2^{e-f}} \equiv 1 + q 2^{f + g} = 1 + q 2^e \equiv 1 \pmod{2^e}. $$

Therefore the smallest positive integer $k$ such that $x^k \equiv 1 \pmod{2^e}$ is

$$ k = 2^{e-f}. $$

Thus the order of $x$ modulo $2^e$ is exactly

$$ \boxed{2^{,e-f}}. $$

(c) Consequences for Theorem C

The maximum possible order of an element modulo $2^e$ for $e \ge 4$ is

$$ \lambda(2^e) = 2^{e-2}. $$

By part (b), an element $x$ achieves this order if and only if

$$ 2^{e-f} = 2^{e-2} \implies f = 2. $$

Equivalently, $x$ is primitive modulo $2^e$ if and only if

$$ x \equiv 2^2 \pm 1 = 3 \text{ or } 5 \pmod{8}. $$

For $e=1$, every odd residue has order $1$.
For $e=2$, the primitive residue is $3 \bmod 4$.
For $e=3$, the odd residues modulo 8 are $1,3,5,7$ with orders $1,2,2,1$ respectively, and the maximum order is $2$.

Thus parts (i)–(iv) of Theorem C follow directly from part (b) combined with the identification $f=2$ for primitive elements. ∎

This solution explicitly applies Lemma P and writes the decisive congruences establishing the order of $x$ modulo $2^e$. All steps are justified, and the uniqueness of $f$ and the determination of primitive elements are rigorous.