Actually, it is really required that p to be prime. However, the universal class of hash function couldn't be derived, especially when we use function described in book "introduction to algorithm". One more reason that why p is prime, is that Zp × Zp* = 1. It comes up from number theory. Where inverse for number is defined when p is prime.