Can every infinite set be finitely sieved by arbitrary congruences of primes? Let $I \subseteq \mathbb{N}$ an infinite subset of positive integers. Denote with $\mathbb{P}$ the set of all prime numbers. For each $p \in \mathbb{P}$ let $I_p = I \cap \{p, 2p, 3p, ...\} = \{n \in I : p|n\}$ where $p|n$ means $p$ divides $n$.
Then $I \cap \displaystyle \bigcap _{p \in \mathbb{P}} I_p^C$ is a finite set, where $I_p^C$ denotes the complement of $I_p$ (as an example, if $I = \mathbb{N}$, then $I \cap \displaystyle \bigcap _{p \in \mathbb{P}} I_p^C = \{1\}$).
I would like to prove or disprove the following generalization of this fact:
Let $I \subseteq \mathbb{N}$ an infinite subset of positive integers and let $f : \mathbb{P} \longrightarrow \mathbb{N}$ such that $f(p) \in \{0,...,p-1\}$ for each $p \in \mathbb{P}$.
For each $p \in \mathbb{P}$ let $I_p = I \cap \{p + f(p), 2p  + f(p), 3p  + f(p), ...\} = \{n \in I : n \equiv f(p) \text{(mod }p\text{)}\}$ (note that, in the first scenario, $f(p) = 0$ for each $p$).
Then $I \cap \displaystyle \bigcap _{p \in \mathbb{P}} I_p^C$ is a finite set.
Any hint? I've tried to use the concept of ultrafilters but without any success - that's because I can't fully grasp it - but I don't know if this type of question can really be handled with ultrafilters.
 A: I found a counterexample for your statement.
Let $I=\Bbb N$ and $$f(p)= \begin{cases} 1 & \mbox{if }p=2 \\ 0 & \mbox{if }p\ge 3\end{cases}$$
then
$$I_2^C = \{ n | n \mbox{ is even}\}$$
and for $p \ge 3$
$$I_p^C = \{ n | n \mbox{ is not a multiple of }p\}$$
Clearly
$$I \cap \bigcap_p I_p^C = \{ n | n \mbox{ is only divisible by }2\}$$
which is not a finite set, since it contains all powers of $2$.
Similar counterexamples can be build by considering $I= \Bbb N$ and $f(p)=0$ for all but finitely many primes $p_1, \dots , p_k$. In such a case all numbers $n$ of the form $$n=p_1^{\alpha_1} \cdots p_k^{\alpha_k}$$ (with $\alpha_1, \dots , \alpha_k \ge 1$) belong to $\bigcap_p I_p^C$.
A: This is to answer some follow-up questions you had or could have:

*

*If $f(p) \neq 0$ for all $p$, is the set necessarily finite?
The answer is no: Take any sequence of numbers of the form $2^a$, $2^b3^c$, $2^d3^e5^f$, ... Given the $k$th prime $p_k$, from the $k$th numbers onwards they are all divisible by $p_k$. So define $f(p_k)$ to be any nonzero residue that is not the residue of one of the first $k−1$ numbers. Because $p_k−1>k−1$, this can be done.


*Can the set ever be finite for a nontrivial choice of $f$?
The answer is yes, by a diagonal argument. It can even be empty: Define $f(p_k)$ to be the residue of $k$ modulo $p_k$. (Since $p_k > k$, this just means $f(p_k) = k$.)
