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 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 2h, is not prime, and p divides n, then 2 raised to the 2h is -1 mod p. This means 2h+1 divides p-1. For h > 1, p = 1 mod 8, and 2 is a square. Therefore p is 1 mod 2h+2.