Period of a set of primes Let $S$ be a set of primes. We call a positive integer $n$ a period of $S$ if $p\in S$ implies $q\in S$ for all primes $q$ with $q\equiv p\mod n$. Show that if $n_1$, $n_2$ are periods of $S$, then $\gcd(n_1,n_2)$ is a period of $S$.
The problem in this exercise is that the "base set" is the set of primes. Within all integers, you could simply use the Bézout identity.
I'm interested in a solution as elementary as possible. However, I guess something like Dirichlet's theorem on arithmetic progressions is needed.
 A: Given $n = \gcd(n_1,n_2)$, $p\in S$ and $q\equiv p\pmod n$, find (using Dirchlet and the Chinese remainder theorem) a prime $r$ such that $r\equiv p\pmod{n_1}$ and $r\equiv q\pmod{n_2}$. Then $r\in S$ because $p\in S$ and $n_1$ is a period and then $q\in S$ because $r\in S$ and $n_2$ is a period.
It looks like the claim is almost equivalent to Dirichlet's theorem ...
A: To show that $n = \gcd(n_1,n_2)$ is a period of $S$, let $p\in S$ be a prime
and $q$ be a second prime with $p\equiv q\mod n$. We have to show that $q\in S$.
If both numbers $n_1$ and $n_2$ are divisible by $p$, then $p\mid n$ and therefore $p\mid q$. Since $p$ and $q$ are prime, we get $q = p\in S$.
Otherwise, without loss of generality, $n_1$ is coprime to $p$. By Dirichlet, the set $p + n_1\mathbb{Z}$ containes infinitely many primes. So there is a prime $p'\equiv p\mod n_1$ such that $n_2$ is not divisible by $p$.
Since $n_1$ is a period of $S$, we have $p\in S \iff p'\in S$.
Furthermore, $p'\equiv q\mod n$.
So we may replace $p$ by $p'$.
In the same way, if $n_1$ and $n_2$ are both divisible by $q$, then $q = p\in S$. Otherwise, we may replace $q$ by a prime $q'$ such that neither $n_1$ nor $n_2$ are divisible by $q'$.
After the replacements, we got the additional preconditions $\gcd(p,n_1) = \gcd(p,n_2) = \gcd(q,n_1) = \gcd(q,n_2) = 1$.
Since $p\equiv q\mod \gcd(n_1,n_2)$, the system of congruence equations
\begin{align*}
r & \equiv p\pmod{n_1} \\
r & \equiv q\pmod{n_2}
\end{align*}
has the solution set $x + \operatorname{lcm}(n_1,n_2)\mathbb{Z}$ with some $x\in\mathbb{Z}$.
Assume there is a prime $d$ dividing both $x$ and $\operatorname{lcm}(n_1,n_2)$.
Without loss of generality, $d$ divides $n_1$ (otherwise, interchange the role of $n_1$ and $n_2$). From $x\equiv p\mod n_1$ we get $x = p + kn_1$ with $k\in\mathbb{Z}$. So $d$ is a divisor of $x - kn_1 = p$. Since $d$ and $p$ are prime, we get $d = p$ which contradicts $p\nmid n_1$.
So $x$ and $\operatorname{lcm}(n_1,n_2)$ are coprime. Now By Dirichlet, the solution set $x + \operatorname{lcm}(n_1,n_2)\mathbb{Z}$ containes a prime $r$.
From $p\in S$ and $r\equiv p\mod n_1$ and the precondition that $n_1$ is a period of $S$, it follows that $r\in S$.
Finally, from $r\equiv q\mod n_2$ and $n_2$ a period of $S$ we get $q\in S$.
