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?

$\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
    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$ 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$ Apr 22, 2013 at 21:06

1 Answer 1

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

$\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$ 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$ 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
    Apr 23, 2013 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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