Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

June 4, 2007

Quadratic Reciprocity

Posted by John Baez

Next week is the last week of class here at UC Riverside! Yay!

I’m almost done teaching an undergraduate course on number theory, where the big final blaze of fireworks consists of proving Quadratic Reciprocity. I’m following a standard proof due to Eisenstein, outlined here:

But, despite its pompous title, this outline doesn’t explain much. I don’t understand what makes Eisenstein’s proof tick, even after reading this play about it:

Maybe someone could explain what really makes this proof work?

In case you’re not in the know, Quadratic Reciprocity lets you tell if pp is the square of some integer mod qq, assuming you know if qq is the square of some integer mod pp. Here pp and qq are two odd primes.

So, it relates these two questions:

(A): Is pp is a square mod qq?

(B): Is qq is a square mod pp?

It asserts that

  • If both pp and qq equal 3 mod 4, then questions (A) and (B) have opposite answers.
  • Otherwise, questions (A) and (B) have the same answer.

People usually make this fact even prettier with a gadget called the Legendre symbol. This is written

(pq) \left( \frac{p}{q} \right)

and it equals 11 if pp is a square mod qq, and 1-1 otherwise. In terms of this trick, Quadratic Reciprocity says:

(pq)(qp)=(1) (p12)(q12) \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\left(\frac{p-1}{2}\right) \left( \frac{q-1}{2}\right)}

It’s a fair amount of work to demonstrate this, at least using elementary methods. So, people have given many proofs. Gauss came up with 8. As of today, at least 227 proofs are known! They’re all listed here:

I would like to understand how the elementry proof in my outline connects to more conceptual proofs, like those using algebraic number theory, which hint at generalizations such as Artin Reciprocity.

Posted at June 4, 2007 8:51 PM UTC

TrackBack URL for this Entry:

22 Comments & 1 Trackback

Re: Quadratic Reciprocity

John, I didn’t attempt to work through the details of the proof you sketched for your course, but have you looked at the postscript in John H. Conway’s The Sensual (Quadratic) Form? There seems to some sort of family resemblance between the elegant proof of quadratic reciprocity given by Conway and the Eisenstein proof, but you may find the Conway proof much more illuminating.

He starts off very sensibly by giving Zolotarev’s definition of the Jacobi symbol: If aa is prime to nn, the symbol (a/n)(a/n) is defined to be the sign of the permutation of multiplying by aa on the set \mathbb{Z} mod nn. He comments, “This definition leads to an extremely simple proof of the quadratic reciprocity theorem. It is remarkable that this proof does not use either the notion of prime number, or even that of square number. We shall however use he fact that the sign of a permutation is multiplicative.”

Of course, one has to relate the Zolotarev definition of (a/p)(a/p) to the usual definition, but that’s not hard (just uses the fact that the multiplicative group of \mathbb{Z} mod pp is cyclic).

Posted by: Todd Trimble on June 5, 2007 12:23 AM | Permalink | Reply to this

Re: Quadratic Reciprocity

Although that proof has a special place in my heart (due to its connections with the Ross program) it is neither the easiest nor the most informative.

Although the 3rd proof may be the easiest of the classical proofs, there is a much easier and cleaner argument due to Rousseau, (“On the quadratic reciprocity law.” J. Austral. Math. Soc. Ser. A 51 (1991), no. 3, 423–425. MR1125443.)

His argument is sumarized in the review. However, with a little bit of playing around you should be able to reconstruct the argument from the following hint. Consider the units in Z/pqZ = Z/p x Z/q (by CRT). We are going to take the product of half of them, by which i mean for every pair (x, -x) pick one of them, and multiply those together. The final answer is well-defined up to an overall sign. There are three obvious choices:
a) 1…p-1/2 mod p and anything mod q
b) anything mod p and 1…q-1/2 mod q
c) 1 … pq-1/2 mod pq.
Compare the three products (thinking of them as living in Z/p x Z/q) and out pops QR.

On the other hand, I think these elementary arguments are all rather uninformative because they don’t illustrate how cyclotomic integers come in (which is the key for all the algebraic number theory proofs). Here’s a simple example of how those proofs work. We want to know when -3 is a square modulo p. Well, there’s a simple linear formula relating the square root of -3 to the cube root of 1. So all we need to know is when there is a nontrivial cube root of 1. But that’s clearly when p = 1 mod 3. This is the first example of QR.

Posted by: Noah Snyder on June 5, 2007 2:24 AM | Permalink | Reply to this

Re: Quadratic Reciprocity

I see how to use that logic to show when -3 has a square root, but how did you use quadratic reciprocity? I see how to use quad rep when the prime is 1 mod 4 since -1 has a square root, but that only gets me that the prime is 1 mod 12. How do you get the case p = 3 mod 4 using quad rep?

Posted by: Cary Martin on February 29, 2008 3:40 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

Hi, here some articles putting it into an interesting geometrical context:

Hill, Richard
A geometric proof of a reciprocity law.
Nagoya Math. J. 137 (1995), 77–144.
‘… the author uses singular homology groups and homotopy theory’

Grant, David
Geometric proofs of reciprocity laws.
J. Reine Angew. Math. 586 (2005), 91–124.
‘This beautiful and self-contained paper contributes to our understanding of the relationship between power reciprocity laws and the geometry of abelian varieties.’

Ash, Avner; Gross, Robert
Generalized non-abelian reciprocity laws: a context for Wiles’ proof.
Bull. London Math. Soc. 32 (2000), no. 4, 385–397.

Not in the library here, but its title sounds very interesting:
Kubota, Tomio
A foundation of class field theory applying properties of spatial figures
Sugaku Expositions 8 (1995), no. 1, 1–16.

Posted by: Thomas Riepe on June 5, 2007 4:03 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

This is basically just a fleshing out of what Noah said above. Let q be an integer which is 1 modulo 4. The essence of quadratic reciprocity is that (q on p) is periodic with period q as a function of p. The fact that this periodic function has the specific form given by quadratic reciprocity is not so hard given that it is periodic; one first shows that (q on p) is a character of (Z/q)^* (Conway does this very nicely, IIRC) and then notes that there aren’t a lot of options.

So, how to prove periodicity? Both the elementary proof you are considering and the cyclotomic proofs Noah mentions start in the same place with Euler’s criterion – (q on p)=q^{(p-1)/2} modulo p. I like to understand this through Galois theory of finite fields. Working in K, an algebraic extension of F pF_p where x 2qx^2-q splits, we know that (q) p\sqrt(q)^p is a Galois conjugate of (q)\sqrt(q) and is hence ±(q)\pm \sqrt(q). Moreover, q is a square in F pF_p if and only if (q)\sqrt(q) is fixed by Gal(K/F p)Gal(K/F_p), which is generated by the Frobenius, we see that (q on p) is (q) p/(q)\sqrt(q)^p/\sqrt(q), which can be rewritten as q (p1)/2q^{(p-1)/2}.

In the elementary proof, q (p1)/2q^{(p-1)/2} is rewritten as (q*1)(q*2)(q*(p1)/2)/(1*2*(p1)/2)(q*1)(q*2) \cdots (q*(p-1)/2)/(1*2*\cdots (p-1)/2). One looks at each of the terms in the numerator to see it lies in {1,2,(p-1)/2}+p*Z or whether it lies in {-1,-2,…,-(p-1)/2}+p*Z. I’ll do the example q=-3. For k=1,2,…,[(p-1)/6], we have q*k{1,2,...,(p1)/2}q*k \in \{-1,-2,...,-(p-1)/2\} and for k=[(p+1)/3], …, (p-1)/2 we have q*k{1,2,...,(p1)/2}pq*k \in \{-1,-2,...,-(p-1)/2\}-p. So (up to boundary errors on my part) (q on p) depends only on the parity of [(p1)/2][(p+1)/3]+[(p1)/6][(p-1)/2]-[(p+1)/3]+[(p-1)/6]. It is fairly clear that this is periodic modulo 1212 and, if I didn’t screw up, the actual period is 33. In general, you should be able to convince yourself that the (q on p) has period 4q and, if you are careful, get rid of the 4.

In the cyclotomic proofs, one tries to lift the Frobenius map to a Galois autmorphism in some characteristic zero setting. Specifically, one shows (using that q=1 mod 4) that (q)\sqrt(q) is contained in L q:=Q[e 2πi/q]L_q := Q[e^{2 \pi i/q}]. Writing ζ=e 2πi/q\zeta=e^{2 \pi i/q}, L qL_q has a Galois automorphism σ p=ζζ p\sigma_p=\zeta \to \zeta^p which clearly only depends on what pp is modulo qq. One then considers the ring of integers O inside L qL_q. There is a quotient of O which is a field KK as in our second paragraph and such that σ p\sigma_p descends to the Frobenius on this quotient. Since σ p\sigma_p only depended on p modulo q, we have the periodicity again.

Posted by: David Speyer on June 5, 2007 8:25 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

Just an advertisement – I have a post on the secret blogging seminar where I explain what the finite field version of QR says, and how to think about it geometrically.

Posted by: David Speyer on June 17, 2007 4:37 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

Cool — thanks!

I’m glad you’ve joined the world of math group blogging.

I wish you could summarize your explanation of quadratic reciprocity in one sentence. I’m missing the forest — there are too many trees. I’d like to hear just the moral essence, disregarding all technical details. Something like “??? is periodic because some deck transformation of ??? satisfies ???”

Or, it’s possible that what’s important in your outlook is not quadratic reciprocity but something else, of which quadratic reciprocity is just a spinoff. Then the moral essence of this ‘something else’ is what I’d like to hear.

Posted by: John Baez on June 17, 2007 9:30 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

I was going to let Speyer respond to this, but since it’s been a while, here’s my take (not quite one sentence, admittedly). Let p be odd, and take q to be 1 (mod 4) for simplicity, and let p be odd.

The elements Frobp in the Galois group of Q(zetaq)/Q are certainly periodic in p (with period q). But Frobp(sqrt(q)) is +/-sqrt(q), and the sign is precisely the Legendre symbol (q/p), because if we reduce mod p then Frobp fixes sqrt(q) exactly when this square root lives in the finite field of order p. Therefore (q/p) is periodic in p.

Of course, to make this go through, one has to do a calculation to show that sqrt(q) lives in Q(zetaq). The extra complication in the case when q is 3 (mod 4) comes from the fact that one has to use sqrt(-q) instead.

In short, the periodicity comes from the way that the Frobp’s are distributed among the elements of Gal(Q(zetaq)/Q), and the precise form of the law (and the connection with the Legendre symbol) comes from an explicit understanding of the fixed field of the quadratic character of this group.

Posted by: David Savitt on June 29, 2007 1:22 AM | Permalink | Reply to this

Re: Quadratic Reciprocity


Here is a sketch of the proof of quadratic reciprocity given in algebraic number theory books nowadays (I think essentially that given by David Speyer). In his lectures on algebraic number theory Hermann Weyl says “There certainly exist more elementary proofs of the reciprocity law, but hardly one that is less artificial and goes straight to the root of the phenomenon.”

Let p and q be primes and let
q* be defined by
q* = q (for q = 1 (mod 4)
q* = -q (for q = 3 (mod 4)

Let w be a primitive q’th root of unity.

Then the following statements are true:
1) 1 = (q*/p) p splits in Q(sqrt(q*))
(This is easy)

2) p splits in Q(sqrt(q*)) p splits into an even number of ideals in Q(w)

(This step requires Galois theory. The basic point is that Q(sqrt(q*)) is a subfield of Q(w) and that if p splits in Q(sqrt(q*)) then each of the two prime factors of p splits into an equal number of factors when we move to Q(w) and that conversely if p splits into an even number of factors in Q(w) then they can be split into two groups that separately multiply to two factors in Q(sqrt(q*)).

3)The number of ideals in Q(w) that p splits into is given by
r = (q - 1)/f

where f is the minimum positive integer such that

p^f = 1 (mod q)

(Deriving this formula requires algebraic number theory)

Once we have these three facts we see that (q*/p) = 1 iff r is even but by our formula this is so iff f | (q - 1)/2)

this is so iff

p^[(q - 1)/2] = 1 (mod q)

which is (by Euler criterion) the same as (p/q) = 1.


I hope the above was sufficiently concise and not too technical. I don’t know whether or not there’s a known relationship between this proof and Eisenstein’s lattice point counting proof.

Posted by: Jonah Sinick on June 18, 2007 7:54 AM | Permalink | Reply to this

Re: Quadratic Reciprocity

i know there is like about 227 proofs of the law of quadratic reciprocity,
but i was wondering can anyone tell me the trigonometric proof for the law of quadratic reciprocity?
i cant seems to find any website or online resources for that.
many many thanks.

Posted by: Adam Ho on December 2, 2007 11:37 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

Dear John, One can perhaps explain the elementary proofs of quadratic reciprocity conceptually by using the following result.

Proposition. If a cyclic group C of odd order acts freely on a finite set X, and if f is a permutation of X commuting with the action of C, then the sign of f is the same as the sign of the induced permutation on the quotient set X/C.

In particular, let p and q be distinct odd primes, let X be the set of integers between -pq/2 and pq/2, let C be a cyclic group of order q acting on X so that its generator sends k to k+p mod pq, and let f be the permutation of X such that

f(i+pj)=qi+pj mod pq

for i between -p/2 and p/2 and for j between -q/2 and q/2. The induced permutation on X/C is essentially multiplication by q on the ring of integers modulo p, so its sign is the Legendre symbol (q/p) as interpreted by Zolotarev. By the Proposition, (q/p) is also the sign of f.

Similarly (p/q) is the sign of the permutation g of X given by

g(qi+j)=qi+pj mod pq

for i between -p/2 and p/2 and for j between -q/2 and q/2.

The Legendre symbols (q/p) and (p/q) have now been interpreted in a conceptual way as the signs of two permutations of the same set X, so their ratio can be naturally computed as the sign of the composite c=hf, where h is the inverse of g; thus


for i between -p/2 and p/2 and for j between -q/2 and q/2. One has c(-k) = -c(k) for all k in X, so the sign of c is -1 raised to the power m, where m is the number of positive integers k in X such that c(k) is negative. It turns out that

m = (p-1)(q-1)/4,

so this gives one quadratic reciprocity.

Posted by: Richard Steiner on January 18, 2008 12:41 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

Very nice!!! I may use this Zolotarev approach, also mentioned by Todd Trimble, the next time I teach the undergraduate course on number theory.

As Todd points out, Conway notes this proof uses “the fact that the sign of a permutation is multiplicative”:

sign(στ)=sign(σ)sign(τ).sign(\sigma \tau) = sign(\sigma) sign(\tau).

This is a very fundamental fact, but a self-contained proof from scratch is surprisingly annoying. When I last checked, the tricky part was showing that the sign was well-defined: a product of an even number of transpositions can’t also be a product of an odd number of transpositions.

I know brutal direct arguments for this. A lot of people suggest getting around this by defining the sign of a permutation to be the determinant of the corresponding matrix. However, to be fully honest, one must then check one has a definition of the determinant that doesn’t secretly rely on the concept of the sign of a permutation! If one’s not careful, one is led into an extensive digression on exterior algebra.

It may be wiser to hide these issues from undergrads… I don’t remember anyone ever explaining to me why the sign of a permutation was well-defined!

Posted by: John Baez on January 18, 2008 6:35 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

I can remember trying to prove it as an undergraduate. It was an awful struggle, and I don’t think I was ever entirely happy with my proof.

Posted by: Tim Silverman on January 18, 2008 9:37 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

One common way is to define the sign of a permutation of {1,,n}\{1,\dots,n\} by how it acts on the discriminant (x ix j),\prod(x_i-x_j), where the product runs over pairs where ii is less than jj (couldn’t get that to display right). So the sign is positive if and only if it moves an even number of pairs (i,j)(i,j) from above the diagonal to below it. Then you don’t have to prove it’s well-defined because you actually defined it! It’s also essentially obviously a homomorphism. On the other hand, you do have to prove it’s independent of the ordering you chose on the set. It’s kind of obvious once you know it’s a homomorphism to an abelian group, but it would be nice to actually define it in a choice-free way.

Another way is to define the sign in terms of cycles: it’s positive if and only if it has an odd number of even length cycles. Then since you didn’t pick an ordering and you did actually define it, it’s well-defined and independent of any choice of ordering, but then you have to show it’s a homomorphism. It seems that no matter which way you do it, you have to make a choice or prove something. Could it be possible to make that statement precise?

Posted by: James on January 18, 2008 11:18 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

I asked above whether it could be possible to make a precise statement saying that you have to do some work or make some choices to construct the sign homomorphism Aut(X){±1}\mathrm{Aut}(X)\to\{\pm 1\}, where XX is a finite set.

One general way of convincing yourself that you have to do some work is by showing that in a similar but more general situation, the result you want is false. For example, any finite-dimensional vector space is isomorphic to its dual. One explanation of why this requires some work is that it’s false for vector bundles. So any proof will have to involve something particular.

So here’s a vague question: is there some category, analogous to the category of finite sets, in which automorphism groups of objects don’t have a sign function?

You might try the category of “locally finite” objects in a (Grothendieck?) topos. But this doesn’t work: because the sign function is natural (though not trivially), the local sign functions patch together to form a global one. This also makes clear a way in which my example above with duals is less than ideal. In that case, the construction really does depend on choices, while the sign function ultimately doesn’t.

Alternatively, try to find a sign map in very weak categories. Having both hands tied behind your back might force you to be cleverer.

I’m not convinced this question isn’t silly, but I will be if someone comes up with a good answer!

Posted by: James on January 22, 2008 9:14 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

James wrote:

One common way is to define the sign of a permutation of {1,,n}\{1,\dots,n\} by how it acts on the discriminant i<j(x ix j)\prod_{i \lt j} (x_i - x_j).


Paul Pedersen explained that approach in the sci.math thread I referred to. It’s slick — but ain’t it sort of weird to use polynomials to construct this very fundamental homomorphism from S nS_n to /2\mathbb{Z}/2?

I know, I sound like I’m complaining — but it’s actually just fun to ponder this issue.

The problem you mention, about the independence from the choice of ordering, is also interesting.

Another way is to define the sign in terms of cycles: it’s positive if and only if it has an odd number of even length cycles. Then since you didn’t pick an ordering and you did actually define it, it’s well-defined and independent of any choice of ordering, but then you have to show it’s a homomorphism.

Right. Another friend of ours named James, who used to write in ALL CAPITALS, posted this proof on that same sci.math thread. He made it pretty snappy.

i is less than j (couldn’t get that to display right).

Alas, the ‘less than’ sign also plays a fundamental role in HTML, so to get a <\lt using TeX around here you have to type $\lt$.

(Extra credit for figuring out how I just typed that sentence!)

Posted by: John Baez on January 19, 2008 1:29 AM | Permalink | Reply to this

Re: Quadratic Reciprocity

You can also use &lt;

And similarly &gt; for the “greater than” sign.

Posted by: Tim Silverman on January 22, 2008 6:37 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

Here’s a sort-of-proof that the sign of a permutation is well-defined. I learned it in my first ever group theory course. The lecturer called it the “unbraiding theorem”…

As usual, it’s enough to prove that the identity can only be written as the composite of an even number of transpositions. So, suppose we’ve expressed the identity as the composite of some transpositions. Draw it in a manner like this — and check the comment afterwards before you start frowning —

| | | | | |
 \| |/  | |
  \ /   | |
  |X|   | |
  / \   | |
 /| |\  | |
| | | | | |
| | |  \|/
| | |   *
| | |  /|\
| | | | | |

OK, so I’ve drawn the composite of some (two) transpositions, and I know they don’t compose to the identity, but they’re meant to… this kind of drawing’s hard work. Anyway, I hope you get the idea.

We’re going to count the number of crossings, mod 2, in two ways.

First, each transposition contributes exactly one crossing, mod 2. Suppose we’re transposing the iith and jjth wires. To move the iith wire into the jjth position, it needs to cross the rr wires in between (where r=|ji|1r = |j - i| - 1, but that doesn’t matter). Similarly, to move the jjth wire into the iith position, it needs to cross the rr wires in between. Also, the iith and jjth wires need to cross each other. So the transposition contributes 2r+1=1(mod2)2r + 1 = 1\, (mod\, 2) crossings. So mod 2, the total number of crossings is the number of transpositions.

On the other hand, take any ii and jj and follow the iith and jjth wires as they wiggle their way from top to bottom. Since (say) the iith wire starts and finishes to the left of the jjth wire, they must cross an even number of times. So the total number of crossings is even.

Putting the two together, the number of transpositions is even.

Posted by: Tom Leinster on January 22, 2008 7:57 PM | Permalink | Reply to this

Re: Quadratic Reciprocity

The proof of quadratic reciprocity that I gave on 18 January 2008 I have subsequently found in G. Rousseau, On the Jacobi symbol, Journal of Number Theory 48 (1994) no. 1, 109-111. This paper actually proves quadratic reciprocity for the Jacobi symbol (a/m), defined for a positive odd integer m and an integer a coprime to m as the sign of the permutation of the congruence classes modulo m induced by multiplication by a.

A similar method shows that the Jacobi symbol (a/m) defined in this way is multiplicative in m. Let m and n be positive odd integers and let a be an integer coprime to m and n. Let f and g be the permutations of the integers between -mn/2 and mn/2 given by
f(i+mj) = ai+mj mod mn,
g(i+mj) = i+amj mod mn
for i between -m/2 and m/2 and for j between -n/2 and n/2; then the signs of fg, f and g are (a/mn), (a/m) and (a/n), so (a/mn) = (a/m)(a/n).

As a consequence, if m has prime factorisation m = p1…pk then the Jacobi symbol (a/m) defined as the sign of a permutation is the product of the Legendre symbols (a/p1), …, (a/pk), so it agrees with the Jacobi symbol (a/m) as originally defined.

Posted by: Richard Steiner on January 30, 2008 11:40 AM | Permalink | Reply to this

Re: Quadratic Reciprocity

Here´s one way to implement zolotarev´s idea. Given a finite set X let perm(X) be the group of permutations of X. it´s easy to see that swaps (i.e swap two elements a and b) generate Perm(X). Define a sign to be a function S on Perm(X) with values in +1 or -1 such that S(fog)=S(f)S(g) and S(swap) = -1. Since swaps generate perm(X) there can be at most one sign. To show existence, identify X anyhow with a subset of a field not of characteristic 2 (i.e. +1 not = -1) and define S(f) to be Product over all unordered pairs {x,y} of f(x)-f(y)/x-y.
This is well-defined since f(y)-f(x)/y-x = f(x)-f(y)/x-y. since any f permutes the {x,y} S(fog) = S(f)S(g) is easy. Also if f swaps a and b then the pairs are {a,b},{a,x}, {b,x} and {x,y} so S(f) = a-b/b-a.

Now Zolotarev defines (a/q) (q odd prime) to be the sign of multiplication by a mod q. Thus (ab/q)=(a/q)(b/q). Taking X = field of q elements, the sign formula gives us (mod q) that (a/q)=Product(ax-ay)/(x-y)=a^q(q-1)/2 = a^(q-1)/2 by the easy binomial theorem (a^q=a mod q). It follows easily that a is square mod q iff (a/q) = +1. Let p be another odd prime. Adjoin a pth root of unity to Fq (field of q elements) by taking Fq[x] modulo irreducible factor of x^p-1/x-1. This gives a field containing Fq and R such that R^p=1 but R=not 1. So we have p pth roots of 1 including of course 1. We identify Fp with the pth roots by x –> R^x . Then (q/p)=product of S^q-T^q/S-T over all unordered pairs {S,T} of pth roots of 1. By the easy binomial theorem this (product of S-T)^(q-1) = D^(q-1)/2 where D is product (S-T)^2. But D is easily seen to be (-1)^p(p-1)/2 times product (S-T) over all ordered pairs (S,T) which is easily seen to be p^p. Thus (q/p) = (-1)^(p-1)(q-1)/4 times (p^p)^(q-1)/2 (mod q of course) = (-1)^etc times (p/q)^p = (-1)^etc times (p/q) since (p/q) is =1 or -1 and p is odd. Thus (q/p) = (-1)^etc (p/q) mod q which implies equality since both sides are +1 or -1.

Posted by: derek on March 5, 2008 10:32 PM | Permalink | Reply to this
Read the post Lautman on Reciprocity
Weblog: The n-Category Café
Excerpt: Lautman on reciprocity
Tracked: August 14, 2008 3:59 PM

Re: Quadratic Reciprocity

Excuse a pure amateur who is trying to understand QR for butting in, but isn’t the following statement, which I have highlighted from the opening page of this discussion, incorrect?

I cannot paste it. It says if p and q are both 4n+3 type primes, then they have opposite answers, in other words are not mutually quadratic residues in each other’s set.

But 19 and 23 when squared are both equal to 16 mod the other one.

Please explain where I have gone wrong, or repair your site.


Jesse Baird

Posted by: jesse baird on September 28, 2015 8:13 AM | Permalink | Reply to this

Re: Quadratic Reciprocity

You need to ask yourself if 1919 considered modulo 2323 and 2323 modulo 1919 are mutually squares or not – not if their squares are.

2323 is congruent to 44 modulo 1919, which is 2 22^2, so that’s a square.

Is there anything that whose square is congruent to 1919 modulo 2323?

Posted by: Todd Trimble on September 28, 2015 9:33 AM | Permalink | Reply to this

Post a New Comment