Section 17.5 Some Surprising Applications of QR
Subsection 17.5.1 Factoring, briefly
As an example, it can help us with factoring large integersSubsection 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. (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 forhttp://www.prothsearch.com/fermat.html
for which Fermat numbers still need more factorsβ2β, or the relevant member of the excellent Prime Pages.
xxxxxxxxxx
def _(n=(1,[1..6])):
F=2^(2^n)+1
pretty_print(html("The $%s$th Fermat number is $%s$"%(n,F)))
test = mod(3,F)^((F-1)/2)
if test == -1:
pretty_print(html(r"Since $3^{(%s-1)/2}\equiv %s$, this Fermat number is prime"%(F,test)))
else:
pretty_print(html(r"Since $3^{(%s-1)/2}\equiv %s$, this Fermat number is not prime"%(F,test)))
Fact 17.5.1. PΓ©pin's Test.
For
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
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
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,
Subsection 17.5.3 Yes, even cryptography
Suppose we have two primesSubsection 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 useThe equation
has no integer solutions. (Uses )The equation
has no integer solutions. (Uses )
Subsection 17.5.5 Artin's conjecture
Let's return to the test forConjecture 17.5.3. Artin's Conjecture.
Every nonsquare integer except
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
or 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.
xxxxxxxxxx
def _(n=(1,[1..6])):
F = 2^(2^n)+1
a = mod(3,F)
if a.multiplicative_order()==F-1:
pretty_print(html("$3$ is a primitive root of $F_{%s}=%s$"%(n,F)))
else:
pretty_print(html("Not prime, no primitive root!"))
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
Such a prime
(This is how we know that
In this case, not only are all residues other than
are all different modulo
Here is the key; that means that the additive inverses of perfect squares,
xxxxxxxxxx
def _(q=(11,[r for r in prime_range(3,100) if is_prime(2*r+1)])):
p = 2*q+1
a=mod(p-4,p)
if a.multiplicative_order()==p-1:
pretty_print(html("$-4$ is a primitive root of $%s$"%p))
else:
pretty_print(html("Mistake!"))