LemmaStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passjudge pass (deepseek-v4-pro + claude-opus-5[1m])audited 2026-08-24

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.

A prime congruent to $3$ modulo $4$ divides both coordinates of a divisible two-square sum

Statement

If $q \equiv 3 (m o d 4)$ is prime and $q ∣ x^{2} + y^{2}$ , then $q ∣ x$ and $q ∣ y$ . Consequently $q^{2} ∣ x^{2} + y^{2}$ .

Facts & Assumptions

Given: A prime $q \equiv 3 (m o d 4)$ and integers $x, y$ such that $q ∣ x^{2} + y^{2}$ .

[F1]

A representation of a nonnegative integer $n$ as a sum of two squares is an ordered pair $(x, y) \in Z^{2}$ such that $n = x^{2} + y^{2}$ (Representations and primitive representations as sums of two squares).

[L1]

For an odd prime $p$ , $(- 1 / p) = 1$ if and only if $p \equiv 1 (m o d 4)$ , while $(- 1 / p) = - 1$ if and only if $p \equiv 3 (m o d 4)$ (First supplement: $(- 1 / p) = (- 1)^{(p - 1) / 2}$ ).

[F2]

For an odd prime $p$ , the Legendre symbol is $0$ when $p$ divides the numerator, $1$ when its nonzero class is a square, and $- 1$ otherwise (The Legendre symbol, including its zero value).

[L2]

For every prime $p$ , addition and multiplication make $Z / p$ a field (For every prime $p$ , the two operations on $Z / p$ make it a field).

[L3]

If a prime $p$ divides $a b$ , then $p ∣ a$ or $p ∣ b$ (Euclid's lemma: if $p$ is prime and $p ∣ a b$ then $p ∣ a$ or $p ∣ b$ ).

[F3]

The congruence $a \equiv b (m o d n)$ means that $n ∣ (a - b)$ (Congruence modulo an integer: $a \equiv b (m o d n)$ when $n ∣ (a - b)$ , including the moduli $0$ and $1$ ).

Proof

technique · direct

1.1

The divisibility hypothesis is the congruence $x^{2} + y^{2} \equiv 0 (m o d q)$ .

givenF1F3

2.1

If $q ∣ y$ , then step 1.1 gives $q ∣ x^{2}$ , so [L3] gives $q ∣ x$ ; the same argument with the coordinates interchanged handles $q ∣ x$ .

step 1.1L3algebra

2.2

If neither coordinate were divisible by $q$ , the nonzero class of $y$ would be invertible in the field $Z / q$ , and step 1.1 would give $(x y^{- 1})^{2} = - 1$ . Thus $- 1$ would be a nonzero quadratic residue and $(- 1 / q) = 1$ .

step 1.1L2F2F3algebra

3.1

Since $q \equiv 3 (m o d 4)$ , [L1] instead gives $(- 1 / q) = - 1$ , contradicting step 2.2.

step 2.2L1F2given

4.1

Hence at least one coordinate is divisible by $q$ , and step 2.1 makes both divisible by $q$ . Writing $x = q x_{0}$ and $y = q y_{0}$ gives $x^{2} + y^{2} = q^{2} (x_{0}^{2} + y_{0}^{2})$ .

step 2.1step 3.1algebra∎

Depends on

Used by

539=7²·11 is not a sum of two squares Counterexample
Prime powers represented as sums of two squares Lemma
Characterisation of positive integers that are sums of two squares Theorem
Characterisation of primitive sums of two squares Theorem

Dependency tree · two levels

23 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

P. Hackman, Elementary Number Theory, Chapter E, §E.II.2 (standard reference, not scraped)
W. Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Lemma 5.7.4 (standard reference, not scraped)

A prime congruent to 33 modulo 44 divides both coordinates of a divisible two-square sum