What can primes, except 2, 3, and 5, be congruent to $\pmod {30}$?

It happens to be true for a $30$ (if you allow $q=1$ as gnometorule pointed out), but not necessarily for other moduli.

For example, $109 \equiv 49 \pmod{60}$, but $109$ is prime and $49$ isn't.

In general the possible remainders of primes are everything (in the appropriate range) that is coprime with the modulus, by Dirichlet's theorem. When the modulus is 30, it just happens that all of these, except 1, are primes themselves.


As gnometorule points out this isn't true because $1$ is not a prime. It is on the other hand true that every prime is congruent to $1 \leq q < 30$, modulo $30$, where $q$ is either $1$ or a prime.

The reason is because every number between $1$ and $29$ which is not prime is divisible by at least one of $2, 3, 5$. As $30$ is also divisible by these numbers this means any number congruent to these is divisible by one of $2, 3, 5$.


31 isn't. (adding minimum # chars)