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.  These results extend to larger finite fields, using the same proof as 2.

When factoring 999993, p must divide 10002-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 nonsquare.  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 2h, is not prime, and p divides n, then 2 raised to the 2h is -1 mod p.  Take logs in the multiplicative group mod p, and log(2)×2h maps to (p-1)/2.  The image contains all but one of the factors of 2 in p-1.  This means log(2)×2h+1 contains exactly the powers of 2 in p-1.  For h > 1, p = 1 mod 8, and 2 is a square.  Thus log(2), relative to a primitive element b, is even.  Pull a factor of 2 out and log(sqrt(2))×2h+2 accounts for the factors of 2 in p-1.  Therefore p is 1 mod 2h+2.

I tried this for the first few fermat numbers, including 2128+1.  The factors are 59649589127497217 and 5704689200685129054721; and each is 1 mod 256.  Similarly, 2256+1 = 1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321.  And that's enough of that.