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.

Mixed CRT signs yield proper gcd factors

Statement

Let $N = \prod_{i < k} p_{i}^{e_{i}}$ , where $k \geq 1$ , the $p_{i}$ are distinct odd primes, and every $e_{i} \geq 1$ . If $z^{2} \equiv 1 (m o d N)$ but $z \equiv̸ 1, - 1 (m o d N)$ , then both $\gcd (z - 1, N)$ and $\gcd (z + 1, N)$ are proper nontrivial divisors of $N$ . When $k = 1$ , the hypotheses cannot hold, because the proof below shows the only roots are the two global signs.

Facts & Assumptions

Given: The stated factorization of odd $N$ , an integer $z$ with $z^{2} \equiv 1 (m o d N)$ , and $z \equiv̸ \pm 1 (m o d N)$ .

[F1]

The Chinese remainder map is a bijection preserving multiplication, and it restricts to the product isomorphism of the corresponding unit groups for pairwise-coprime moduli (Chinese remainder theorem for a finite pairwise-coprime list: simultaneous residues determine one class modulo the product, and the resulting bijection preserves addition and multiplication, For pairwise coprime positive moduli, the Chinese remainder bijection restricts to an isomorphism of unit groups).

[F2]

For odd prime $p$ and $e \geq 1$ , $(Z / p^{e})^{\times}$ is cyclic of even order $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)$ ).

[F3]

For a generator $g$ of a cyclic group of order $M$ , $g^{t} = 1$ exactly when $M ∣ t$ (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$ ).

[F4]

For a nonzero pair, gcd is a common divisor and is greatest in the usual order (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ); divisibility is transitive (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[F5]

Every odd prime is at least $3$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ , The integers form a totally ordered ring). If $d ∣ a$ and $a \neq 0$ , then $d \leq ∣ a ∣$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ).

[F6]

Congruence classes multiply by multiplying representatives, and equal classes are equivalent to congruence (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).

Proof

1.1givenF1F2F3F5F6choosealgebra

By [F1], $z$ has components $z_{i} = [z]_{p_{i}^{e_{i}}}$ . Each satisfies $z_{i}^{2} = 1$ , hence is a unit. Choose a generator $g_{i}$ of its cyclic unit group of even order $M_{i}$ by [F2], and write $z_{i} = g_{i}^{t_{i}}$ . By [F3], $z_{i}^{2} = 1$ exactly when $M_{i} ∣ 2 t_{i}$ . Among residues $t_{i}$ modulo even $M_{i}$ , this gives only $t_{i} = 0$ or $t_{i} = M_{i} / 2$ , so $z_{i}$ is one of the two roots $1, - 1$ : the second is $- 1$ because $- 1$ is a root and it is distinct from $1$ modulo $p_{i}^{e_{i}} > 2$ (otherwise $p_{i}^{e_{i}} ∣ 2$ , contrary to [F5]). To see the two exponent classes explicitly, write $M_{i} = 2 s_{i}$ ; $M_{i} ∣ 2 t_{i}$ is equivalent to $s_{i} ∣ t_{i}$ , which has the two residue classes $0, s_{i}$ modulo $2 s_{i}$ .

2.1givenstep 1.1F1choose

The signs cannot all be $+ 1$ , since CRT injectivity would then give $z \equiv 1 (m o d N)$ , and they cannot all be $- 1$ , since it would give $z \equiv - 1 (m o d N)$ . Choose indices $i_{+}$ and $i_{-}$ with signs $+ 1$ and $- 1$ , respectively. This also shows that when $k = 1$ the hypotheses are impossible.

3.1givenstep 2.1F4F5F6algebra

Since $p_{i_{+}}^{e_{i_{+}}} ∣ z - 1$ and $p_{i_{+}}^{e_{i_{+}}} ∣ N$ , it is a common divisor, so $\gcd (z - 1, N) \geq p_{i_{+}}^{e_{i_{+}}} > 1$ . Since $z \equiv - 1 (m o d p_{i_{-}}^{e_{i_{-}}})$ , that prime power divides $z + 1$ ; it cannot divide $z - 1$ because then it would divide $2 = (z + 1) - (z - 1)$ , whereas $p_{i_{-}}^{e_{i_{-}}} > 2$ . Thus $N ∤ z - 1$ and $\gcd (z - 1, N) < N$ .

4.1step 3.1step 2.1F4∎

Interchanging the two signs in step 3.1 gives $1 < \gcd (z + 1, N) < N$ . Hence both gcds are proper nontrivial divisors.

Depends on

Used by

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

Dependency tree · two levels

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