Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer
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
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.