Section 17.5 Some Surprising Applications of QR
What else can quadratic reciprocity do? The answer is, a lot. This section collates various interesting applications of QR, as well as some places where being able to efficiently calculate quadratic residues by its means is generally helpful.
Subsection 17.5.1 Factoring, briefly
As an example, it can help us with factoring large integers \(n\text{;}\) Gauss used it. The process itself is a little too long to describe here, but it’s important to get the flavor.
The essential idea is that if \(a\) is a QR of \(n\text{,}\) then \(a\) is a QR of any prime \(p\mid n\text{.}\) QRs often have congruence conditions associated with them, so \(n\) must obey all of the congruence conditions for \(\left(\frac{a}{p}\right)\) for all the \(p\) which divide it. This might be a lot of conditions, which narrows the field considerably.
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 (again, quadratic reciprocity can help), 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.
Subsection 17.5.2 Primality testing
A specific example where quadratic reciprocity is helpful is with the socalled Fermat numbers. Recall (
Subsection 12.1.1) that Euler blasted the following conjecture of Fermat’s out of the water by disproving it for
\(n=5\text{:}\)
\begin{equation*}
F_n=2^{2^n}+1\text{ is always prime for }n\geq 0\text{.}
\end{equation*}
But what about bigger \(F_n\text{;}\) surely they are inaccessible to the usual factoring techniques?
Here is the test implemented naively in Sage:
You can already see from this code that it is checking Euler’s criterion modulo \(F_n\text{,}\) and looking for a negative answer. Why would this test primality? Let’s formally state and prove the criterion.
Fact 17.5.1. Pépin’s Test.
For \(n> 0\text{,}\) \(F_n=2^{2^n}+1\) is prime exactly when
\begin{equation*}
3^{2^{2^n1}}\equiv 1\text{ (mod }2^{2^n}+1)
\end{equation*}
Proof.
We will try to connect this with
Euler’s Criterion. Note that
\((F_n1)/2 = 2^{2^n1}\text{,}\) the power of three in the statement.
First, let’s assume \(F_n\) is prime. Since \(F_n\) is one more than a multiple of four, clearly
\begin{equation*}
F_n\equiv 1, 5,\text{ or }9\text{ (mod }12)\text{.}
\end{equation*}
Let’s examine a few cases.
If \(F_n\equiv 1\text{ (mod }12)\text{,}\) then \(3\mid 2^{2^n}=F_n1\text{,}\) which cannot be true.
If \(F_n\equiv 9\text{ (mod }12)\text{,}\) 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).\)
Since
\(F_n\) is prime, that means by
Proposition 17.3.4 we know
\(3\) is not a QR mod
\(F_n\text{.}\) (Quadratic reciprocity is implicit here, though we happened to calculate this before we had stated it.) Thus
Theorem 16.5.2 should give that
\(3^{(F_n1)/2}=1\text{.}\)
For the converse, let’s assume that
Euler’s Criterion gives this answer of
\(1\) for
\(a=3\text{.}\) Then square both sides to get
\begin{equation*}
3^{F_n1}\equiv 1\text{ (mod }p)
\end{equation*}
for all primes \(p\) dividing \(F_n\text{.}\) Now, what order does \(3\) have here?
Since \(F_n1=2^{2^n}\text{,}\) that means 3 has order some power of \(2\) (in \(U_p\)).
But 3 can’t have order \(2^{2^n1}\) (or less), because it isn’t the identity when taken to that power.
So it must have order \(2^{2^n}\text{.}\)
The only way 3 can have that big an order is if \(p\) is at least \(2^{2^n}+1=F_n\text{.}\) So since \(p\mid F_n\text{,}\) they must be equal!
Subsection 17.5.3 Yes, even cryptography
Suppose we have two primes \(p\) and \(q\) that are both of the form \(4n+3\text{.}\) Then it should (probabilistically) be possible to find a number \(a\) such that
\begin{equation*}
\left(\frac{a}{p}\right)=1=\left(\frac{a}{q}\right)\text{ so that }\left(\frac{a}{pq}\right)=1
\end{equation*}
Then the
GoldwasserMicali cryptosystem^{ 9 } uses the fact that it isn’t obvious whether a Jacobi symbol which equals one implies
\(a\) is actually a quadratic residue to create a publickey cryptosystem.
Now, does this really use quadratic reciprocity? It’s true that decryption is possible using criteria like Euler’s if you have the factorization
\(n=pq\text{,}\) and the Legendre/Jacobi symbol would be multiplicative with or without
Theorem 17.4.1. But to my mind one wouldn’t have even had the thought to create such a system (or even the Jacobi symbol itself) without the full theorem, so it seems appropriate to mention this application here.
Subsection 17.5.4 Solving equations
There is even more! As one example, quadratic reciprocity (or at least the Legendre symbol, which we most easily compute using reciprocity) helps us solve Mordell equations. For instance,
Fact 15.3.3 and similar facts implicitly use
\(\left(\frac{1}{p}\right)\text{.}\) The next 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 solvable with the help of knowledge of values of the Legendre symbol. See for example
[E.4.6, Theorem 9.12] or
[E.2.8, Section 7.4C], the latter of which explicitly uses quadratic reciprocity.
Subsection 17.5.5 Artin’s conjecture
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\text{,}\) 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 longstanding question.
Conjecture 17.5.3. 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\text{,}\) \(5\text{,}\) 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 \text{.}\) It turns out that this is directly connected to whether
\(10\) is a primitive root for a given prime (see
Exercise 17.7.21). Likewise, when Euler found that
\(F_5=4294967297\) was composite (recall
Subsection 12.1.1) he would have been helped along quite a bit by information about this conjecture, as his 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.
Example 17.5.4.
Recall from the very end of
Section 11.6 that if
\(q\) and
\(p=2q+1\) are both odd primes, then we call
\(q\) a Germain prime. In that case, every residue of
\(p\) other than
\(a=1\) and
\(a=0\) is a primitive root or a QR. One way to interpret this is as complementing
Fact 16.4.5, which characterizes even powers of a primitive root as being QRs; namely, for
\(p\) nearly all odd powers must be primitive roots.
Such a prime \(p\) must be of the form \(p\equiv 3\text{ (mod }4)\text{.}\) This follows because \(q\) is odd so \(q=2k+1\) for some integer \(k\text{,}\) yielding
\begin{equation*}
p=2(2k+1)+1=4k+3\text{.}
\end{equation*}
(This is how we know that
\(1\text{,}\) which is clearly not a primitive root, also isn’t a QR; recall
Fact 16.1.2.)
In this case, not only are all residues other than \(0,1\) either a primitive root or a QR, but \(a\) is one of these things precisely when \(pa\) is the other. We know that
\begin{equation*}
1^2,2^2,3^2,\ldots,q^2
\end{equation*}
are all different modulo \(p\text{,}\) and of course all of these are QRs (and so not primitive roots).
Here is the key; that means that the additive inverses of perfect squares,
\(pk^2\text{,}\) for
\(2\leq k\leq q\text{,}\) must all be primitive roots. The smallest of these,
\(p4\text{,}\) must thus be a primitive root for any such (safe; recall
Subsection 11.6.4) prime
\(p=2q+1\text{.}\)
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.
\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.)
en.wikipedia.org/wiki/Solovay–Strassen_primality_test
www.fermatsearch.org/factors/faclist.php
As of this writing \(F_{20}\) has been known to be composite for over thirty years, yet we still do not know any of its factors.
primes.utm.edu/glossary/page.php?sort=FermatNumber
en.wikipedia.org/wiki/Goldwasser–Micali_cryptosystem
primes.utm.edu/top20/page.php?sort=SophieGermain