Polynomials over Z/pZ are quite useful for encoding various kinds of information in number theory. Applications include the proofs of Wilson's theorem, Euler's criterion, and the existence of primitive roots mod p; as well as the determination of the sign of the quadratic Gauss sum.