TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16

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.

The nonzero squares modulo an odd prime form an index-two subgroup

Statement

Let $p$ be an odd prime. The nonzero quadratic-residue classes form the subgroup

$((Z / p)^{\times})^{2} : = {u^{2} : u \in (Z / p)^{\times}} .$

For every primitive root $g$ modulo $p$ , this subgroup is $⟨ g^{2} ⟩$ and has index two in $(Z / p)^{\times}$ .

Facts & Assumptions

Given: An odd prime $p$ and the unit group $G = (Z / p)^{\times}$ .

[L1]

The group $G$ is cyclic of order $p - 1$ (For every prime $p$ , the multiplicative group $(Z / p Z)^{\times}$ is cyclic).

[L2]

For a group element $g$ , the subgroup $⟨ g ⟩$ is exactly the set of all integer powers of $g$ ( $⟨ g ⟩ = {g^{n} : n \in Z}$ , and every cyclic group is abelian).

[L3]

A group is cyclic exactly when it is generated by one element (The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups).

[L4]

The quadratic-residue classes modulo $p$ are exactly the image of squaring on $G$ (Quadratic residuosity is representative-independent and the residues are the image of squaring).

[L5]

Integer powers in a group satisfy $(g^{m})^{n} = g^{m n}$ and $g^{m + n} = g^{m} g^{n}$ (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).

[L6]

For every integer $t$ , there are unique integers $q, r$ with $t = 2 q + r$ and $0 \leq r < 2$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ ).

[L7]

The index $[G : H]$ of a finite-index subgroup is the cardinality of its coset space $G / H$ (The coset set $G / H$ and the index $[G : H]$ of a subgroup).

Proof

technique · direct

1.1L1L2L3choose

By [L1] and [L3], choose $g \in G$ with $G = ⟨ g ⟩$ ; then every $u \in G$ is $g^{t}$ for some $t \in Z$ by [L2].

2.1L4L5L6step 1.1

If $u = g^{t}$ , then $u^{2} = g^{2 t}$ by [L5], so every square lies in $⟨ g^{2} ⟩$ ; conversely $(g^{2})^{q} = (g^{q})^{2}$ , so every element of $⟨ g^{2} ⟩$ is a square. By [L4], the quadratic-residue classes are therefore exactly $⟨ g^{2} ⟩$ .

3.1L2L5L7step 1.1step 2.1∎

Write each exponent as $t = 2 q + r$ with $r \in {0, 1}$ by [L6]. Then $g^{t}$ lies in $⟨ g^{2} ⟩$ when $r = 0$ and in $g ⟨ g^{2} ⟩$ when $r = 1$ . These cosets are distinct: if $g = g^{2 q}$ , then the order $p - 1$ of $g$ would divide the odd integer $2 q - 1$ , impossible because $p - 1$ is even. Hence there are exactly two cosets, so the subgroup has index two by [L7].

Depends on

Used by

Dependency tree · two levels

40 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

W. Stein, Elementary Number Theory, Section 4.1 (standard reference, not scraped)