1

I have an arithmetic sequence, $a+dn$, where $a$ and $d$ are constants and $n$ is the term number. How would I efficiently calculate solutions to the following equation,

$$ (a+dn)\%b=0 $$

where $b$ is also a constant. (and $\%$ means modulo)

I attempted the question myself and found out that I really just need to find the smallest $n$ that satisfies the equation and find the rest by adding ${kb\over GCD(d,b)}$ to $n$, where $k$ is any integer. I also noticed that the smallest solution will always be less than $b$ and if no solution exist within this range, then there is no solution. So I tried to find the solution by brute forcing from 0 to $b$, until I got a solution. But this method is not nearly as efficient as I need it to be.

FieryRMS
  • 69
  • 4
  • is it for $n$ that you are looking for the solutions ? – Spectre Nov 03 '20 at 16:04
  • Yes, I am for solution for $n$. – FieryRMS Nov 03 '20 at 16:07
  • Ok then @FieryRMS..lemme see... – Spectre Nov 03 '20 at 16:07
  • 1
    If $\gcd(d,b)=1$, then the modular multiplicative inverse of $d$ modulo $b$ can be computed using the [extended Euclidean algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) – J. W. Tanner Nov 03 '20 at 16:09
  • 1
    If $\gcd(d,b)>1$, you could use the [congruence division rule](https://math.stackexchange.com/questions/1883921/d-gcdc-m-ac%e2%89%a1bc-pmod-m-rightarrow-a%e2%89%a1b-pmod-m-d-congruence-div) – J. W. Tanner Nov 03 '20 at 16:11
  • @J.W.Tanner, is my answer valid ? – Spectre Nov 03 '20 at 17:05
  • @Spectre: I would suggest multiplying by the multiplicative inverse of $d$ mod $b$ (when it exists), to solve when $d\nmid b-a$ – J. W. Tanner Nov 03 '20 at 17:10
  • @J.W.Tanner , I haven't learnt it completely, so what I'd like to know is whether what I have put up is ok... I have put a reference to your comments here do that the OP find other cases that this answer doesn't have. – Spectre Nov 03 '20 at 17:12

1 Answers1

0

If $a + dn \equiv 0(\mod{b})$, $$dn \equiv -a (\mod{b}) \implies dn \equiv b - a (\mod{b})$$ (assuming $b > a$, and of course the remainder should be less than the divisor as per Euclid's Division Lemma, and remainders should be positive) $$\implies n \equiv \dfrac{b - a}d (\mod{b}) \space \text{if} \space gcd(b,d) = 1 \space \text{and} \space d \mid (b - a)$$

Therefore, $n = bx + \dfrac{b - a}d$ is the kind of $n$ you might want.

But there may arise cases where this alone won't work, so I'd suggest attending a course on some advanced topics in modular arithmetic (even I am not an expert and I used what I knew to answer this question).

Refer the suggestions in @J.W.Tanner's comments beneath your question for more methods.

Spectre
  • 1,563
  • 5
  • 22
  • I found out this is a modified version of a Diophantine equation. Solving a Diophantine equation in the form, $ dx + by = a $ will give solution to my problem since I can rewrite it to be $y= {a+dx \over b}$ (I didn't change the sign because it really doesn't matter since $x$ can be any number, negative or positive.) – FieryRMS Nov 04 '20 at 06:16