As an example, it can help us with factoring large integers \(n\); Gauss did this. The process itself is just a little too long to make it worth including here, but it's important to get the flavor.

The essential idea is that if \(a\) is a QR of \(n\), then \(a\) is a QR of any prime \(p\mid n\). So since QRs often have congruence conditions associated with them, \(n\) must obey all of the congruence conditions for \(\left(\frac{a}{p}\right)\) for all the \(p\) which divide it.

Then we can use a variant on the Fermat factoring method to check for possible \(a\) for which a prime divisor \(p\) of \(n\) definitely is or definitely is not a QR (which quadratic reciprocity can help with), and then one can compute Legendre/Jacobi symbols of possible \(p\mid n\) to reduce to just having to check a very few bigger possible prime factors.

Amazingly, we are still not done with the applications of this theorem! It can help us check primality.

One specific place where it is helpful (though not the only one!) is with the so-called Fermat numbers. Recall that Euler blasted the following conjecture of Fermat's out of the water: \[F_n=2^{2^n}+1\text{ is always prime for }n\geq 0\, .\] But what about bigger ones - surely they are inaccessible to the usual factoring techniques?

Just like with Mersenne numbers, for which the Lucas-Lehmer test can check for primality (remember GIMPS?), there is a test called Pepin's test which can check for primality of Fermat numbers. (Pepin did this work in the late 1800s.) It turns out that no bigger Fermat numbers have turned out to be prime (all the way through \(n=31\)); see here, part of the excellent Prime Pages, for more information.

Here is the test in Sage:

Or, you can write it as: \[F_n=2^{2^n}+1\text{ is prime exactly when }3^{2^{2^n-1}}\equiv -1\text{ mod }2^{2^n}+1\, .\] This is really Euler's criterion for checking whether 3 is a quadratic residue mod \(F_n\), and getting a negative answer. (Notice that it is not very helpful for \(n=0\), which is why we skip that.)

Why would this check for primality? Let's see a proof:

• First, let's assume \(F_n\) is prime.
  • Since \(F_n\) is one more than a multiple of four, it is clearly \[F_n\equiv 1, 5,\text{ or }9\text{ mod }(12)\; .\]
  • If \(F_n\equiv 1\text{ mod }(12)\), then \(3\mid 2^{2^n}=F_n-1\), which cannot be true.
  • If \(F_n\equiv 9\text{ mod }(12)\), then \(F_n\) is a number greater than three which is divisible by three - but it's prime, so that's not possible.
  • So \(F_n\equiv 5\text{ mod }(12).\) That means \(3\notin Q_p\), based on our work earlier today.
  • So if \(F_n\) is prime, then Euler's criterion gives the result.
• Now let's assume that Euler's criterion gives this answer of \(-1\).
  • Then square both sides to get \[3^{F_n-1}\equiv 1\text{ mod }(p)\] for all primes \(p\) dividing \(F_n\).
  • Since \(F_n-1=2^{2^n}\), that means 3 has order (in \(U_p\)) some power of \(2\).
  • But 3 can't have order \(2^{2^n-1}\) (or less), because it isn't the identity when taken to that power.
  • So it must have order \(2^{2^n}\).
  • But the only way 3 can have that big of an order is if \(p\) is at least \(2^{2^n}+1\)!
  • So since \(p\mid F_n\), we must have \(p=F_n\)!

There is even more! As one example, quadratic reciprocity (or at least the Legendre symbol) helps us solve Mordell equations. The easiest cases use \(\left(\frac{2}{p}\right)\) and multiplicativity. But more advanced ones need to compute more complicated square roots. Here are two examples, without proof; there are many others.

• The equation \(x^3=y^2+16\) has no integer solutions. (Uses \(\left(\frac{-8}{p}\right)\).)
• The equation \(x^3=y^2-46\) has no integer solutions. (Uses \(\left(\frac{-18}{p}\right)\).)

Let's return now to the proof of \(F_n\)'s primality above. Some books point out that the proof itself shows that \(3\) is a primitive root for \(F_n\) if it's prime. So if we had infinitely many Fermat primes (and not just five of them), we'd have a proof of at least one explicit case for Artin's conjecture:

Every nonsquare integer except \(-1\) is a primitive root for infinitely many primes.

This conjecture is interesting for several reasons.

• Although it is mostly believed to be true, currently there are no integers known to be a primitive root for infinitely primes.
• Weirder, it is known that at least one of 3, 5, and 7 does in fact satisfy this (that is, at least one of 3, 5, or 7 is a primitive root for infinitely many primes) but we don't know which one!
• Weirdest, it has been proved that there are at most two exceptions to this conjecture, yet we also know of no integers which do not satisfy it!

So if only Euler had lived another 100 years or so, he wouldn't have needed to do the Great Theorem in William Dunham's book Journey Through Genius where he found that 4294967297 was composite...

Or we can use these ideas to find another possible way to attack Artin's Conjecture. It's not directly related to the reciprocity per se, but definitely connects all our theoretical ideas of the last several sections.

We put this in the form of several steps.

• If \(q\) and \(p=2q+1\) are both odd primes, then every residue for which primitive root makes sense (i.e. not \(a=-1\) or \(a=0\)) is either a primitive root or a QR. (Requires proof, see below.)
• Such a prime \(p\) must be of the form \(p\equiv 3\text{ mod }(4)\), because \(q=2k+1\) so that \[p=2(2k+1)+1=4k+3\; .\]
• Not only are all residues either a primitive root or a QR, but \(a\) is one of these things precisely when \(p-a\) is the other kind. (Requires proof, see below.)
• We know that \[1^2,2^2,3^2,\ldots,q^2\] are all different modulo \(p\), and of course all of these are QRs (and so not primitive roots). (Requires proof, see below.)
• That means that \(p-k^2\), for \(2\leq k\leq q\), is a primitive root.
• So we see that \(p-4\) is a primitive root for any such prime \(p=2q+1\)!

The largest currently known Germain prime, due to Philipp Bliedung, is \[18543637900515\cdot 2^{666667} - 1\] which is a number with over two hundred thousand digits. (The previous record had about eighty thousand, so this is a huge advance.)