LemmaStatement: AI-adaptedProof: AI-generatedPipeline-generated

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.

Half an even order gives a square root of one

Statement

Let $N \geq 2$ , let $x$ be a unit modulo $N$ , and let $q \geq 2$ be an even integer with $x^{q} \equiv 1 (m o d N)$ . Then $z = x^{q / 2} m o d N$ satisfies $z^{2} \equiv 1 (m o d N)$ . If $q = {ord}_{N} (x)$ , then additionally $z \equiv̸ 1 (m o d N)$ .

Facts & Assumptions

Given: $N \geq 2$ , an integer $x$ with $[x]_{N} \in (Z / N)^{\times}$ , an even integer $q \geq 2$ with $x^{q} \equiv 1 (m o d N)$ , and $z = [x^{q / 2}]_{N}$ . Here ${ord}_{N} (x)$ means the order of $[x]_{N}$ in the unit group.

[F1]

Multiplication makes $(Z / N)^{\times}$ a group, and congruence classes multiply by multiplying representatives (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ , The congruence class $[a]_{n}$ and the quotient set $Z / n$ , For every natural $n$ , $(Z / n, +)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold).

[F2]

For an element of finite order $r$ , $x^{t} = 1$ exactly when $r ∣ t$ (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, 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$ ).

Proof

1.1givenF1algebra

Write $q = 2 h$ with $h = q / 2 \geq 1$ . Then $z^{2} = [x^{h}]_{N} [x^{h}]_{N} = [x^{2 h}]_{N} = [x^{q}]_{N} = [1]_{N}$ , so $z$ is a square root of one.

2.1givenF1F2step 1.1algebra

If $q = {ord}_{N} (x)$ and $z = [1]_{N}$ , then $[x]_{N}^{h} = [1]_{N}$ in the unit group. By [F2], $q ∣ h$ , which is impossible because $0 < h < q$ . Thus $z \neq [1]_{N}$ .

3.1step 1.1step 2.1∎

The square relation holds for every accepted even exponent, and step 2.1 supplies the additional nonidentity conclusion when it is the true order.

Depends on

Used by

Classical randomized order-to-factor success bound Theorem
Order-to-factor output correctness Theorem

Dependency tree · two levels

42 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)