LemmaStatement: AI-adaptedProof: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Two-adic order distribution in odd prime-power unit groups

Statement

Let $p$ be an odd prime and $e \geq 1$ . If $A$ is uniform in $(Z / p^{e})^{\times}$ , then for every possible integer $j$ ,

$P (v_{2} ({ord}_{p^{e}} (A)) = j) \leq \frac{1}{2} .$

Here $v_{2} (r)$ is the greatest $s \in N$ such that $2^{s} ∣ r$ , for the positive integer order $r$ .

Facts & Assumptions

Given: An odd prime $p$ , an integer $e \geq 1$ , and the uniform finite probability law on $(Z / p^{e})^{\times}$ .

[F1]

The unit group is cyclic of order $M = p^{e - 1} (p - 1)$ (For every odd prime $p$ and $k \geq 1$ , $(Z / p^{k} Z)^{\times}$ is cyclic of order $p^{k - 1} (p - 1)$ , The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[F2]

For a finite-order group element, its powers equal the identity exactly at multiples of its order (The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity, Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ , If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[F3]

For a positive integer $r$ , $v_{2} (r)$ is the greatest $s$ with $2^{s} ∣ r$ (The $p$ -adic valuation $v_{p} (a)$ of a nonzero integer: the greatest $k \in N$ with $p^{k} ∣ a$ , with prime $2$ ).

[F4]

A finite uniform probability space assigns each outcome equal weight (Finite probability spaces, outcome weights, events, and event probabilities).

[F5]

The gcd is a greatest common divisor in the divisibility order and $\gcd (M, 0) = M$ for $M > 0$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , $\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$ ); Bézout's identity characterizes coprimality, and if $c, d$ are coprime and $c ∣ d x$ , then $c ∣ x$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ , Coprime integers: $\gcd (a, b) = 1$ , $a$ and $b$ are coprime if and only if $a x + b y = 1$ for some integers $x, y$ ; and in that case the only common divisors of $a$ and $b$ are $1$ and $- 1$ , If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ , Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution).

[F6]

Integer multiplication is associative and cancellation by a nonzero factor is valid (The integers form a commutative ring, The integers have no zero divisors; multiplicative cancellation).

Proof

1.1givenF1F2choose

Since $p$ is odd, $M = p^{e - 1} (p - 1)$ is even; write $M = 2^{s} u$ with $s \geq 1$ and $u$ odd. Choose a generator $g$ by [F1]. The map $t \mapsto g^{t}$ for $0 \leq t < M$ is a bijection onto the unit group, by the order statement in [F2], so a uniform unit corresponds to a uniform such exponent $t$ .

1.2givenF2F5F6algebra

Put $d = \gcd (M, t)$ . For $t > 0$ , write $M = d M_{0}$ and $t = d t_{0}$ . Bézout's identity for $M, t$ divides through by $d$ to give $M_{0} x + t_{0} y = 1$ , so $M_{0}, t_{0}$ are coprime by [F5]. For every $h \geq 1$ , [F2] gives $(g^{t})^{h} = 1$ exactly when $M ∣ t h$ , equivalently $M_{0} ∣ t_{0} h$ ; [F5] makes this equivalent to $M_{0} ∣ h$ . Hence the least such $h$ is $M_{0} = M / d$ . If $t = 0$ , then $d = M$ and $g^{t} = 1$ has order $1 = M / d$ .

2.1step 1.1step 1.2F3F4F5algebra

The exponent of $2$ in $d = \gcd (M, t)$ is $s$ exactly when $2^{s} ∣ t$ : if $2^{s} ∣ t$ , then $2^{s}$ is a common divisor and hence divides $d$ ; if $2^{s}$ divides $d$ , it divides $t$ . Since $2^{s}$ is the full power of $2$ dividing $M$ , this is equivalent to $v_{2} (M / d) = 0$ . There are $M / 2^{s} = u$ such residues among $0, \dots, M - 1$ , so this probability is $u / M = 2^{- s} \leq 1 / 2$ .

3.1step 1.1step 1.2F3F4F5algebra

For $1 \leq j \leq s$ , $v_{2} (M / d) = j$ exactly when the exponent of $2$ in $d$ is $s - j$ . As in step 2.1, this is exactly when $2^{s - j} ∣ t$ and $2^{s - j + 1} ∤ t$ . The number of such residues is $\frac{M}{2^{s - j}} - \frac{M}{2^{s - j + 1}} = 2^{j - 1} u,$ so their probability is $2^{j - 1} u / M = 2^{j - s - 1} \leq 1 / 2$ . No other valuation occurs because $M / d$ divides $M$ .

4.1step 2.1step 3.1∎

The cases $j = 0$ and $1 \leq j \leq s$ exhaust all possible valuations, and each has probability at most $1 / 2$ by steps 2.1 and 3.1.

Depends on

Used by

Classical randomized order-to-factor success bound Theorem

Dependency tree · two levels

75 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes (standard reference, not scraped)