Session-authored (Fable 5 assisted)

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 · 5 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 4 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Quadratic Residues and the Legendre Symbol — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Quadratic residues, roots, and the Legendre table modulo $11$

Example

Modulo $11$ , the nonzero quadratic residues are $1, 3, 4, 5, 9$ , with root pairs

$1 : {1, 10}, 3 : {5, 6}, 4 : {2, 9}, 5 : {4, 7}, 9 : {3, 8} .$

For representatives $a = 0, 1, \dots, 10$ , the Legendre values are

$0, 1, - 1, 1, 1, 1, - 1, - 1, - 1, 1, - 1.$

Facts & Assumptions

Given: The odd prime modulus $11$ .

[L1]

For an odd prime $p$ , exactly $(p - 1) / 2$ nonzero classes are quadratic residues, the same number are nonresidues, and every nonzero residue has exactly two square roots (An odd prime has $(p - 1) / 2$ nonzero quadratic residues and as many nonresidues).

[L2]

The Legendre symbol is $0$ on a divisible numerator, $1$ on a quadratic residue, and $- 1$ on a quadratic nonresidue (The Legendre symbol, including its zero value).

Verification

technique · direct

1.1

Squaring $1, 2, 3, 4, 5$ modulo $11$ gives $1, 4, 9, 5, 3$ . Their negatives give the same squares, so the displayed pairs are roots of those five distinct classes; [L1] shows that this exhausts all nonzero residues and all roots.

L1givenalgebra

2.1

The remaining nonzero classes $2, 6, 7, 8, 10$ are therefore nonresidues, while the zero class is in the separate divisible branch of [L2].

L2step 1.1

3.1

Assigning $1$ to the five residue classes, $- 1$ to the five nonresidue classes, and $0$ to the zero class by [L2] gives the displayed table.

L2step 1.1step 2.1∎

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

Fourth and eighth powers modulo $17$

Example

The nonzero fourth powers modulo $17$ are $1, 4, 13, 16$ , and the nonzero eighth powers are $1, 16$ . Each fourth-power target has four fourth roots, and each eighth-power target has eight eighth roots.

Facts & Assumptions

Given: The prime modulus $17$ and nonzero target classes.

[L1]

If $n \geq 1$ admits a primitive root, $\gcd (a, n) = 1$ , $m \geq 1$ , and $d = \gcd (m, φ (n))$ , then $x^{m} \equiv a (m o d n)$ is soluble exactly when $a^{φ (n) / d} \equiv 1 (m o d n)$ (Euler's criterion: if $n$ has a primitive root, $\gcd (a, n) = 1$ , and $m \geq 1$ , then $x^{m} \equiv a (m o d n)$ is solvable if and only if $a^{φ (n) / \gcd (φ (n), m)} \equiv 1 (m o d n)$ ).

[L2]

Every prime admits a primitive root modulo that prime (Every prime modulus admits a primitive root).

[L3]

For every prime $p$ , $φ (p) = p - 1$ ( $φ (1) = 1$ , and $φ (p) = p - 1$ for every prime $p$ ).

[L4]

Under the hypotheses of [L1], a soluble congruence $x^{m} \equiv a (m o d n)$ has exactly $\gcd (φ (n), m)$ solution classes (If $n$ has a primitive root, $\gcd (a, n) = 1$ , $m \geq 1$ , and $x^{m} \equiv a (m o d n)$ is solvable, then it has exactly $\gcd (φ (n), m)$ solution classes modulo $n$ ).

[L5]

If $p ∤ a$ , then $p$ and $a$ are coprime (For a prime $p$ and any integer $a$ , $\gcd (p, a)$ is $p$ when $p ∣ a$ and $1$ otherwise; so $p ∤ a$ makes $p$ and $a$ coprime).

Verification

technique · direct

1.1

By [L2], $17$ admits a primitive root, [L3] gives $φ (17) = 16$ , and [L5] supplies the coprimality of every nonzero target. Thus [L1] says that a target is a fourth power exactly when its fourth power is $1$ , and an eighth power exactly when its square is $1$ .

L1L2L3L5given

2.1

Direct reduction gives the fourth-power values $1^{4} = 4^{4} = 13^{4} = 16^{4} \equiv 1$ , $2^{4} = 8^{4} = 9^{4} = 15^{4} \equiv 16$ , $3^{4} = 5^{4} = 12^{4} = 14^{4} \equiv 13$ , and $6^{4} = 7^{4} = 10^{4} = 11^{4} \equiv 4$ . Squaring the unit classes shows that the targets satisfying $a^{2} \equiv 1$ are exactly $1, 16$ . These lists agree with both directions of the tests in [L1].

L1step 1.1algebra

3.1

Fact [L4] gives $\gcd (16, 4) = 4$ roots for each fourth-power target and $\gcd (16, 8) = 8$ roots for each eighth-power target.

L3L4step 2.1algebra∎

CounterexampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Two quadratic nonresidues modulo $15$ can have a nonresidue product

Statement refuted

The product of two quadratic nonresidues modulo an integer need not be a quadratic residue. Modulo $15$ , the classes of $2$ and $7$ are nonresidues, and their product $14$ is also a nonresidue.

Facts & Assumptions

Given: The composite modulus $15$ .

[L1]

A unit integer is a quadratic residue modulo $n$ exactly when it has a square root modulo $n$ , and otherwise it is a quadratic nonresidue (Quadratic residues and nonresidues modulo an integer).

[L2]

The quadratic-residue classes are exactly the image of squaring on $(Z / n)^{\times}$ (Quadratic residuosity is representative-independent and the residues are the image of squaring).

[L3]

A class $[a]_{n}$ is a unit exactly when $\gcd (a, n) = 1$ (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

Counterexample

technique · direct

1.1

By [L3], the units modulo $15$ are $1, 2, 4, 7, 8, 11, 13, 14$ . Squaring them gives respectively $1, 4, 1, 4, 4, 1, 4, 1$ , so [L2] identifies the square image as exactly ${1, 4}$ .

L2L3givenalgebra

2.1

The unit classes $2, 7, 14$ lie outside that image, so [L1] and [L2] make all three quadratic nonresidues modulo $15$ .

L1L2step 1.1

3.1

Yet $2 \cdot 7 = 14 (m o d 15)$ , so the product of the two nonresidues $2$ and $7$ is the nonresidue $14$ .

step 2.1algebra∎

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

The unique cube root of $2$ modulo $29$ is $- 3$

Example

The congruence $x^{3} \equiv 2 (m o d 29)$ has the unique solution class $[- 3]_{29}$ .

Facts & Assumptions

Given: The prime $29$ , exponent $3$ , and target $2$ .

[L1]

If $p$ is prime, $k \geq 1$ , $p ∤ a$ , and $\gcd (k, p - 1) = 1$ , then $x^{k} \equiv a (m o d p)$ has one solution class; if $k ℓ \equiv 1 (m o d p - 1)$ , it is $[a^{ℓ}]_{p}$ (A coprime exponent gives a unique nonzero $k$ -th root modulo a prime).

Verification

technique · direct

1.1

Since $\gcd (3, 28) = 1$ and $3 \cdot 19 = 57 \equiv 1 (m o d 28)$ , [L1] says that the unique cube-root class is $[2^{19}]_{29}$ .

L1givenalgebra

2.1

Modulo $29$ , $2^{8} \equiv 24$ and $2^{10} \equiv 9$ , so $2^{19} = 2^{10} 2^{8} \cdot 2 \equiv 9 \cdot 24 \cdot 2 \equiv 26 \equiv - 3$ ; directly, $(- 3)^{3} = - 27 \equiv 2 (m o d 29)$ .

step 1.1algebra∎

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

Euler's criterion computes $(3 / 726377359)$ by repeated squaring

Example

Let $p = 726377359$ . Repeated squaring computes

$3^{(p - 1) / 2} = 3^{363188679} \equiv - 1 (m o d p),$

and therefore $(3 / p) = - 1$ .

For a checkable transcript, let $q_{i} \equiv 3^{2^{i}} (m o d p)$ and let $c_{i}$ be the accumulated product through bit $i$ of $363188679$ . The rows with bit $0$ leave the accumulator unchanged.

$i$	bit	$q_{i}$	$c_{i}$
0	1	3	3
1	1	9	27
2	1	81	2187
3	0	6561	2187
4	0	43046721	2187
5	0	311816404	2187
6	1	332055490	554374989
7	1	627697086	692682703
8	1	290411863	122079421
9	0	428546868	122079421
10	0	664373569	122079421
11	0	128724442	122079421
12	1	392778933	332499182
13	0	25099053	332499182
14	1	74866315	85056380
15	1	620616191	683996757
16	1	721181380	157844918
17	0	204089129	157844918
18	1	418766369	355227031
19	0	709737354	355227031
20	0	528168097	355227031
21	1	329748334	275223588
22	0	397327928	275223588
23	1	16921694	272602723
24	1	688270323	635018952
25	0	178932138	635018952
26	1	99664525	255823173
27	0	375528119	255823173
28	1	179529638	726377358

Facts & Assumptions

Given: The prime $p = 726377359$ , the binary exponent $363188679$ , and the displayed repeated-squaring transcript.

[L1]

Euler's criterion gives $(a / p) \equiv a^{(p - 1) / 2} (m o d p)$ for every integer $a$ and odd prime $p$ (Euler's criterion: $(a / p) \equiv a^{(p - 1) / 2} (m o d p)$ ).

Verification

technique · direct

1.1

Starting from $q_{0} = 3$ , each table entry satisfies $q_{i + 1} \equiv q_{i}^{2} (m o d p)$ ; the bit column is the binary expansion $363188679 = (10101101001011101000111000111)_{2}$ , and multiplying precisely the $q_{i}$ with bit $1$ gives the displayed accumulators, ending at $726377358$ .

givenalgebra

2.1

The final residue is $726377358 = p - 1 \equiv - 1 (m o d p)$ , and it is not congruent to $1$ because $p > 2$ .

step 1.1algebra

3.1

Applying [L1] with $a = 3$ and using step 2.1 gives $(3 / p) = - 1$ .

L1step 2.1∎

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

The signed half-system for $3$ modulo $11$ gives $(3 / 11) = 1$

Example

For $p = 11$ and $a = 3$ , the signed half-system is

$3, - 5, - 2, 1, 4.$

There are two negative signs, so Gauss's lemma gives $(3 / 11) = 1$ .

Facts & Assumptions

Given: The odd prime $11$ , multiplier $3$ , and the half-system $1, 2, 3, 4, 5$ .

[L1]

Multiplication by a unit modulo an odd prime reduces the half-system to unique signed representatives whose absolute values permute the half-system (Multiplication by $a$ with $p ∤ a$ permutes an odd prime's signed half-system up to sign).

[L2]

If $N (a, p)$ counts the least positive residues of $a j$ that exceed $p / 2$ for $1 \leq j \leq (p - 1) / 2$ , then $(a / p) = (- 1)^{N (a, p)}$ (Gauss's quadratic-residue lemma).

Verification

technique · direct

1.1

The products $3, 6, 9, 12, 15$ reduce modulo $11$ to the signed representatives $3, - 5, - 2, 1, 4$ .

L1givenalgebra

2.1

Their absolute values are $3, 5, 2, 1, 4$ , a permutation of $1, 2, 3, 4, 5$ as [L1] requires, and exactly two signs are negative.

L1step 1.1

3.1

Fact [L2] gives $(3 / 11) = (- 1)^{2} = 1$ .

L2step 2.1∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-16Open item page →

A nonmonic quadratic congruence solved through its discriminant

Example

The congruence

$3 x^{2} + 4 x + 1 \equiv 0 (m o d 11)$

has exactly the two solution classes $[7]_{11}$ and $[10]_{11}$ .

Facts & Assumptions

Given: The polynomial $3 x^{2} + 4 x + 1$ modulo the odd prime $11$ .

[L1]

If $p$ is odd and $p ∤ A$ , then $A x^{2} + B x + C \equiv 0 (m o d p)$ has exactly $1 + ((B^{2} - 4 A C) / p)$ solution classes (The discriminant counts roots of $A x^{2} + B x + C \equiv 0 (m o d p)$ for odd prime $p ∤ A$ ).

[L2]

For an odd prime $p$ , $(\frac{a}{p}) = 1$ when $p ∤ a$ and $a$ is a quadratic residue modulo $p$ , and $(\frac{a}{p}) = - 1$ when $p ∤ a$ and $a$ is a quadratic nonresidue modulo $p$ (The Legendre symbol, including its zero value).

[L3]

The quotient $Z / p$ is a field (For every prime $p$ , the two operations on $Z / p$ make it a field).

Verification

technique · direct

1.1

The discriminant is $Δ = 4^{2} - 4 \cdot 3 \cdot 1 = 4$ . Here $11 ∤ 4$ and $2^{2} = 4$ , so $4$ is a quadratic residue modulo $11$ and [L2] gives $(Δ / 11) = 1$ .

L2givenalgebra

2.1

Since $11$ is odd and $11 ∤ 3$ , fact [L1] applies and predicts exactly $1 + 1 = 2$ solution classes.

L1step 1.1

3.1

Completing the square gives $(6 x + 4)^{2} \equiv 4 (m o d 11)$ , so $((6 x + 4) - 2) ((6 x + 4) + 2) \equiv 0 (m o d 11)$ ; by [L3] the field $Z / 11$ has no zero divisors, so $6 x + 4 \equiv 2$ or $6 x + 4 \equiv - 2$ . Since $6^{- 1} \equiv 2 (m o d 11)$ , these yield $x \equiv 7$ and $x \equiv 10$ ; direct substitution gives $176 \equiv 0$ and $341 \equiv 0 (m o d 11)$ . Thus both predicted classes occur.

L3step 1.1step 2.1algebra∎

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Squaring is not a homomorphism on a nonabelian group

Statement refuted

The squaring map $s (g) = g^{2}$ need not be a group homomorphism. It fails on the nonabelian symmetric group $S_{3}$ .

Facts & Assumptions

Given: The permutations $τ = (1 2)$ and $ρ = (2 3)$ of ${1, 2, 3}$ , composed from right to left.

[L1]

The symmetric group on a set consists of its permutations under composition (The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition).

[L2]

The symmetric group on every set is a group, and on a set with three distinct elements it is nonabelian ( $Sym (X)$ is a group under composition, and it is non-abelian whenever $X$ has at least three distinct elements).

[L3]

Natural powers in a group satisfy $g^{0} = e$ and $g^{n + 1} = g^{n} g$ (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ ).

[L4]

Group powers satisfy $(g^{m})^{n} = g^{m n}$ , and if $g h = h g$ then $(g h)^{n} = g^{n} h^{n}$ ; that last claim is false in general without its hypothesis, and the equation can fail already at $n = 2$ (Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute).

[L5]

A group homomorphism $f$ satisfies $f (x y) = f (x) f (y)$ for all $x, y$ (Monoid homomorphism and group homomorphism).

Counterexample

technique · direct

1.1

By [L1] and [L2], $τ, ρ \in S_{3}$ , and their product is $τ ρ = (1 2 3)$ under the stated composition convention.

L1L2given

2.1

The two transpositions satisfy $τ^{2} = ρ^{2} = e$ , while [L3] gives $(τ ρ)^{2} = (1 3 2) \neq e$ . Here $ρ τ = (1 3 2) \neq (1 2 3) = τ ρ$ , so $τ$ and $ρ$ do not commute and the hypothesis of the power law in [L4] is not met; [L4] records that the equation can fail at $n = 2$ in exactly that case.

L3L4step 1.1

3.1

Therefore $s (τ ρ) = (τ ρ)^{2} \neq e = τ^{2} ρ^{2} = s (τ) s (ρ)$ , so $s$ violates the homomorphism identity [L5].

L5step 2.1∎

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

A soluble square congruence need not define a quadratic residue

Statement refuted

Solubility of $x^{2} \equiv a (m o d p)$ does not by itself make $a$ a quadratic residue. For every odd prime $p$ , the target $a = 0$ gives a soluble congruence but belongs to neither the residue nor the nonresidue class.

Facts & Assumptions

Given: An odd prime $p$ and the target $a = 0$ .

[L1]

For every integer $a$ and odd prime $p$ , $x^{2} \equiv a (m o d p)$ has exactly $1 + (a / p)$ solution classes ( $x^{2} \equiv a (m o d p)$ has exactly $1 + (a / p)$ solution classes).

[L2]

The terms quadratic residue and quadratic nonresidue modulo $n$ are defined only for integers coprime to $n$ (Quadratic residues and nonresidues modulo an integer).

[L3]

The Legendre symbol has value $0$ when its numerator is divisible by the odd prime denominator (The Legendre symbol, including its zero value).

Counterexample

technique · direct

1.1

Since $(0 / p) = 0$ by [L3], fact [L1] gives exactly one solution class to $x^{2} \equiv 0 (m o d p)$ ; it is visibly the zero class.

L1L3given

2.1

Yet $\gcd (0, p) = p \neq 1$ , so [L2] puts zero outside the quadratic residue and nonresidue dichotomy, and [L3] assigns it the separate Legendre value zero. Thus the congruence is soluble without making its target a quadratic residue.

L2L3step 1.1∎

Sources

Standard references

Recommended treatments; not extraction sources.

Quadratic Residues and the Legendre Symbol — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Quadratic residues, roots, and the Legendre table modulo 1111

Example

Facts & Assumptions

Verification

Fourth and eighth powers modulo 1717

Example

Facts & Assumptions

Verification

Two quadratic nonresidues modulo 1515 can have a nonresidue product

Statement refuted

Facts & Assumptions

Counterexample

The unique cube root of 22 modulo 2929 is −3−3

Example

Facts & Assumptions

Verification

Euler's criterion computes (3/726377359)(3/726377359) by repeated squaring

Example

Facts & Assumptions

Verification

The signed half-system for 33 modulo 1111 gives (3/11)=1(3/11)=1

Example

Facts & Assumptions

Verification

A nonmonic quadratic congruence solved through its discriminant

Example

Facts & Assumptions

Verification

Squaring is not a homomorphism on a nonabelian group

Statement refuted

Facts & Assumptions

Counterexample

A soluble square congruence need not define a quadratic residue

Statement refuted

Facts & Assumptions

Counterexample

Sources

Standard references

Quadratic residues, roots, and the Legendre table modulo $11$

Fourth and eighth powers modulo $17$

Two quadratic nonresidues modulo $15$ can have a nonresidue product

The unique cube root of $2$ modulo $29$ is $- 3$

Euler's criterion computes $(3 / 726377359)$ by repeated squaring

The signed half-system for $3$ modulo $11$ gives $(3 / 11) = 1$