Quadratic Residues and Nonresidues

Fix a prime number pp and ask a simple question. Which nonzero remainders modulo pp are perfect squares? For p=7p=7, squaring every nonzero residue gives 1,4,2,2,4,11,4,2,2,4,1. So only {1,2,4}\{1,2,4\} arise as squares, while {3,5,6}\{3,5,6\} never do. This split of the nonzero residues into "squares" and "non-squares" looks like an accident of arithmetic. But it turns out to be one of the most structured phenomena in elementary number theory. It is exactly half and half, always, for every odd prime. This partition matters because it governs the solvability of the humble equation x2≡a(modp)x^2 \equiv a \pmod p. This in turn controls sums of two squares, the arithmetic of quadratic forms, primality tests, and the design of pseudorandom sequences. These sequences are used in cryptography and coding theory. Whether −1-1, 22, or 55 is a square modulo pp dictates which primes divide numbers of the form n2+1n^2+1, n2−2n^2-2, or n2−5n^2-5. This is exactly the kind of question that separates elementary from deep number theory. The big picture is that the multiplicative group of nonzero residues modulo pp is cyclic of even order p−1p-1. It is denoted (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times. Squaring is a group homomorphism on this cyclic group. The image of a homomorphism from a cyclic group of even order onto itself has index exactly 22 in the target. This single group-theoretic fact, once unpacked, is the entire reason quadratic residues split the nonzero residues exactly in half. This article gives the precise definition of quadratic residues and nonresidues modulo an odd prime. It proves the exact counting theorem: there are p−12\frac{p-1}{2} of each. It also builds the intuition — via the cyclic structure of (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times — that will be packaged in later articles. These later articles are Euler's Criterion and The Legendre Symbol.

Key takeaways
  • A quadratic residue mod pp is a nonzero remainder that equals some x2  px^2 \bmod p; a nonresidue is a nonzero remainder that never does.
  • For any odd prime pp, exactly p−12\frac{p-1}{2} of the p−1p-1 nonzero residues are quadratic residues, and p−12\frac{p-1}{2} are nonresidues.
  • The proof uses that (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times is cyclic and that squaring is exactly 22-to-11 on it.
  • Zero is excluded from the definition by convention; it behaves separately and trivially (02=00^2 = 0).
  • The residue −1-1 is a quadratic residue mod pp exactly when p≡1(mod4)p \equiv 1 \pmod 4, a first hint of deeper reciprocity laws.
  • This counting fact is the seed for Euler's Criterion and the Legendre symbol, which give computational tests for residue status.
  • Key idea: squaring is a 2-to-1 group homomorphism on a cyclic group of even order, so the squares are precisely half the group.

Where this lives today

The exact halving of quadratic residues underlies Euler's Criterion, which computes residue status via a(p−1)/2  pa^{(p-1)/2} \bmod p, and the Legendre symbol, the ±1\pm1-valued function that packages residue/nonresidue status algebraically and obeys the multiplicative law (abp)=(ap)(bp)\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) — both are direct successors to the counting fact proved here. This machinery feeds directly into Quadratic Reciprocity, which lets one decide residue status of large numbers without brute-force search. Quadratic residues also drive the quadratic sieve and other integer-factorization algorithms, where finding congruences x2≡y2(modn)x^2 \equiv y^2 \pmod n with x≢±yx \not\equiv \pm y exploits exactly the residue structure explored above. In cryptography, the Rabin cryptosystem and quadratic-residuosity-based schemes (including Goldwasser–Micali probabilistic encryption) rest on the presumed hardness of distinguishing residues from nonresidues modulo a composite with unknown factorization. In coding theory and sequence design, Legendre sequences, built from the ±1\pm1 pattern of residues mod pp, give pseudorandom binary sequences with excellent autocorrelation properties, used in radar and spread-spectrum communications. Finally, the question of which primes represent n2+1n^2+1, or divide values of n2−dn^2 - d, connects directly back to whether −1-1 or dd is a residue mod pp — a thread that leads into the theory of Binary Quadratic Forms.

Ask the tutor: How does Euler's Criterion turn this counting fact into a fast test for whether a specific number is a quadratic residue modulo a large prime?

DefinitionQuadratic residue and nonresidue modulo a prime

Let pp be an odd prime. An integer aa with p∤ap \nmid a is called a quadratic residue modulo pp if the congruence

x2≡a(modp)x^2 \equiv a \pmod{p}

has a solution x∈Zx \in \mathbb{Z}. If no such xx exists, aa is called a quadratic nonresidue modulo pp. Since residue status depends only on the class of aa modulo pp, this partitions the set of nonzero residue classes

{1,2,…,p−1}⊂Z/pZ\{1, 2, \dots, p-1\} \subset \mathbb{Z}/p\mathbb{Z}

into two disjoint subsets: the quadratic residues QRpQR_p and the quadratic nonresidues QNRpQNR_p, with

QRp∪QNRp={1,…,p−1},QRp∩QNRp=∅.QR_p \cup QNR_p = \{1,\dots,p-1\}, \qquad QR_p \cap QNR_p = \varnothing.

The class 00 is conventionally excluded from both sets: 00 is always a square (0=020=0^2) but carries no information, since p∣ap \mid a makes x2≡ax^2\equiv a trivially solvable by x≡0x\equiv 0.

Intuition

Think of (Z/pZ)×={1,2,…,p−1}(\mathbb{Z}/p\mathbb{Z})^\times = \{1, 2, \dots, p-1\} under multiplication as a clock with p−1p-1 hours, arranged (using a generator) in a cycle. Squaring sends each element to another element of the same cycle. Because the group is cyclic of even order p−1p-1, squaring behaves exactly like the map "double the exponent" on a cyclic group of even order — and doubling exponents modulo an even number p−1p-1 hits exactly half the possible exponents, each exactly twice. Concretely, for p=11p=11 the group (Z/11Z)×(\mathbb{Z}/11\mathbb{Z})^\times has order 1010 and is generated by 22, since the powers of 22 modulo 1111 are 2,4,8,5,10,9,7,3,6,12,4,8,5,10,9,7,3,6,1 — all ten nonzero residues, confirming 22 is a primitive root. Writing each nonzero residue as 2k2^k for k=0,…,9k=0,\dots,9, squaring corresponds to doubling kk modulo 1010. The exponents kk for which 2k  102k \bmod 10 can equal any given even target are exactly the even kk; squaring an odd-exponent element gives an even exponent times two, which is even, and running over all k=0,…,9k=0,\ldots,9, the squares 22k  102^{2k \bmod 10} only ever land on the elements with even exponent. There are five even exponents among 0,…,90,\dots,9, matching p−12=5\frac{p-1}{2}=5 residues. A second way to see the same fact: the squaring map x↦x2x \mapsto x^2 on (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times satisfies x2=(−x)2x^2 = (-x)^2, and since pp is odd, x≢−xx \not\equiv -x for x≢0x \not\equiv 0. So the p−1p-1 nonzero elements pair up into p−12\frac{p-1}{2} pairs {x,−x}\{x,-x\}, each pair giving a single square, and different pairs give different squares (this is the content of the theorem below, proved rigorously).

Figure
Squaring on (Z/11Z)×(\mathbb{Z}/11\mathbb{Z})^\times: ten elements collapse onto five residues
Domain: x = 1..10 (mod 11) Codomain: x² mod 11 1 2 3 4 5 6 7 8 9 10 1 3 4 5 9 Red dots {1,3,4,5,9}: the five quadratic residues mod 11; each is hit by exactly two domain points.
TheoremCounting quadratic residues modulo a prime

Let pp be an odd prime. Among the p−1p-1 nonzero residue classes modulo pp, exactly p−12\frac{p-1}{2} are quadratic residues and exactly p−12\frac{p-1}{2} are quadratic nonresidues. Moreover, the quadratic residues are precisely the residue classes of

12,22,…,(p−12)2(modp),1^2, 2^2, \dots, \left(\frac{p-1}{2}\right)^2 \pmod p,

and these p−12\frac{p-1}{2} values are pairwise distinct modulo pp.

Proof

We use elementary properties of congruences and of the group (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times (the nonzero residues under multiplication mod pp), which is known to consist of exactly p−1p-1 elements since pp is prime.

Step 1: Every quadratic residue is the square of some xx in {1,…,p−12}\{1,\dots,\frac{p-1}{2}\}. Let aa be a quadratic residue modulo pp, so a≡x2(modp)a \equiv x^2 \pmod p for some integer xx with p∤xp \nmid x (if p∣xp\mid x then a≡0a\equiv 0, excluded since a∈{1,…,p−1}a\in\{1,\dots,p-1\}). Reduce xx modulo pp to assume 1≤x≤p−11 \le x \le p-1. If x≤p−12x \le \frac{p-1}{2}, we are done. Otherwise x≥p+12x \ge \frac{p+1}{2}; set y=p−xy = p - x. Then 1≤y≤p−121 \le y \le \frac{p-1}{2}, and

y2=(p−x)2=p2−2px+x2≡x2≡a(modp).y^2 = (p-x)^2 = p^2 - 2px + x^2 \equiv x^2 \equiv a \pmod p.

So aa is also the square of y∈{1,…,p−12}y \in \{1,\dots,\frac{p-1}{2}\}. Either way, aa is congruent to the square of some integer in {1,…,p−12}\{1,\dots,\frac{p-1}{2}\}.

Step 2: The list 12,22,…,(p−12)21^2, 2^2, \dots, \left(\frac{p-1}{2}\right)^2 is a complete list of the quadratic residues. By definition, each term k2k^2 in this list (1≤k≤p−121 \le k \le \frac{p-1}{2}) is a quadratic residue (it is literally a square, and k2≢0k^2 \not\equiv 0 since p∤kp \nmid k as k<pk < p). Step 1 shows every quadratic residue occurs among these values. Hence the set of values taken by {k2  p:1≤k≤p−12}\{k^2 \bmod p : 1 \le k \le \tfrac{p-1}{2}\} equals QRpQR_p exactly.

Step 3: These p−12\frac{p-1}{2} values are pairwise distinct modulo pp. Suppose 1≤i<j≤p−121 \le i < j \le \frac{p-1}{2} and i2≡j2(modp)i^2 \equiv j^2 \pmod p. Then

p∣(j2−i2)=(j−i)(j+i).p \mid (j^2 - i^2) = (j-i)(j+i).

Since pp is prime, pp divides j−ij - i or pp divides j+ij+i. Now 0<j−i<p−12<p0 < j - i < \frac{p-1}{2} < p, so p∤(j−i)p \nmid (j-i). Also 2≤i+j≤p−1<p2 \le i + j \le p - 1 < p (using i,j≥1i,j \ge 1 and i,j≤p−12i,j \le \frac{p-1}{2}, so i+j≤p−1i+j \le p-1), so p∤(j+i)p \nmid (j+i) either. This contradicts p∣(j−i)(j+i)p \mid (j-i)(j+i). Hence no such i<ji<j exist, and the p−12\frac{p-1}{2} squares 12,…,(p−12)21^2,\dots,\left(\frac{p-1}{2}\right)^2 are pairwise incongruent modulo pp.

Step 4: Conclusion. By Step 2, QRpQR_p is exactly the set of residues of 12,…,(p−12)21^2,\dots,\left(\frac{p-1}{2}\right)^2, and by Step 3 these are p−12\frac{p-1}{2} distinct residues. Hence

∣QRp∣=p−12.|QR_p| = \frac{p-1}{2}.

Since QRpQR_p and QNRpQNR_p partition the p−1p-1 nonzero residues (every nonzero a  pa \bmod p is either a square or not, by definition, with no overlap), we get

∣QNRp∣=(p−1)−∣QRp∣=(p−1)−p−12=p−12.|QNR_p| = (p-1) - |QR_p| = (p-1) - \frac{p-1}{2} = \frac{p-1}{2}.

This completes the proof. ■\blacksquare

∎

The proof technique here is direct counting via pairing (x↔p−xx \leftrightarrow p-x) combined with a divisibility argument in a prime modulus (Step 3), avoiding any appeal to primitive roots or Euler's criterion — those are logically downstream results, not needed here, which keeps this proof self-contained and non-circular.

CorollarySquaring is exactly 2-to-1 on (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times

For an odd prime pp, the squaring map σ:(Z/pZ)×→(Z/pZ)×\sigma: (\mathbb{Z}/p\mathbb{Z})^\times \to (\mathbb{Z}/p\mathbb{Z})^\times, σ(x)=x2\sigma(x) = x^2, has image exactly QRpQR_p, and every element of QRpQR_p has exactly two preimages under σ\sigma, namely {x,−x}\{x, -x\} for some xx.

Proof

The image of σ\sigma is QRpQR_p by definition of quadratic residue. If σ(x)=σ(y)=a\sigma(x) = \sigma(y) = a, then p∣x2−y2=(x−y)(x+y)p \mid x^2 - y^2 = (x-y)(x+y), so (as pp is prime) x≡yx \equiv y or x≡−y(modp)x \equiv -y \pmod p. These give at most two distinct preimages, xx and −x≡p−x-x \equiv p - x; they are distinct since pp is odd, so x≡−xx \equiv -x would force 2x≡02x\equiv 0, impossible for x≢0(modp)x\not\equiv 0 \pmod p (as pp is odd, 22 is invertible mod pp). Both do map to the same square: x2=(−x)2x^2 = (-x)^2. Hence exactly two preimages for each element of QRpQR_p. Since ∣(Z/pZ)×∣=p−1|(\mathbb{Z}/p\mathbb{Z})^\times| = p-1 and each of the ∣QRp∣|QR_p| image points has exactly 22 preimages partitioning the domain, 2∣QRp∣=p−12|QR_p| = p-1, recovering ∣QRp∣=p−12|QR_p| = \frac{p-1}{2} as an alternative route to the theorem. ■\blacksquare

∎

Worked examples

Example 1: p=13p = 13. Here p−12=6\frac{p-1}{2} = 6. Compute k2  13k^2 \bmod 13 for k=1,…,6k=1,\dots,6:

12=1,22=4,32=9,42=16≡3,52=25≡12,62=36≡10.1^2=1,\quad 2^2=4,\quad 3^2=9,\quad 4^2=16\equiv 3,\quad 5^2=25\equiv 12,\quad 6^2=36\equiv 10.

So QR13={1,3,4,9,10,12}QR_{13} = \{1,3,4,9,10,12\}, a set of size 66 as predicted, and QNR13={2,5,6,7,8,11}QNR_{13} = \{2,5,6,7,8,11\}, also size 66. Sanity check via the pairing x↔13−xx \leftrightarrow 13-x: e.g. 7=13−67 = 13-6, and indeed 72=49≡49−39=10≡62(mod13)7^2 = 49 \equiv 49 - 39 = 10 \equiv 6^2 \pmod{13} — matches, both give 1010. Also 11=13−211 = 13-2 and 112=121≡121−117=4≡22(mod13)11^2 = 121 \equiv 121-117=4 \equiv 2^2\pmod{13} — consistent. This confirms Step 3's pairing mechanism concretely: the squares of 7,…,127,\dots,12 merely repeat the squares of 6,…,16,\dots,1 in reverse order. Notice 12=−1  13∈QR1312 = -1 \bmod 13 \in QR_{13}, and indeed 13≡1(mod4)13 \equiv 1 \pmod 4, consistent with the later fact (a preview of quadratic reciprocity) that −1-1 is a residue exactly when p≡1(mod4)p\equiv 1\pmod 4.

Example 2: p=19p = 19 — verifying non-multiplicativity of the naive residue count, and checking an asymmetric value. Here p−12=9\frac{p-1}{2}=9. Compute k2  19k^2 \bmod 19 for k=1,…,9k=1,\dots,9:

1, 4, 9, 16, 25≡6, 36≡17, 49≡11, 64≡7, 81≡5.1,\ 4,\ 9,\ 16,\ 25\equiv 6,\ 36\equiv 17,\ 49\equiv 11,\ 64\equiv 7,\ 81\equiv 5.

So QR19={1,4,5,6,7,9,11,16,17}QR_{19} = \{1,4,5,6,7,9,11,16,17\} — count them: nine values, matching 19−12=9\frac{19-1}{2}=9 exactly. Now ask: is a=13a=13 a quadratic residue mod 1919? Scan the list {1,4,5,6,7,9,11,16,17}\{1,4,5,6,7,9,11,16,17\}: 1313 is absent. So 13∈QNR1913 \in QNR_{19}, and indeed one can confirm directly that no x∈{1,…,18}x\in\{1,\dots,18\} satisfies x2≡13(mod19)x^2\equiv 13\pmod{19} by noting 1313 is not among the 99 computed squares, and every square mod 1919 appears in that list by Step 1 of the theorem (every xx pairs with 19−x19-x to reduce to the range 1,…,91,\dots,9). Is a=17a = 17 a residue? Yes — it is 62  196^2 \bmod 19. So x2≡17(mod19)x^2 \equiv 17 \pmod{19} has the two solutions x≡±6≡6,13(mod19)x \equiv \pm 6 \equiv 6, 13 \pmod{19}. Check: 132=169=8⋅19+17≡1713^2 = 169 = 8\cdot 19 + 17 \equiv 17. Confirmed, and this exhibits the Corollary's "exactly two preimages" claim concretely with an asymmetric pair (6,13)(6,13) rather than a symmetric-looking small pair.

CounterexampleWhy "pp prime" cannot be dropped: composite moduli break the exact halving

Take the composite modulus m=8m = 8 in place of an odd prime. The nonzero residues coprime to 88 are {1,3,5,7}\{1,3,5,7\} (φ(8)=4\varphi(8)=4 of them). Squaring each:

12=1,32=9≡1,52=25≡1,72=49≡1(mod8).1^2 = 1,\quad 3^2 = 9 \equiv 1,\quad 5^2 = 25 \equiv 1,\quad 7^2 = 49 \equiv 1 \pmod 8.

Every unit modulo 88 squares to 11. So among the 44 units, only 11 residue class ({1}\{1\}) is a square, not φ(8)/2=2\varphi(8)/2 = 2. The clean "exactly half" count utterly fails: here it is 14\frac14, not 12\frac12. The reason the theorem's proof breaks down is visible directly in Step 3: the key divisibility step used that pp is prime, so that p∣(j−i)(j+i)p \mid (j-i)(j+i) forces pp dividing one of the factors. For m=8m=8 (composite, in fact a prime power 232^3), we can have 8∣(j−i)(j+i)8 \mid (j-i)(j+i) with 88 dividing neither factor — e.g. i=1,j=3i=1, j=3: (j−i)(j+i)=2⋅4=8(j-i)(j+i) = 2\cdot 4 = 8, divisible by 88, yet neither 22 nor 44 is divisible by 88. This is exactly why 12≡32(mod8)1^2 \equiv 3^2 \pmod 8 despite 1≠31 \ne 3: the distinctness argument of Step 3 needs primality, and without it, squares can collapse onto far fewer than half of the units. (Separately, m=8m=8 is even, so the pairing x↔−xx \leftrightarrow -x used in the intuition is also degenerate: x=3x=3 pairs with −3≡5-3\equiv 5, a different residue than x=1x=1 pairs with −1≡7-1\equiv 7, yet both pairs produce the same square 11 — the pairs are disjoint but not square-distinguishing, which is precisely the multiplicity failure.)

Scope, edge cases & common traps

SituationWhat happensWhy
p=2p=2Every nonzero residue mod 22 is just 11, and 1=121=1^2; the "half-and-half" split is vacuous/degeneratep−1=1p-1=1 is odd, not even, so the group is trivial and the halving argument (needs pp odd) does not apply
a≡0(modp)a \equiv 0 \pmod pExcluded from QRp,QNRpQR_p, QNR_p by convention00 is always a square but conveys no residue-splitting information
Composite modulus mmResidue counts among units need not be φ(m)/2\varphi(m)/2Step 3 of the proof needs primality of the modulus; see Counterexample
Checking if aa is a QR by trial squaringCorrect but slow (O(p)O(p) naively, O(p/2)O(p/2) using the pairing)Faster criteria (Euler's Criterion, quadratic reciprocity) come later and avoid brute force
Confusing "aa has a square root mod pp" with "aa has a square root mod p2p^2"These are different questions (Hensel lifting needed for the latter)The definition here is strictly mod a single prime pp, not a prime power

The mathematician behind it

Origins · 1 minCarl Friedrich Gauss and how this was discovered
CF
Carl Friedrich Gauss
1777–1855 · Germany, foundational work in number theory and quadratic reciprocity

Gauss gave the first complete proofs of the Quadratic Reciprocity law in his 1801 Disquisitiones Arithmeticae, the book that turned quadratic residues from scattered curiosities into a structured theory. He returned to reciprocity repeatedly over his life, eventually publishing (or leaving) eight distinct proofs, each illuminating a different facet of the phenomenon — Gauss sums, lattice-point counting, and cyclotomy among them. His painstaking numerical tables of residues for small primes, computed by hand, informed the conjectural patterns he later proved.

History
- 1640: Fermat studies which primes divide n2+1n^2+1, implicitly using quadratic residues of −1-1.
- 1750s: Euler formulates a criterion (later named for him) for recognizing quadratic residues via exponentiation.
- 1785: Legendre introduces the symbol (ap)\left(\frac{a}{p}\right) and states reciprocity, without a complete proof.
- 1801: Gauss publishes the Disquisitiones Arithmeticae, giving the first rigorous proof of quadratic reciprocity.
- 1839: Eisenstein gives a strikingly short geometric proof of reciprocity, refining Gauss's lattice-point argument.
Is 00 ever called a quadratic residue?

By the standard convention used in this article and in most textbooks (Hardy–Wright, Ireland–Rosen), no: quadratic residues and nonresidues are defined only for aa with p∤ap \nmid a. The class 00 is a perfect square (0=020=0^2) but including it would break the clean count of p−12\frac{p-1}{2} each, since it would leave an odd total of pp classes to split. Some authors informally say "00 is always trivially a square" as an aside, but it is not assigned to QRpQR_p or QNRpQNR_p. Always check which convention a given source uses before comparing counts.

Does the theorem say anything about which specific numbers are residues, or just the count?

Only the count, and a description of QRpQR_p as the squares of 1,…,p−121,\dots,\frac{p-1}{2}. It does not tell you, for instance, whether 22 is a residue mod a given prime without computing 2  2 \bmod that range's squares directly. Determining residue status of a specific small number like −1-1, 22, or 33 efficiently for large primes is exactly what Euler's Criterion and the quadratic reciprocity law are built to do, building on the group structure exposed in the proof here.

Why does (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times being cyclic matter, even though the proof given avoids using it?

The proof given uses only elementary divisibility, deliberately avoiding the (true, but separately proved) fact that (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times is cyclic, to keep this foundational result self-contained. However, cyclicity gives a second, illuminating proof: if gg is a primitive root mod pp, every nonzero residue is gkg^k for a unique k∈{0,…,p−2}k \in \{0,\dots,p-2\}, and gkg^k is a square exactly when kk is even, since (p−1)(p-1) is even, half the exponents 0,…,p−20,\dots,p-2 are even. This is the "clock doubling" picture from the Intuition section, and it generalizes more easily to prime powers and other cyclic groups.

Is the number of quadratic residues ever not equal to (p−1)/2(p-1)/2 for an odd prime?

No — the theorem proved above is unconditional for every odd prime pp, with no exceptions. The count p−12\frac{p-1}{2} holds for p=3p=3 (giving 11 residue, namely {1}\{1\}), all the way up through arbitrarily large primes. What can vary from prime to prime is which specific numbers land in QRpQR_p versus QNRpQNR_p — that pattern is governed by quadratic reciprocity, not by this counting theorem.

How does this relate to solving x2≡a(modp)x^2 \equiv a \pmod p in practice?

This theorem tells you how many aa's admit solutions (exactly half), and the proof's Step 1–3 tell you that if a solution exists, it can be found among x∈{1,…,p−12}x \in \{1,\dots,\frac{p-1}{2}\}, with exactly two solutions overall (±x\pm x) once one is found, by the Corollary. It does not by itself give an efficient algorithm to find xx for large pp; that is the separate problem of modular square root extraction (e.g. Tonelli–Shanks), which uses Euler's Criterion first to check solvability.

Does the "exactly half" count generalize to prime powers or composite moduli?

Not in the same clean form. For an odd prime power pkp^k, one can show the units mod pkp^k still split with exactly φ(pk)2\frac{\varphi(p^k)}{2} squares among the φ(pk)\varphi(p^k) units, because (Z/pkZ)×(\mathbb{Z}/p^k\mathbb{Z})^\times is still cyclic for odd pp. But for m=2km=2^k with k≥3k\ge 3, the group (Z/2kZ)×(\mathbb{Z}/2^k\mathbb{Z})^\times is not cyclic, and the fraction of squares among units is 14\frac14, not 12\frac12 — exactly the phenomenon shown in the Counterexample block for m=8m=8. General composite mm requires the Chinese Remainder Theorem to combine residue conditions prime-by-prime, and the resulting fraction of residues is generally smaller than 12\frac12.

Where this leads