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 | 2^{p}-1
if and only if p = 3 mod 4;
If p and q = 4p+1 are odd primes, then q | 2^{2p}+1.
If U_{n} denote the Fibonacci numbers U_{1} = 1,
U_{2} = 1, U_{n+1} = U_{n} + U_{n-1},
then primes p different from 5 divide U_{p-1} if (p/5) = +1,
and U_{p+1} if (p/5) = -1.
Let me also mention a conjecture that I hope to be able to prove in the second volume: Let F_{n} denote the n-th Fermat number; it is well known that F_{n} is prime if and only if 3^{22n-1} = -1 mod F_{n}. The conjecture says that we may save that last n multiplications because F_{n} is prime if and only if (-3)^{22n-n-1} = -8 mod F_{n}.
Let q be an odd integer and suppose that p = 4q+1
is prime. Then S_{q} = 2^{2q}+1 is never
prime because of the (Aurifeullian) factorization
S_{q} = A_{q} B_{q}, where
A_{q} = 2^{q} - 2^{(q+1)/2} + 1 and
B_{q} = 2^{q} + 2^{(q+1)/2} + 1.
Now p = 4q+1 = 5 mod 8, hence the quadratic reciprocity
law shows that
S_{q} = 2^{(p-1)/2} +1
= (2/p)+ 1 = 0 mod p. Thus p divides A_{q}B_{q},
and the question (first posed by Brillhart [Concerning the numbers
2^{2p}+1, p prime, Math. Comp. 16 (1962), 424-430])
is: which? Since quadratic reciprocity has told us that
p | A_{q}B_{q}, we might hope that
quartic reciprocity will answer this question. And it does:
if we write p = a^{2} + b^{2} as a sum of squares
with b even, then the result is that
p | A_{q} if and only if b/2 = 3, 5 mod 8, and
p | B_{q} if and only if b/2 = 1, 7 mod 8.