Applications of Quadratic Reciprocity

Modular Mathematics, Applications of Quadratic Reciprocity

Applications of Quadratic Reciprocity

Is 3 a square mod p? Flip to find out, negating if p = 3 mod 4. The answer is yes if p = ą1 mod 12. For instance, 3 = 5 squared mod 11. Similarly, [5\p] = 1 when p = ą1 mod 5, and [7\p] = 1 when p = ą{1,3,9} mod 28.

When factoring 999993, p must divide 1000²-7. Reducing mod p shows 7 is a residue, hence p is ą1, ą3, or ą9 mod 28. I don't know if this trick is used by any general purpose factoring programs; probably not.

If p is a Fermat prime, 3 is primitive mod p. Recall that p-1 is a power of 2. There are φ(p-1) = (p-1)/2 primitive elements, each a non residue. Assuming p > 3, 3 does not divide p or p-1. Thus [3\p] = [p\3] = -1, and 3 is primitive.

If a Fermat number n, with exponent 2^h, is not prime, and p divides n, then 2 raised to the 2^h is -1 mod p. This means 2^h+1 divides p-1. For h > 1, p = 1 mod 8, and 2 is a square. Therefore p is 1 mod 2^h+2.