Applications of quadratic reciprocity to integers abound; a few that will be generalized later on are the following:
If p and q = 2p+1 are odd primes, then q | 2p-1
if and only if p = 3 mod 4;
If p and q = 4p+1 are odd primes, then q | 22p+1.
If Un denote the Fibonacci numbers U1 = 1, U2 = 1, Un+1 = Un + Un-1, then primes p different from 5 divide Up-1 if (p/5) = +1, and Up+1 if (p/5) = -1.
Let me also mention a conjecture that I hope to be able to prove in the second volume: Let Fn denote the n-th Fermat number; it is well known that Fn is prime if and only if 322n-1 = -1 mod Fn. The conjecture says that we may save that last n multiplications because Fn is prime if and only if (-3)22n-n-1 = -8 mod Fn.
Let q be an odd integer and suppose that p = 4q+1
is prime. Then Sq = 22q+1 is never
prime because of the (Aurifeullian) factorization
Sq = Aq Bq, where Aq = 2q - 2(q+1)/2 + 1 and Bq = 2q + 2(q+1)/2 + 1.
Now p = 4q+1 = 5 mod 8, hence the quadratic reciprocity law shows that
Sq = 2(p-1)/2 +1 = (2/p)+ 1 = 0 mod p. Thus p divides AqBq,
and the question (first posed by Brillhart [Concerning the numbers 22p+1, p prime, Math. Comp. 16 (1962), 424-430]) is: which? Since quadratic reciprocity has told us that p | AqBq, we might hope that quartic reciprocity will answer this question. And it does: if we write p = a2 + b2 as a sum of squares with b even, then the result is that
p | Aq if and only if b/2 = 3, 5 mod 8, and
p | Bq if and only if b/2 = 1, 7 mod 8.