What can primes (except 2,3, or 5) be congruent to (mod 30)?

Question

I know that $30$ must divide $p-x$ which implies 30n+x=p.

My thought was to find all integer solutions of this equation. I have that $0,p$ is always a solution so my next thought is to solve this as a linear diophantine equation. I have that $n=1+pt$ and $x=p-30t$ $\forall t\in \mathbb{Z}$. I then thought all solutions are of the form $p-30t$.

When I plug them into the equation for some choices of $t$, everything works out. Is this a proper solution and is there a better way to tackle this problem?

Answer 1

You are almost there! You already know $30n+x=p$. Hence, if $\gcd(x,30)\neq 1$, you can factor out $\gcd(x,30)(\frac{30n+x}{\gcd(x,30)})=p$, contradicting $p$ prime.

So you only have the numbers $1,7,11,13,17,19,23,29$. Examples of such primes that are $\mod 30$ are $31,37,41,43,47,79,83,89$ respectively, and we are done.

Answer 2

maybe this is prior art that I'm unaware of, but I realized those 8 scenarios under 30

1, 7, 11, 13, 17, 19, 23, 29

for all primes can be collapsed down to a single unified formula that isn't too complicated :

---

(( n % 30 - 15 ) ^ 4 ) % 30 == 16

---

• The pros is that one can either skip either a 8-scenario case statement, a regular expression, or a table lookup.

• The cons is that one extra high-cost division/modulo must be performed.