# How to solve simultaneous modulus / diophantine equations

Does anyone know how i'd solve a set of equations like this?

$(x_0\%k_0)\%2=0$
$(x_0\%k_1)\%2=1$
$(x_0\%k_2)\%2=0$
$(x_0\%k_3)\%2=1$

$(x_1\%k_0)\%2=0$
$(x_1\%k_1)\%2=0$
$(x_1\%k_2)\%2=1$
$(x_1\%k_3)\%2=1$

I'm trying to find valid values of $x_i$ and $k_i$. I've found some solutions using a program to brute force it, but I want to up the number of $x$'s, $k$'s which rules out brute force as a practical solution.

For instance, there are two $x$ values above, which translate to $2^x$ $k$ values, and $x∗2^x$ equations. I'd like to take the number of $x$ values up to 16, or 32 if possible, which results in huge numbers of $k$'s and equations.

Anyone able to help at all, even to point me in some direction?

I do know about the chinese remainder theorem, multiplicative modular inverse and the extended euclidean algorithm, among some other basic modulus math techniques, but I'm not really sure how to make any progress on this.

Thanks!

Edit: To clarify a bit, Ideally I'd like to find all solutions to this problem, but if there is a way to find a subset of solutions, like if the equations below could be solved that would be fine too. Or, if there is some way to find solutions numerically which is much faster than brute force permuting the $x_i$ and $k_i$ values and testing if they fit the constraints, that'd be helpful too.

$x_0\%k_0=0$
$x_0\%k_1=1$
$x_0\%k_2=0$
$x_0\%k_3=1$

$x_1\%k_0=0$
$x_1\%k_1=0$
$x_1\%k_2=1$
$x_1\%k_3=1$

• Please improve your post using mathjax/LaTeX syntax Sep 19, 2015 at 13:58
• sorry, hadnt had coffee yet, fixed (: Sep 19, 2015 at 13:59
• Note that $f: x \pmod k \mapsto x \pmod 2$ is only a well-defined homomorphism if $2 \mid k$, and in this case $x \pmod 2 = f(x \pmod k)$ so there are no solutions, which means there's not much of a chance you can apply group/ring theory here. Sep 20, 2015 at 8:26
• Do you want all solutions, or do you have any restrictions upon solutions? If you just want one (trivial) solution: for a fixed $x$ we want to find $k$'s such that $(x \% k)\%2 = 0$ and $(x\%k)\%2 = 1$, so we can just take $k = x$ and $k = x-1$. Sep 20, 2015 at 8:42
• I just realized my notation was messed up. I migrated this from cryptography and lost the notation along the way. Fixed now! FWIW I'd prefer finding all solutions, but if there was a way to find a subset of solutions, or a numerical way to find solutions that was much, much, much faster than brute force, that would be acceptable too. My actual usage case that i'm working towards has many more x's and k's Sep 20, 2015 at 14:11

If there are a large number of solutions then any method of reducing your search will still have many indeterminate variables.

That said some modulo 2 equations can be reduced to exclusive or (xor) equations that have similar reduction methods to linear equations.

(x%k)%2 = r can be written as $x + ck \equiv r \pmod2$ which can be written as the logic equation $$x\oplus ck \oplus r = 0$$ where $\oplus$ is the xor operator and x,c,k,r are Boolean values.

e.g. If r = 0 then $x=ck$. If r = 1 then $x=ck\oplus 1$, $x= not\ ck$.

You can convert all of the mod 2 equations into xor equations then reduce them into an upper triangular form Uz = b, z = [x ck]'. If there are no solutions then the bottom non zero line will be 0 = 1. If there is a unique solution the bottom line will have the form $z_t$ = [0|1]. If there are multiple solutions then it will be of the form $z_1\oplus z_2\oplus z_3\dots=[0|1]$. You will have to try the combinations that solve the equation and move up the U matrix doing the same with those equations.

The ck terms increase the number of solutions. If ck = 1 then (c=1,k=1). If ck = 0 then (c=0,k=0) or (c=0,k=1) or (c=1,k=0).

• intriguing! Thanks for this info arthur, very cool stuff. Sep 24, 2015 at 16:43
• this only works if x and k are booleans, 0 or 1 right? i need integer solutions for the x's and k's unfortunately, 0 and 1 alone won't help me. really cool info though and very interesting :P Sep 24, 2015 at 22:10
• This works for all integers. Under modulo mathematics if x = y mod m then x and y can be substituted for each other into polynomials and the same result is achieved in that modulo. if x = 2*c + 1 and y = 1 then $f(z) = a_n.z^n + ... + a_1.x + a_0$ mod 2 f(x) = f(y) mod 2 So you can solve the equations mod 2 then add multiples of 2 to any variable and it will still solve the equations.
– user186104
Sep 25, 2015 at 0:30

I came up with a solution that I'm happy with so far, since it lets me find decent solutions that lets me move on with my reason for wanting to solve these equations.

I'm solving these equations:
$x_0\%k_0=0$
$x_0\%k_1=1$
$x_0\%k_2=0$
$x_0\%k_3=1$

$x_1\%k_0=0$
$x_1\%k_1=0$
$x_1\%k_2=1$
$x_1\%k_3=1$

I solve them by using the chinese remainder theorem for each $x_i$, and i use prime numbers for each $k_i$ value, where each $k_i$ gets it's own prime number. This is to ensure than the $k_i$ values are co-prime, when running them through the chinese remainder theorem algorithm.

This works well and answers are calculated extremely fast, so I'm happy :P