2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Stefan Kohl ♦
    Commented Apr 22, 2013 at 20:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Greg Martin
    Commented Apr 22, 2013 at 20:50
  • $\begingroup$ 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. $\endgroup$
    – Maaz-ul-Haq
    Commented Apr 22, 2013 at 21:06

1 Answer 1

Reset to default
4
$\begingroup$

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$

and

$N \equiv 5 \bmod 7$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Barry Cipra
    Commented Apr 22, 2013 at 21:19
  • $\begingroup$ The question is for coprime moduli. It appears that this is it: Chinese remainder theorem with some basic algebra and modular arithmetic. $\endgroup$
    – Maaz-ul-Haq
    Commented Apr 22, 2013 at 21:32
  • $\begingroup$ 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. $\endgroup$
    – fretty
    Commented Apr 23, 2013 at 7:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .