I think, in fact, for every prime number p at least 5, 4 mod p is (congruent to) 4.

Even without the restriction to primes, that feels like a pretty good guess!