How can $\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$

Question

While looking through some of the formulae I came across this formula.$$\left(\dfrac pq\right)\left(\dfrac qp\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$$ What I know is $\left( \dfrac pq\right)\left( \dfrac qp\right)=1$. But I have no idea how the above formula was derived. I just want to know how it is done. Any ideas?

Answer 1

The crucial parts that you're missing are modulo and that $p$ and $q$ are primes. Let's say $p = 5$ and $q = 11$. Is 11 a square modulo 5? Maybe.

Actually yes. Since $11 \equiv 1 \pmod 5$ it should not be too difficult to find a value of $x$ to satisfy $x^2 \equiv 11 \pmod 5$. Obviously 1 will do, since after all $11 \times 0 + 1 = 1$. Much more interestingly, $10^2 \equiv 11 \pmod 5$ and $12^2 \equiv 11 \pmod 5$. In fact there are infinitely many values of $x$ that will do just fine.

What about the other way around? Is 5 a square modulo 11? The squares modulo 11 are 1, 4, 9, 5, ding, ding, ding! So $x = 11k + 4$ gives us "half" the answers.

This searching through squares is fine and good for small primes, but what if you want to know if the two largest known Mersenne primes are squares modulo each other? The answer is that one is and the other is not, but I get ahead of myself. Going through 1, 4, 9, 16, 25, 36, 49, etc., is tedious and error-prone.

If only there was a formula that gave us the answer as a simple yes or no! Or what if the answer was expressed as 1 for yes and $-1$ for no? Let's call this function $L(a, p)$, just to pick letters out of the air. Well, $p$ is a positive odd prime, so you see why we picked that one. $a$ can be any integer.

Then if we do enough searching with squares modulo small primes, we will hopefully find that $$L(a, p) = a^{\frac{p - 1}{2}} \pmod p,$$ and that this is either 1 or $-1$ except when $\gcd(a, p) > 1$, in which case $L(a, p) = 0$.

So, for example, $L(3, 5) = -1$ and $x^2 \equiv 3 \pmod 5$ has no solution in integers. Let's call 3 "$q$" rather than "$a$". Then we see that $L(5, 3) = -1$ and $x^2 \equiv 5 \pmod 3$ has no solution in integers.

It turns out that for two positive odd primes $p$ and $q$, $L(p, q) = L(q, p)$ always, except when both $p$ and $q$ are $-1 \pmod 4$ (or $3 \pmod 4$, if you prefer), in which case $L(p, q) = -L(q, p)$. This means the answer for one of them is yes and the answer for the other is no.

So, for example, $L(3, 7) = -1$ but $L(7, 3) = 1$ and $1^2, 2^2, 4^2, 5^2, 7^2, 8^2, \ldots$ are all squares that are 7 more than a multiple of 3.

This fact of quadratic reciprocity, this "law" if you will, is encapsulated in the almost impenetrable formula $$L(p, q) L(q, p) = (-1)^{\frac{p - 1}{2} \frac{q - 1}{2}}.$$ Of course that's not quite the notation the French mathematician Adrien-Marie Legendre used.

These facts are very useful in algebraic number theory. For instance, $(2 - \sqrt 7)(2 + \sqrt 7) = -3$, but $(a - b \sqrt 3)(a + b \sqrt 3) = \pm 7$ has no solution in integers $a$ and $b$.

To give proofs of these facts would test how long I can make an answer here on MSE. And in any case, I don't recall the proofs exactly. I think it suffices for me to reassure you they can be found in almost any book on elementary number theory and maybe one or two books on algebraic number theory.

Answer 2

I'd just like to mention that $$\left(\dfrac pq\right)\left(\dfrac qp\right) = -1$$ if both $p$ and $q$ are primes of the form $4k + 3$, with $k \geq 0$.

Otherwise $p$ "reciprocates" to $q$ and then either $$\left(\dfrac pq\right)\left(\dfrac qp\right) = 1 \times 1 = 1$$ or $$\left(\dfrac pq\right)\left(\dfrac qp\right) = -1 \times -1 = 1$$ just the same.