The solution of the equation $a + b \cdot k \equiv 0 \pmod{n}$ for given values $a$, $b$ and $n$ (we are looking for value $k$)

Question

I have a problem.

I looking solution of the equation $a + b \cdot k \equiv 0 \pmod{n}$ for given values $a$, $b$ and $n$ (we are looking for value $k$). $k$ is positive integer.

How can we calculate it quickly?

---

For example:

$a = 10554$, $b = 6370$ and $n = 16383$

Solutions:

1. $10554 + 6370 \cdot 2025 \equiv 0 \pmod{16383}$

2. $10554 + 6370 \cdot 18408 \equiv 0 \pmod{16383}$

3. $10554 + 6370 \cdot 34791 \equiv 0 \pmod{16383}$

4. $10554 + 6370 \cdot 51174 \equiv 0 \pmod{16383}$

...

General: $k = 2025 + 16383 \cdot k_2$

When solutions do not exist?

Answer 1

If $\gcd(b,n) = 1$, then we are guaranteed a solution, as the inverse of $b$ modulo $n$ exists. In general if $\gcd(b,n) \mid a$ then we are guaranteed a solution too, as we can get rid of the $\gcd(b,n)$ factor. Indeed the later condition is necessary too, as then $nm - bk=a$ and so $\gcd(b,n) \mid a$.

To find solutions you might use the Extended Euclidean Algorithm. It's pretty easy application and just some basica algebra.

Answer 2

Hint:

Consider the possible cases:

• $a\equiv 0\mod \gcd(b,n)$,
• $a\not\equiv 0\mod \gcd(b,n)$.

Let $d=\gcd(n,b)$. So we can write $b=dba'$, $n=dn'$,where $\gcd(b',n')=1$, and the congruence becomes $$a+d(b'k)\equiv 0\pmod{dn'},\enspace\text{which implies }\;a\equiv 0\mod d.$$ Thus, if $a=da'$ we can simplify the congruence to $$a'+kb'\equiv 0\pmod{n'}.$$ Can you proceed?

Answer 3

As you already state, x≡2015 (mod 16383) is a solution to 6370x≡-10554 (mod 16383).

The method I used to solve the example problem may be used to solve any problem of the form a+bx≡0 (mod n). The method has two phases: the constraint generation phase and the basis conversion phase. The constraint generation phase tells us if a solution exists, no solution exists or the greatest common factor. It is possible to solve the problem via symbolic manipulation. However it may be better to solve a problem by hand using an augmente matrix representation. Furthermore, the augmented matrix representation may be used as a basis for further improving the method by using a more compact representation (such as a sparse, augmented matrix).

For more information, you can follow this think to a PDF version of this reply: https://www.academia.edu/36814068/How_I_Solved_10554_6370x_0_mod_16383_A_Reply_to_a_Question_at_Mathematics_Stack_Exchange .

I am also including images of the pages here: