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.

✓ 9 results · all verified · 6 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 3 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Quadratic Reciprocity and the Jacobi Symbol — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (deepseek-v4-pro + claude-sonnet-5)audited 2026-08-17Open item page →

A complete reciprocity table for $3, 5, 7, 11$

Example

The nonzero square classes for the primes $3, 5, 7, 11$ are

$p$	nonzero squares modulo $p$
$3$	$1$
$5$	$1, 4$
$7$	$1, 2, 4$
$11$	$1, 3, 4, 5, 9$

Using the definition of the Legendre symbol (The Legendre symbol, including its zero value) gives the complete pair table

${p, q}$	$(p / q)$	$(q / p)$	relation
${3, 5}$	$- 1$	$- 1$	agree
${3, 7}$	$- 1$	$1$	opposite
${3, 11}$	$1$	$- 1$	opposite
${5, 7}$	$- 1$	$- 1$	agree
${5, 11}$	$1$	$1$	agree
${7, 11}$	$- 1$	$1$	opposite

The signs are opposite exactly when both primes are congruent to $3$ modulo $4$ , as predicted by quadratic reciprocity (Quadratic reciprocity for distinct odd primes).

Facts & Assumptions

Given: The primes $3, 5, 7, 11$ and the residue tables displayed in the Example.

[L1]

For distinct odd primes $p, q$ , $(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{(p - 1) (q - 1) / 4}$ (Quadratic reciprocity for distinct odd primes).

[L2]

For an odd prime $p$ , the Legendre symbol is $1$ on nonzero square classes, $- 1$ on nonzero nonsquare classes, and $0$ on the zero class (The Legendre symbol, including its zero value).

Verification

technique · direct

1.1L2givenalgebra

Squaring every residue class modulo each prime gives the displayed nonzero square sets. Reading the residues of each numerator from those sets by [L2] gives all entries in the pair table.

2.1step 1.1L1algebra∎

For the pairs ${3, 7}$ , ${3, 11}$ , and ${7, 11}$ both primes are $3$ modulo $4$ and the direct signs are opposite; in every other row at least one prime is $1$ modulo $4$ and the signs agree. Each row therefore has the product required by [L1].

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + claude-sonnet-5)audited 2026-08-17Open item page →

Computing $(1111 / 8093)$ by the Euclidean Jacobi algorithm

Example

The Euclidean Jacobi algorithm (The Euclidean algorithm computes the Jacobi symbol without factoring the denominator) evaluates

$(\frac{1111}{8093}) = - 1$

without factoring $8093$ . Its states $(ε, A, N)$ are

$(1, 1111, 8093), (1, 8093, 1111), (- 1, 1111, 79), (- 1, 79, 5), (- 1, 5, 1) .$

Facts & Assumptions

Given: The initial pair $(1111, 8093)$ with odd positive denominator.

[L1]

The Euclidean Jacobi algorithm terminates and returns $(\frac{a}{n})$ without factoring the odd denominator $n$ (The Euclidean algorithm computes the Jacobi symbol without factoring the denominator).

Verification

technique · direct

1.1L1givenalgebra

The divisions and sign updates are $8093 = 7 \cdot 1111 + 316$ , $316 = 2^{2} \cdot 79$ , $1111 = 14 \cdot 79 + 5$ , $79 = 15 \cdot 5 + 4$ , and $4 = 2^{2}$ . The first swap has no sign change, removing either square power of $2$ has no sign change, and the swap of $79$ and $1111$ changes the sign because both are $3$ modulo $4$ ; the next denominator is $1$ . After each complete update, these calculations give exactly the displayed state sequence.

2.1step 1.1L1∎

The terminal sign is $- 1$ , and [L1] identifies it with $(\frac{1111}{8093})$ . No factorisation of $8093$ occurs in step 1.1.

CounterexampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passaudited 2026-08-17Open item page →

Jacobi symbol one does not imply a square: $(2 / 15) = 1$

Statement refuted

The converse of A unit square modulo an odd integer has Jacobi symbol one is false: a unit $a$ with $(\frac{a}{n}) = 1$ need not be a square modulo the odd positive integer $n$ .

Facts & Assumptions

Given: The unit numerator $2$ and the odd denominator $15 = 3 \cdot 5$ .

[L1]

For odd $n \geq 1$ with canonical prime factorisation $n = \prod_{i < r} p_{i}^{e_{i}}$ , define $(\frac{a}{n}) : = \prod_{i < r} {(\frac{a}{p_{i}})}^{e_{i}}$ (The Jacobi symbol, with its zero value and empty-product convention).

Counterexample

technique · direct

1.1L1givenalgebra

The nonzero square classes modulo $3$ are ${1}$ and those modulo $5$ are ${1, 4}$ , so $(2 / 3) = - 1$ and $(2 / 5) = - 1$ . Using $15 = 3 \cdot 5$ in [L1] gives $(2 / 15) = (- 1) (- 1) = 1$ .

2.1step 1.1algebra∎

If $x^{2} \equiv 2 (m o d 15)$ , reduction modulo $3$ would give $x^{2} \equiv 2 (m o d 3)$ , but the complete square set modulo $3$ is ${0, 1}$ . Thus $2$ is not a square modulo $15$ , despite its Jacobi symbol being $1$ .

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (deepseek-v4-pro + claude-sonnet-5)audited 2026-08-17Open item page →

Lifting both square roots of $2$ from modulo $7$ to modulo $7^{4}$

Example

The two roots of $2$ lift along the powers of $7$ as follows:

modulus	first branch	second branch
$7$	$3$	$4$
$49$	$10$	$39$
$343$	$108$	$235$
$2401$	$2166$	$235$

Thus the square roots of $2$ modulo $7^{4} = 2401$ are the classes of $235$ and $2166$ .

Facts & Assumptions

Given: The target $a = 2$ , the odd prime $p = 7$ , and the two roots $3, 4$ modulo $7$ .

[L1]

A nonsingular root modulo $p^{k}$ has a unique lift of the form $x_{k} + t p^{k}$ modulo $p^{k + 1}$ , with $t$ uniquely determined modulo $p$ (A nonsingular square root lifts uniquely by one odd-prime-power step).

[L2]

A soluble unit square congruence modulo an odd prime power has exactly two solution classes (Unit square criterion and root count modulo odd prime powers).

Verification

technique · direct

1.1L1givenalgebra

Direct squaring gives the roots $3, 4$ modulo $7$ . Solving the correction congruence of [L1] on each branch gives corrections $(1, 5)$ modulo $7$ for the lift to $49$ , then $(2, 4)$ for the lift to $343$ , and finally $(6, 0)$ for the lift to $2401$ ; these yield the two displayed chains $3 \mapsto 10 \mapsto 108 \mapsto 2166$ and $4 \mapsto 39 \mapsto 235 \mapsto 235$ .

2.1step 1.1L2algebra∎

One has $235^{2} = 23 \cdot 2401 + 2$ and $2166^{2} = 1954 \cdot 2401 + 2$ , so both final classes are roots. They are distinct, and [L2] says a soluble unit congruence has exactly two roots, so the list is complete.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (deepseek-v4-pro + claude-sonnet-5)audited 2026-08-17Open item page →

The four square roots of $9$ modulo $128$

Example

The square roots of $9$ modulo $128$ are

$3, 61, 67, 125.$

Facts & Assumptions

Given: The unit target $9$ modulo $128 = 2^{7}$ .

[L1]

For $k \geq 3$ , an odd target is a square modulo $2^{k}$ exactly when it is $1$ modulo $8$ , and every soluble target has exactly four roots (Unit square criterion and root count modulo powers of two).

Verification

technique · direct

1.1givenalgebra

The representatives are distinct modulo $128$ , and $3^{2} = 9$ , $61^{2} = 29 \cdot 128 + 9$ , $67^{2} = 35 \cdot 128 + 9$ , and $125^{2} = 122 \cdot 128 + 9$ . Thus all four displayed classes are roots.

2.1step 1.1L1∎

Since $9 \equiv 1 (m o d 8)$ , [L1] says that the congruence is soluble and has exactly four root classes. The four distinct roots in step 1.1 are therefore complete.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-08-17Open item page →

The square roots of $1$ modulo $360$ by the Chinese remainder theorem

Example

The square roots of $1$ modulo $360$ are

$1, 19, 71, 89, 91, 109, 161, 179, 181, 199, 251, 269, 271, 289, 341, 359.$

Facts & Assumptions

Given: The factorisation $360 = 8 \cdot 9 \cdot 5$ into pairwise coprime prime powers.

[L1]

A unit is a square modulo $n$ if and only if it is a square modulo every prime-power factor of $n$ (A unit is a square modulo $n$ exactly when it is a square at every prime-power factor).

[L2]

The number of square roots of a soluble unit is the product of the local root counts (The number of square roots of a unit modulo $n$ is the product of the local counts).

Verification

technique · direct

1.1L1L2givenalgebra

The roots of $1$ are $1, 3, 5, 7$ modulo $8$ , are $1, 8$ modulo $9$ , and are $1, 4$ modulo $5$ . By [L1], every combination of these local roots gives a global root, and [L2] gives $4 \cdot 2 \cdot 2 = 16$ global roots.

2.1step 1.1L1L2algebra∎

Solving the finite CRT systems and reducing modulo $360$ gives exactly the displayed representatives. They are distinct, and reducing each one modulo $8$ , $9$ , and $5$ places it in the corresponding local root set from step 1.1, so [L1] verifies that each square is $1$ modulo $360$ ; the count in [L2] proves completeness.

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (deepseek-v4-pro + claude-sonnet-5)audited 2026-08-17Open item page →

Odd-prime tests alone miss the obstruction to $13$ being a square modulo $24$

Statement refuted

For an even modulus, testing whether a unit is a square modulo every odd prime divisor does not suffice to prove that it is a square modulo the original modulus.

Facts & Assumptions

Given: The unit $13$ modulo $24 = 8 \cdot 3$ .

[L1]

For $k \geq 3$ , an odd integer is a square modulo $2^{k}$ if and only if it is congruent to $1$ modulo $8$ (Unit square criterion and root count modulo powers of two).

[L2]

A unit square modulo $n$ is a square modulo every prime-power factor of $n$ (A unit is a square modulo $n$ exactly when it is a square at every prime-power factor).

Counterexample

technique · direct

1.1L1givenalgebra

The only odd prime divisor of $24$ is $3$ , and $13 \equiv 1 (m o d 3)$ , so it passes the odd-prime square test. But $13 \equiv 5 (m o d 8)$ , and [L1] shows that it is not a square modulo $8$ .

2.1step 1.1L2∎

If $13$ were a square modulo $24$ , the forward implication in [L2] would make it a square modulo the prime-power factor $8$ , contradicting step 1.1. Hence the odd-prime test misses the two-part obstruction.

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passaudited 2026-08-17Open item page →

Odd primes represented by a divisor of $x^{2} + 3$

Example

An odd prime $p$ divides $x^{2} + 3$ for some integer $x$ if and only if $p = 3$ or $p \equiv 1 (m o d 3)$ . Equivalently, for every odd prime $p \neq 3$ , the congruence $x^{2} \equiv - 3 (m o d p)$ is soluble if and only if $p \equiv 1 (m o d 3)$ .

Facts & Assumptions

Given: An odd prime $p$ .

[L1]

For distinct odd primes $p, q$ , $(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{(p - 1) (q - 1) / 4}$ (Quadratic reciprocity for distinct odd primes).

[L2]

For every odd prime $p$ , $(\frac{- 1}{p}) = (- 1)^{(p - 1) / 2}$ (First supplement: $(- 1 / p) = (- 1)^{(p - 1) / 2}$ ).

[L3]

For an odd prime $p$ , the Legendre symbol is $1$ exactly on the nonzero square classes modulo $p$ (The Legendre symbol, including its zero value).

[L4]

For every odd prime $p$ and integers $a, b$ , $(\frac{a b}{p}) = (\frac{a}{p}) (\frac{b}{p})$ (The Legendre symbol is multiplicative for all integer numerators).

Verification

technique · direct

1.1L1L2L4givenalgebra

Suppose $p \neq 3$ . Applying [L1] to $3$ and $p$ gives $(3 / p) (p / 3) = (- 1)^{(p - 1) / 2} = (- 1 / p)$ by [L2]. Since $(3 / p)$ is a sign and [L4] gives $(- 3 / p) = (- 1 / p) (3 / p)$ , multiplication by $(3 / p)$ yields $(- 3 / p) = (p / 3)$ .

2.1step 1.1L3algebra∎

By [L3], $x^{2} \equiv - 3 (m o d p)$ is soluble exactly when $(- 3 / p) = 1$ . For $p \neq 3$ , step 1.1 makes this equivalent to $(p / 3) = 1$ , and the nonzero square classes modulo $3$ consist only of $1$ , so this is equivalent to $p \equiv 1 (m o d 3)$ . For $p = 3$ , the class $x = 0$ directly satisfies $x^{2} \equiv - 3 (m o d 3)$ .

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + claude-sonnet-5)audited 2026-08-17Open item page →

There are infinitely many primes congruent to $1$ modulo $3$

Statement

The set of primes $p$ satisfying $p \equiv 1 (m o d 3)$ is infinite (Finite, countably infinite, countable, uncountable).

Facts & Assumptions

Given: The set $S = {p : p is prime and p \equiv 1 (m o d 3)}$ .

[L1]

For every odd prime $p \neq 3$ , the congruence $x^{2} \equiv - 3 (m o d p)$ is soluble if and only if $p \equiv 1 (m o d 3)$ (Odd primes represented by a divisor of $x^{2} + 3$ ).

[L2]

Every integer greater than $1$ has a prime divisor (Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime).

[L3]

A finite product has empty-product value $1$ and satisfies $\prod_{i < k + 1} g_{i} = (\prod_{i < k} g_{i}) g_{k}$ (The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

[L4]

In a commutative monoid, permuting the entries of a finite product does not change its value (Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either).

[L5]

A set $A$ is finite if $A \approx n$ for some $n \in N$ (Finite, countably infinite, countable, uncountable).

[L6]

The relation $A \approx B$ means that there exists a bijection $A \to B$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

[L7]

A bijection is, in particular, surjective (Injection, surjection, bijection).

[L8]

If $d ∣ u$ and $d ∣ v$ , then $d ∣ u x + v y$ for all integers $x, y$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

Proof

technique · contradiction

1.1assume-contraL2L3L5L6L7choose

Suppose, for contradiction, that $S$ is finite. By [L5] and [L6], choose a bijection from some natural number $r$ onto $S$ and write its prime values as $p_{0}, \dots, p_{r - 1}$ ; surjectivity is [L7]. Let $P = \prod_{i < r} p_{i}$ , using the value $P = 1$ if $r = 0$ from [L3], and set $N = 12 P^{2} + 1 > 1$ . By [L2], choose a prime $q ∣ N$ . Since $N$ is odd and $N \equiv 1 (m o d 3)$ , one has $q \neq 2, 3$ .

2.1step 1.1L1L3L4L8discharge-contradiction∎

From $q ∣ N$ and $(6 P)^{2} + 3 = 3 N$ , the class of $6 P$ solves $x^{2} \equiv - 3 (m o d q)$ , so [L1] gives $q \equiv 1 (m o d 3)$ . Thus $q \in S$ and equals some $p_{i}$ ; by [L4] move that factor to the end of the finite product, and then [L3] gives $q ∣ P$ , hence $q ∣ 12 P^{2}$ . Together with $q ∣ 12 P^{2} + 1$ , [L8] gives $q ∣ 1$ , impossible for a prime. Therefore $S$ is not finite.

Quadratic Reciprocity and the Jacobi Symbol — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

A complete reciprocity table for 3,5,7,113,5,7,11

Example

Facts & Assumptions

Verification

Computing (1111/8093)(1111/8093) by the Euclidean Jacobi algorithm

Example

Facts & Assumptions

Verification

Jacobi symbol one does not imply a square: (2/15)=1(2/15)=1

Statement refuted

Facts & Assumptions

Counterexample

Lifting both square roots of 22 from modulo 77 to modulo 7474

Example

Facts & Assumptions

Verification

The four square roots of 99 modulo 128128

Example

Facts & Assumptions

Verification

The square roots of 11 modulo 360360 by the Chinese remainder theorem

Example

Facts & Assumptions

Verification

Odd-prime tests alone miss the obstruction to 1313 being a square modulo 2424

Statement refuted

Facts & Assumptions

Counterexample

Odd primes represented by a divisor of x2+3x2+3

Example

Facts & Assumptions

Verification

There are infinitely many primes congruent to 11 modulo 33

Statement

Facts & Assumptions

Proof

Sources

A complete reciprocity table for $3, 5, 7, 11$

Computing $(1111 / 8093)$ by the Euclidean Jacobi algorithm

Jacobi symbol one does not imply a square: $(2 / 15) = 1$

Lifting both square roots of $2$ from modulo $7$ to modulo $7^{4}$

The four square roots of $9$ modulo $128$

The square roots of $1$ modulo $360$ by the Chinese remainder theorem

Odd-prime tests alone miss the obstruction to $13$ being a square modulo $24$

Odd primes represented by a divisor of $x^{2} + 3$

There are infinitely many primes congruent to $1$ modulo $3$