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