I'm trying to figure out how to solve multiple simultaneous modulus equations. The problem I'm hitting is that I get to a point where there's too many unknowns or degrees of freedom for how many equations I have and I'm not sure what to do about it.

For instance, let's say I have these 4 equations:
$A mod K_0 = 0$
$A mod K_1 = 1$
$B mod K_0 = 0$
$B mod K_1 = 0$

I'm trying to find any values of $A$,$B$,$K_0$ and $K_1$ that satisfy the above.

I know that I can transform each of those into the four following equations:
$A = K_0N_0$
$A = K_1N_1+1$
$B = K_0N_2$
$B = K_1N_3$

Where $N_i \epsilon \mathbb Z$.

That then seems to leave me with 4 unknowns ($A$,$B$,$K_0$,$K_1$) and four values that can be any integer value ($N_0$, $N_1$, $N_2$, $N_3$), and four equations.

Four equations with four unknowns sounds like I'm basically there, but what do i do about the $N_i$ values?

How do I go about finding values for $A$,$B$,$K_0$ and $K_1$ that fit the original 4 equations?

EDIT: Since posting this question i've learned a number of things, but am still stuck.

I know modular multiplicative inverse, the chinese remainder theorem, and the extended euclidean algorithm.

I can solve modulus equations of the form: $x \% 10 = 2$
$x \equiv 2 + 10 \mathbb Z$

This form: $((x\%7)\%5)\%2=1$
$x \equiv (1 + 7 \mathbb Z) \cup (3 + 7 \mathbb Z) \cup (6 + 7 \mathbb Z)$
$x \in${…, -6, -4, -1, 1, 3, 6, 8, 10, 13, 15, 17, 20, …}

and This form: $3\%x=1$
$x | 2$

  • 1
    $\begingroup$ Search for Chinese Remainder Theorem. $\endgroup$ – Jyrki Lahtonen Sep 7 '15 at 4:24
  • 1
    $\begingroup$ B is any multiple of LCM($K_0,K_1$). $\endgroup$ – DanielWainfleet Sep 7 '15 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.