# Can we classify all primes in the set of candidates at a certain iteration of the prime number sieve?

Consider the group $U(p_1\dots p_n)$, where $p_i$ is the $i^{th}$ prime. For any pair of primes $p,q>p_n$, say that $p\sim q$ if and only if $p\equiv q\pmod{p_1\dots p_n}$. Does this define an equivalence relation on the set of all primes greater than $p_n$? If so, how many equivalence classes are there? What's the size of each class? Does there exist $r\in U(p_1\dots p_n)$ such that the equivalence class of $r$ is empty?

I made this one up, so if it's a dumb question, I am to blame.

For the second question, it follows from Dirichlet Theorem on arithmetic progressions that for each $r \in U(p1...p_n)$ there are infinitely many prime in its class.
• Okay, and so the number of classes is $\phi(p_1\dots p_n)$, right? Thanks for answering the question. I had no idea about Dirichlet's Theorem. Very interesting. Clearly I know almost nothing about number theory. – Spencer Parkin Apr 10 '17 at 20:04
• So it would be interesting to consider the classes for $p_1\dots p_n+1$ and $p_1\dots p_n-1$ in connection with twin primes. – Spencer Parkin Apr 10 '17 at 20:08
• @SpencerParkin The problem is that it probably doesn't help. There are infinitely many primes of the form $k p_1...p_n \pm 1$ but there is no way of telling if you can find one pair for the same $k$. – N. S. Apr 10 '17 at 22:53