LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck 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.1givenF1F3

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

2.1step 1.1L3algebra

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$ .

2.2step 1.1L2F2F3algebra

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$ .

3.1step 2.2L1F2given

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

4.1step 2.1step 3.1algebra∎

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})$ .

Depends on

Used by

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