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^n-1}}\equiv -1\text{ (mod }2^{2^n}+1)
\end{equation*}
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
Another application is that it can help us check primality. For instance, a test similar in spirit to the Miller-Rabin (probabilistic) primality test, but which uses Legendre/Jacobi symbols, is the Solovay-Strassen test 5 . (See Exercise 17.7.22.)
A specific example where quadratic reciprocity 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 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?
Analogously to 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\text{.}\) See the Distributed Search for Fermat Number Divisors 6 or
http://www.prothsearch.com/fermat.html for which Fermat numbers still need more factors 7 , or the relevant member of the excellent Prime Pages 8 .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.
Proof.
We will try to connect this with Euler’s Criterion. Note that \((F_n-1)/2 = 2^{2^n-1}\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_n-1\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_n-1)/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_n-1}\equiv 1\text{ (mod }p)
\end{equation*}
for all primes \(p\) dividing \(F_n\text{.}\) Now, what order does \(3\) have here?
- Since \(F_n-1=2^{2^n}\text{,}\) that means 3 has order some power of \(2\) (in \(U_p\)).
- 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}\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!
Remark 17.5.2.
Interestingly, Mersenne numbers can sometimes also be shown to be composite using quadratic residues. For instance, \(2^p-1\) with exponent \(p\equiv 3\text{ (mod 4})\) which is itself a Germain prime must be composite. See [E.2.13, Theorem 7.6], and see [E.2.4, Exercises 9.1.37-40] for many more criteria like this.
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*}
where the latter symbol is a Jacobi symbol (recall Definition 17.4.9).
Then the Goldwasser-Micali 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 public-key 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.
- The equation \(x^3=y^2+16\) has no integer solutions. (Uses \(\left(\frac{-8}{p}\right)\text{.}\))
- The equation \(x^3=y^2-46\) has no integer solutions. (Uses \(\left(\frac{-18}{p}\right)\text{.}\))
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 long-standing 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.
We put this in the form of several steps. Verifying several facts in these steps is left to Exercise Group 17.7.8–11.
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 \(p-a\) 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, \(p-k^2\text{,}\) for \(2\leq k\leq q\text{,}\) must all be primitive roots. The smallest of these, \(p-4\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.
The largest currently known 10 (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.)
en.wikipedia.org/wiki/Solovay–Strassen_primality_testwww.fermatsearch.org/factors/faclist.phpAs 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=FermatNumberen.wikipedia.org/wiki/Goldwasser–Micali_cryptosystemprimes.utm.edu/top20/page.php?sort=SophieGermain
