# 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.

-

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 ...

-
Thanks for your answer. Maybe it is worthwile to mention that you used some "extended version" of the Chinese remainder theorem: Normally, $\gcd(n_1,n_2) = 1$ is needed, which is not necesarily true in this case. However, since the right hand sides $p$ and $q$ are equivalent mod $\gcd(n_1,n_2)$, there is a unique solution mod $\operatorname{lcm}(n_1,n_2)$. – azimut Feb 10 '13 at 13:52
Thinking again about it, I don't quite get it. The Chinese remainder theorem gives us the set of solutions of $r\equiv p \pmod{n_1}$, $r\equiv q\pmod{n_2}$ as $x + \operatorname{lcm}(n_1,n_2)\mathbb{Z}$ with some integer $x$. Now to invoke Dirichlet, we need $\gcd(x,\operatorname{lcm}(n_1,n_2)) = 1$, which I don't think is true in general. – azimut Feb 10 '13 at 14:02
I guess in general it is not possible to go from $p$ to $q$ in a single mod $n_1$ and a single mod $n_2$ step. Hagen, what do you think? – azimut Feb 11 '13 at 1:30
@azimut : actually, $x$ is coprime to $n_1$ (since $p$ is prime) and similarly $x$ is coprime to $n_2$. So $x$ is coprime to ${\sf lcm}(n_1,n_2)$. – Ewan Delanoy Feb 13 '13 at 6:43
Dear Hagen, I upvoted your answer, but how would you deduce Dirichlet's theorem from this? – Bruno Joyal Feb 18 '13 at 0:41

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)$ 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$.

-