As an example, it can help us with factoring large integers \(n\); Gauss did this. Describing the process itself is just a little too long to allow its inclusion, 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. Which might be a lot of conditions.

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.

Another application is that it can help us check primality.

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

Just like with Mersenne numbers (Subsection 12.1.3), for which the Lucas-Lehmer test can check for primality (remember GIMPS?), there is a test called Pépin's test which can check for primality of Fermat numbers. (Pépin 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 the relevant member of the excellent Prime Pages for more information.

Here is the test in Sage:

You can already see from this code that it is checking Euler's criterion mod \((F_n)\), and looking for a negative answer. Why would this test primality? Let's formally state and prove the criterion.

There is even more! As one example, quadratic reciprocity (or at least the Legendre symbol) helps us solve Mordell equations (e.g. Subsection 15.3.2). 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 to the test for \(F_n\)'s primality in Fact 17.5.1. A careful look at the proof shows that \(3\) is a primitive root for \(F_n\), if \(F_n\) is prime. Thus, if we had infinitely many Fermat primes (and not just five of them), we'd have an integer which is a primitive root of infinitely many primes.

Such would provide a proof of at least one explicit case for the following long-standing question.

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!

  That is, there are at most two nonsquare integers which are not a primitive root for infinitely many primes, yet we do not have a single specific integer which we can prove that for.

There is some historical connection as well. Gauss spent some time investigating the patterns of repetitions in simple decimal expansions of fractions, like \(\frac{1}{3}=.333\ldots \) or \(\frac{2}{7}=.285714285714\ldots \). It turns out that this is directly connected to whether \(10\) is a primitive root for a given prime (see Exercise 17.7.19). Likewise, the ‘Great Theorem’ in William Dunham's book Journey Through Genius where Euler found that \(F_5=4294967297\) was composite (recall Subsection 12.1.1) would have been helped along quite a bit, as Euler's proof looked directly at factors of powers of 2 (plus one) and their possible form, not powers of 3.

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

So if there were infinitely many such Germain primes, we would also have an explicit example of Artin's conjecture … but, so far, no such luck.

The largest currently known (as of this writing, discovered in early 2016) Germain prime, due to James Scott Brown, is \begin{equation*}2618163402417\cdot 2^{1290000} - 1\end{equation*} which is a number with close to four hundred thousand digits. (The previous record had about half as many, so this is a huge advance.)