For odd , let be a nonsingular cubic Weierstrass equation of an elliptic curve over . Its Trace of Frobenius is , where is the Legendre symbol extended by . By the Euler criterion, reduce this sum to . The sum of a positive power over is zero unless divides , when it is . Since the polynomial has degree , only its coefficient contributes.
Gauss's lemma (number theory) Created 2026-10-14 Updated 2026-11-05
Let be an odd prime and an integer with . Reduce
to their least positive residue classes modulo . If exactly of these representatives exceed , Gauss's lemma states
The symbol on the left is the Legendre symbol. For example, and give representatives . Exactly one exceeds , so is a quadratic nonresidue modulo .
For a proof, replace every representative above by its negative modulo , obtaining numbers in . These numbers are distinct: equality would give , forcing because . They therefore form a permutation of . Multiplying the signed representatives gives
The factorial is invertible modulo . Cancelling it and applying the Euler criterion proves the lemma. Counting signs can thus replace a potentially large modular exponentiation.
Use the square-root encryption convention called the Rabin-Williams scheme in the Cambridge course notes. Choose distinct large primes , keep them secret, and publish . A message block is encrypted as
Usually require ; otherwise the message itself reveals a factor. For a quadratic residue modulo , Euler criterion gives , so is a square root. Compute both signs modulo each prime, then combine the four sign choices by the Chinese remainder theorem. For a unit ciphertext there are four roots modulo . Message redundancy identifies the intended root; squaring alone does not identify it uniquely.
To reduce integer factorization to recovery of square roots, choose uniformly from , compute , and ask the alleged decoder for any root of . Conditional on , the secret is uniform among its four roots, even if the decoder deterministically chooses . With probability , . Then the signs agree modulo one prime and disagree modulo the other. Since
the greatest common divisor factors . Independent trials require an expected two successful oracle calls. If a trial's chosen is not a unit, already factors . This establishes the computational equivalence between factorization and inversion of the squaring map; it does not claim that learning any partial information about a formatted message is equivalent to full inversion.
For coin flipping by telephone, Alice publishes with its factorization secret. Bob chooses uniformly a unit with and sends . Alice computes the two roots in this half interval, selects a binary digit in which they differ, and announces a guess for that digit of Bob's . Bob reveals ; Alice verifies its range and square, and their common bit records whether her guess was correct. Alice then reveals , so Bob verifies the primes, product, and differing digit.
Conditional on , Bob's original root is equally likely to be or , so Alice's guess succeeds with probability . Bob cannot change his answer to the other half-interval root without finding a nontrivial second square root, which would factor by the argument above. Thus, assuming factorization is hard and the prescribed sampling and completed exchange are followed,
The revealed factors make the completed transcript checkable. The protocol does not prevent a party from aborting communication.
For , the displayed integral equation has nonzero elliptic-curve discriminant modulo , so it has good reduction. Let be the Legendre symbol, with . Counting the two, one, or zero possible ordinates over each gives
If , then and the terms for and cancel. The term at zero vanishes. Thus the count is .
For the converse, suppose , and put . The Euler criterion and the sum of powers over a finite field show that the Trace of Frobenius satisfies
Indeed, among the positive exponents in this polynomial, of degree , only has a nonzero sum over , and that sum is . Since , the coefficient formula for trace of Frobenius modulo p yields
Neither nor the binomial coefficient vanishes modulo . Hence , proving the point-count criterion for y squared equals x cubed plus k x:
We use the following formal logarithm fact, also useful for the next part. For a formal group law over , its logarithm has coefficients with , obtained by integrating its integral invariant differential. If is odd and , every term of degree has valuation strictly greater than , since . Thus the logarithm converges and is nonzero at . Its homomorphism into the additive characteristic-zero group proves torsion-freeness of the formal group over Qp for odd p. Consequently reduction injects the entire rational torsion subgroup at any odd prime of good reduction, including its -primary torsion. In particular the torsion subgroup is finite, and its order divides at every good .
By the Dirichlet theorem on primes in arithmetic progressions, choose a good prime . Then , bounding the two-primary part by four. For any odd prime dividing the torsion order, the Chinese remainder theorem and the Dirichlet theorem on primes in arithmetic progressions give a good prime with and , avoiding the finitely many primes dividing . But then , a contradiction. Therefore
The order four does occur. For , the elliptic-curve addition formula gives , so has order four. More precisely, the only nonzero rational 2-torsion point when is , so order four means a cyclic group with a rational half of this point. The duplication formula is
Such a half must have . Writing , positivity of forces . Then , so is a rational square, equivalently for an integer . Conversely is a half of when . The rational torsion on y squared equals x cubed plus positive k x is therefore cyclic of order four exactly for these , and otherwise cyclic of order two.
For an odd prime , the Legendre symbol is
Euler criterion states that
The Gauss lemma says that, for , if of the least positive residues of
lie in , then
To prove it, replace every residue above by its negative. The resulting absolute residues are distinct up to sign and therefore form a permutation of
Multiplying the congruences gives
Cancel the nonzero factorial and apply Euler's criterion.
For , the residues are . The number above is
whose parity gives the second supplementary law for quadratic reciprocity
Consequently, for odd primes,
The congruence is also soluble for .
For an odd prime , the Legendre symbol is
Euler criterion states that
If , both sides vanish. Otherwise choose a primitive root and write . Since ,
The power is a square exactly when is even, proving the criterion. Taking gives the first supplementary law for quadratic reciprocity
Because and commute, the matrix binomial theorem gives
For prime , every intermediate coefficient is divisible by , proving the prime-power binomial congruence for a matrix
For
one has and . If , then
so . If , then and
so .
By Euler criterion, . In either case the preceding congruence gives . Since has the same parity as for , this is the second supplementary law for quadratic reciprocity
By Euler criterion,
Choose a primitive root . For any integer not divisible by ,
For , the exponent satisfies . Therefore
Together with part (i), this is the weighted complete Legendre-symbol sum.
Write . If , the claimed identity has both sides zero. Otherwise let . Applying the Euler criterion gives
Both sides are in , which are distinct residue classes because is odd. Therefore the modular congruence is an equality:
The Euler criterion states that for ,
The same modular congruence holds for , with both sides zero.
Again set . The Euler criterion applied to gives , as an equality of signs. If , the exponent is even and the result is ; if , it is odd and the result is . Hence
Euler criterion states that
When , the power is congruent to or , according as is or is not a quadratic residue.
By multiplicativity of the Legendre symbol and Euler criterion,
Combining this with part (iv) yields
The Euler criterion states that for an odd prime number and ,
The same modular congruence remains true when , with both sides zero.
If divides or , both sides of the claimed multiplicativity identity are zero. Otherwise the Euler criterion gives
Each side is or . Since is odd, these two integers represent different residue classes. Hence the modular congruence gives equality: