How do I solve this system of modular equations?

Question

How do I solve this system of modular equations?

$2=(4+6a)k_1^{-1}\bmod19 $

$11=(3+6b)k_1^{-1}\bmod19$

$8=(5+5a)k_2^{-1}\bmod19$

$6=(18+5b)k_2^{-1}\bmod19$

I want to get the values for $a, b, k_1$, and $k_2$. Note that $k^{-1}$ denotes the modular inverse (mod $19$) of $k$.

How do I solve this? Or are there infinitely many solutions?

Answer 1

Multiply all congruences by $k_1$ or $k_2$ as appropriate. This gives a linear system: $$2k_1=4+6a\bmod19$$ $$11k_1=3+6b\bmod19$$ $$8k_2=5+5a\bmod19$$ $$6k_2=18+5b\bmod19$$ Now $19$ is a prime number, so we can solve this as if it were over $\mathbb Q$, treating all divisions as multiplications by inverses. We get the following set of solutions (modulo $19$ of course): $$(k_1,k_2,a,b)=(5,6,1,15)+(4,4,14,1)t\qquad t\in\mathbb Z;k_1,k_2\ne0$$

Answer 2

Solving in pari/gp.

Find $k_1$:

(4+6*a)/Mod(2,19)=Mod(3, 19)*a + Mod(2, 19)

and

(3+6*b)/Mod(11,19)=Mod(4, 19)*b + Mod(2, 19)

i.e. $k_1\equiv 2+3a\equiv 2+4b \pmod{19}$

Find $k_2$:

(5+5*a)/Mod(8,19)=Mod(3, 19)*a + Mod(3, 19)

and

(18+5*b)/Mod(6,19)=Mod(4, 19)*b + Mod(3, 19)

i.e. $k_2\equiv 3+3a\equiv 3+4b \pmod{19}$

Find $a$ from $3a\equiv 4b \pmod{19}$

4*b/Mod(3,19)=Mod(14, 19)*b

i.e. $a\equiv 14b \pmod{19}$

Thus $(k_1,k_2,a,b) \equiv (2,3,0,0) + (4b,4b,14b,b) \pmod{19}$

Verify in W.Mathematica:

Solve[{2*k1==4+6*a,11*k1==3+6*b,8*k2==5+5*a,6*k2==18+5*b},{k1,k2,a,b},Modulus->19]/.C[1]->b=

{{k1 -> 2 + 4 b, k2 -> 3 + 4 b, a -> 14 b, b -> b}}