

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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


