MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Using elementary matrix row and column operations on the system of two diophantine equations, namely, $N=an+b$ and $N=cn+d$, where $n\in\mathbb{N}^0$, it can be shown that the intersection of these two arithmetic progressions is another arithmetic progression $N=(ac)n+c\delta+d$ where $\delta\in\mathbb{N}:a|\left(c\delta+d-b\right)$.

For example the intersection of $N=5n+3$ and $N=7n-2$ by the above formula is $N=35n+33$

Is there a way to transform $\delta$ such that the condition of divisibility is eliminated?

share|cite|improve this question
Do I understand you right that your question is about the intersection $(b+a\mathbb{Z}) \cap (d+c\mathbb{Z})$? -- This intersection is nonempty if and only if $b \equiv d$ mod ${\rm gcd}(a,c)$. – Stefan Kohl Apr 22 '13 at 20:42
And when it is nonempty, the intersection is a single arithmetic progression modulo $ac/\gcd(a,c)$. What you have written is equivalent, I think, but much more complicated. – Greg Martin Apr 22 '13 at 20:50
Yes the question was for the intersection of $\left(b+a\mathbb{Z},d+c\mathbb{Z}\right)$ and $gcd(a,c)=1$ so that it is always nonempty. – Maaz-ul-Haq Apr 22 '13 at 21:06
up vote 0 down vote accepted

You do not need a divisibility criterion, the intersection of two such arithmetic progressions can be found using the chinese remainder theorem.

In your example notice that any such $N$ in the intersection satisfies:

$N \equiv 3 \bmod 5$


$N \equiv 5 \bmod 7$

Solving gives $N \equiv 33 \bmod 35$.

share|cite|improve this answer
You can avoid a divisibity criterion and use the chinese remainder theorem only when the moduli are relatively prime. A better example would have used 10 and 14 instead of 5 and 7. – Barry Cipra Apr 22 '13 at 21:19
The question is for coprime moduli. It appears that this is it: Chinese remainder theorem with some basic algebra and modular arithmetic. – Maaz-ul-Haq Apr 22 '13 at 21:32
Well yeah but under conditions described above (on gcd$(a,b)$) you can still do a similar thing just it isn't as straight-forward. – fretty Apr 23 '13 at 7:31

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.