# How to solve this system of Modular equations?

I mean

{Mod[31*x + y, z] == 29, Mod[29*x + y, z] == 2, Mod[2*x + y, z] == 26}

Here is my unsuccessful try

FindInstance[{Mod[31*x + y, z] == 29, Mod[29*x + y, z] == 2,Mod[2*x + y, z] == 26},
{x, y, z}, Integers]

FindInstance::nsmet: The methods available to FindInstance are insufficient to find the requested instances or prove they do not exist.

The same results are obtained with Solve and Reduce.

• Perhaps ChineseRemainder would help... – David G. Stork Feb 9 '18 at 18:23
• @David G. Stork: Thank you for your edit: now the title is exacter formulated. Can you kindly elaborate your comment? – user64494 Feb 9 '18 at 18:35
• Look up ChineseRemainder[], which solves systems of Modular equations under certain general conditions on the relative primeness of the terms. – David G. Stork Feb 9 '18 at 18:36
• @David G. Stork: Don't see how to realize your idea. – user64494 Feb 9 '18 at 18:38

Sort of embarassed I forgot this method for a few days. Anyway, one can get a set of possible moduli that work by computing what is called a strong Groebner basis of the defining polynomials over the integers. This happens to be the type computed by GroebnerBasis with the setting CoefficientDomain->Integers.

polys = {31*x + y - 29, 29*x + y - 2, 2*x + y - 26};
gb = GroebnerBasis[polys, {x, y}, CoefficientDomain -> Integers]

(* Out[221]= {-777, -1 - y, 375 + x} *)

The important point is that, for the equations to have solutions, 777 must be equivalent to zero. That can only happen if the modulus is a factor of 777, which is to say, one of the divisors. Below are the nontrivial ones (that is, discarding 1).

moduli = Rest[Divisors[777]]

(* Out[225]= {3, 7, 21, 37, 111, 259, 777} *)

Solutions for a give divisor d might obtained using Solve with Modulus->d. Example:

Solve[polys == 0, {x, y}, Modulus -> moduli[[-3]]]

(* Out[236]= {{x -> 69, y -> 110}} *)

--- edit ---

Since the equations are linear one can also just use the Hermite normal form of the augmented matrix. This is obtained as the second matrix in the result from HermiteDecomposition. It corresponds to the reduced row echelon form, except division is not allowed.

polys = {31*x + y - 29, 29*x + y - 2, 2*x + y - 26};
{rhs, mat} = Normal[CoefficientArrays[polys, {x, y, z}]];
newmat = Join[mat, Transpose[{rhs}], 2]

(* Out[299]= {{31, 1, 0, -29}, {29, 1, 0, -2}, {2, 1, 0, -26}} *)

{umat, hnf} = HermiteDecomposition[newmat]

(* Out[300]= {{{-13, 14, -1}, {-1, 1, 1}, {-27, 29, -2}}, {{1, 0, 0,
375}, {0, 1, 0, 1}, {0, 0, 0, 777}}} *)

Reading from the last row of hnf, we see that 777==0 is a requirement for a solution to exist. The other rows tell us that x==-375 and y==-1

--- end edit ---

• Very systematic way ! – yarchik Feb 15 '18 at 22:02

You can rewrite the equations without Mod by introducing extra variables.

{x, y, z} /. FindInstance[31 x + y == k1 z + 29 && 29 x + y == k2 z + 2 && 2 x + y == k3 z + 26, {x, y, z, k1, k2, k3}, Integers, 3]

(* {{47, 39, 1}, {-39, -19, -1}, {-43, 0, 1}} *)

If you don't want trivial solutions with |z| = 1, you can just add another inequality.

• +1. This is a big step. But how to find all the solutions of the system under consideration? Solve produces a strange result. – user64494 Feb 9 '18 at 20:01

Smallest solution I found is {x->32,y->36,z->37}. I found this by taking the equations and rewriting each of them to be Mod[y,z]=r:

29==Mod[31x+y,z] -> Mod[29-31x,z]==Mod[y,z]
2==Mod[29x+y,z] -> Mod[2-29x,z]==Mod[y,z]
26==Mod[2x+y,z] -> Mod[26-2x,z]==Mod[y,z]

Then you can solve for y using ChineseRemainder:

ChineseRemainder[{29-31x,2-29x,26-2x},{z,z,z}]

This will yield a solution so long as x and z are chosen such that a solution exists.

To find such x and z, brute force was used:

dat = Table[{x, z, ChineseRemainder[{29 - 31 x, 2 - 29 x, 26 - 2 x}, {z, z, z}]}, {x, 1, 100}, {z, 30, 2000}];
DeleteCases[Flatten[dat, 1], {_, _, ChineseRemainder[_, _]}] (* to remove all unevaluated cases *)

Note that this returns in the order {x,z,y}.

{Mod[31 x + y, z] == 29,
Mod[29 x + y, z] == 2,
Mod[2 x + y, z] == 26} /. {x -> 32, y -> 36, z -> 37}
{True, True, True}

In an attempt to generalize the solution, we can attempt to simplify the original equations by adding and subtracting them from each other:

Mod[29-31x,z]==Mod[y,z]==Mod[2-29x,z] -> Mod[27-2x,z]==0
Mod[26-2x,z]==Mod[y,z] && Mod[27-2x,z]==0 -> Mod[y,z]==Mod[-1,z]

Mod[2-29x,z]==Mod[y,z]==Mod[26-2x,z] -> Mod[24+27x,z]==0
Mod[27-2x,z]==0==Mod[24+27x,z] -> Mod[375+x,z]==0 -> Mod[x,z]==Mod[-375,z]

From here we can write these equations in terms of arbitrary integer constants k1 and k2:

x == k1 z - 375
y == k2 z - 1

Which describes a solution set so long as the base case is satisfied (plug in the case when k1 and k2 are both 0 to the original equation). Simplifying that condition, we find that:

Mod[-777,z] == 0

Is another necessary condition, which is satisfied if z equals 37, 111, 259, or 777; or possibly some negative z values as well.

• Thank you. The question " How to obtain all the solutions?" remains open. – user64494 Feb 9 '18 at 20:03
• @user64494 I have generalized the solution to the best of my abilities by applying the steps in the first half of my answer more completely. I'm somewhat surprised that Solve is as unhelpful as it is in this work though. – eyorble Feb 9 '18 at 21:06
• There are also solutions mod 3 and 7. Those are the only other primes for which i could find solutions. I do not have a proof that there are no other such but suspect that is in fact the case. – Daniel Lichtblau Feb 12 '18 at 17:27
• @DanielLichtblau Neat, though I interpreted Mod[31*x + y, z] == 29 in the original problem to mean that at least that modulus needs to be 29 exactly, requiring $z>29$. 3 and 7 do meet the condition I found there, Mod[-777,z]==0. 21 also. – eyorble Feb 12 '18 at 19:51
• That's a fair interpretation I think. As best I can tell, the only moduli that work are of the form 3^r*7^s*37^t with {s,t} all in the set {0,1}. – Daniel Lichtblau Feb 12 '18 at 20:36