Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Say I want to do the following:

Reduce[ x+y+z==1, {x,y,z}, Modulus -> 7 ]

then I get a solution with parameters, C[1] :

x == 1 + 6 C[1] + 6 C[2] && y == C[2] && z == C[1]

Now, for non-linear equations, such as

Reduce[x + y^2 + z == 1, {x, y, z}, Modulus -> 7]

I get a complete list of solutions, here are the first 5 of them :

%[[ ;; 5]]
(x == 0 && y == 0 && z == 1) || (x == 0 && y == 1 && z == 0) || 
(x == 0 && y == 2 && z == 4) || (x == 0 && y == 3 && z == 6) ||
(x == 0 && y == 4 && z == 6)

Is there a way to make the system yield this type of output also in the first case ? (Of course, I can just loop over all possibilities of the parameter and get a complete list, but I'd prefer to make Mathematica do it for me if it is possible.)

share|improve this question
add comment

3 Answers

up vote 10 down vote accepted

This tutorial Diophantine Polynomial Systems collects useful methods for tackling similar problems. There one finds e.g. :

Mathematica enumerates the solutions explicitly only if the number of integer solutions of the system does not exceed the maximum of the $p^{th}$ power of the value of the system option DiscreteSolutionBound, where p is the dimension of the solution lattice of the equations...

That is a necessary but not sufficient condition. Increasing DiscreteSolutionBound (by default 10) doesn't help here e.g.

SetSystemOptions["ReduceOptions" -> "DiscreteSolutionBound" -> 1000];

On the other hand there are instances of limitations of Reduce when we work with the Modulus option (see e.g. : Solving/Reducing equations in Z/pZ) and most likely this is the case here.

Nonetheless one can make Reduce write all solutions explicitly. A straightforward way is to substitute all generated parameters (since they are protected) by another symbols, and using Table to write all cases. Then we have to use Mod[#, 7]& since Reduce[..., Modulus->7] is inside Table.

Flatten[
  Mod[ Table[{x, y, z} /.ToRules[ 
         Reduce[ x + y + z == 1, {x, y, z}, Modulus -> 7] ] /. {C[1] -> a, C[2] -> b},
         {a, 0, 6}, {b, 0, 6}],  7],  1]
{{1, 0, 0}, {0, 1, 0}, {6, 2, 0}, {5, 3, 0}, {4, 4, 0}, {3, 5, 0}, {2, 6, 0},
 {0, 0, 1}, {6, 1, 1}, {5, 2, 1}, {4, 3, 1}, {3, 4, 1}, {2, 5, 1}, {1, 6, 1}, 
 {6, 0, 2}, {5, 1, 2}, {4, 2, 2}, {3, 3, 2}, {2, 4, 2}, {1, 5, 2}, {0, 6, 2}, 
 {5, 0, 3}, {4, 1, 3}, {3, 2, 3}, {2, 3, 3}, {1, 4, 3}, {0, 5, 3}, {6, 6, 3}, 
 {4, 0, 4}, {3, 1, 4}, {2, 2, 4}, {1, 3, 4}, {0, 4, 4}, {6, 5, 4}, {5, 6, 4}, 
 {3, 0, 5}, {2, 1, 5}, {1, 2, 5}, {0, 3, 5}, {6, 4, 5}, {5, 5, 5}, {4, 6, 5}, 
 {2, 0, 6}, {1, 1, 6}, {0, 2, 6}, {6, 3, 6}, {5, 4, 6}, {4, 5, 6}, {3, 6, 6}}

or we can use the Mod function more extensively in the integers with appropriate bounds on the variables x, y, z e.g.

Mod[{x, y, z} /. {ToRules[ Reduce[x + y + z == 1 && -10 < x < 10 &&
                                  -10 < y < 10 && -10 < z < 10, {x, y, z}, Integers]]
                 }, 7] // DeleteDuplicates

Reduce is recommended when we have non-linear equations. In a special case of linear equations namely the Frobenius equations $\; a_1 x_1 +\dots + a_n x_n =b \quad$ (where $a_i$ - positive integers, $x_i$ - nonnegative integers and $b$ is an integer) instead of working with Reduce in the integers we can use FrobeniusSolve for a much more efficient approach (see e.g. Finding the number of solutions to a diophantine equation) :

Flatten[ Mod[ Table[ FrobeniusSolve[ {1, 1, 1}, 1 + 7 k], {k, 2}], 7], 1]//
DeleteDuplicates

All these methods yield identical results with respect to the ordering.

share|improve this answer
    
But what if I have more than one linear equation, and/or do not know if the equations are linear? –  Paxinum Jan 31 '13 at 18:15
    
Really only have to take k up to (1+1+1)-1, that is, 2. For coeffs {a,b,c} it would be (a+b+c)-1. –  Daniel Lichtblau Jan 31 '13 at 19:29
    
@Paxinum Then you can use Reduce, see edit. –  Artes Jan 31 '13 at 21:43
    
Allright, Thanks! This is the solution I went for, but it seems a bit hackish. So, I suspected that it might be possible to do it in a more natural way, but apparently not... –  Paxinum Feb 1 '13 at 10:17
    
One can also use Block[{C}, Table[..., {C[1], 0, 6}, {C[2], 0, 6}]], instead of replacing the Cs with a, b -- not an important difference, but it might suit someone's style. –  Michael E2 May 13 '13 at 12:44
add comment

Making it a non-linear equation works :)

Reduce[(x + y + z - 1)^2 == 0, {x, y, z}, Modulus -> 7]

$$ (x=0\land y=0\land z=1)\lor (x=0\land y=1\land z=0)\lor (x=0\land y=2\land z=6)\lor (x=0\land y=3\land z=5)\lor (x=0\land y=4\land z=4)\lor (x=0\land y=5\land z=3)\lor (x=0\land y=6\land z=2)\lor (x=1\land y=0\land z=0)\lor (x=1\land y=1\land z=6)\lor (x=1\land y=2\land z=5)\lor (x=1\land y=3\land z=4)\lor (x=1\land y=4\land z=3)\lor (x=1\land y=5\land z=2)\lor (x=1\land y=6\land z=1)\lor (x=2\land y=0\land z=6)\lor (x=2\land y=1\land z=5)\lor (x=2\land y=2\land z=4)\lor (x=2\land y=3\land z=3)\lor (x=2\land y=4\land z=2)\lor (x=2\land y=5\land z=1)\lor (x=2\land y=6\land z=0)\lor (x=3\land y=0\land z=5)\lor (x=3\land y=1\land z=4)\lor (x=3\land y=2\land z=3)\lor (x=3\land y=3\land z=2)\lor (x=3\land y=4\land z=1)\lor (x=3\land y=5\land z=0)\lor (x=3\land y=6\land z=6)\lor (x=4\land y=0\land z=4)\lor (x=4\land y=1\land z=3)\lor (x=4\land y=2\land z=2)\lor (x=4\land y=3\land z=1)\lor (x=4\land y=4\land z=0)\lor (x=4\land y=5\land z=6)\lor (x=4\land y=6\land z=5)\lor (x=5\land y=0\land z=3)\lor (x=5\land y=1\land z=2)\lor (x=5\land y=2\land z=1)\lor (x=5\land y=3\land z=0)\lor (x=5\land y=4\land z=6)\lor (x=5\land y=5\land z=5)\lor (x=5\land y=6\land z=4)\lor (x=6\land y=0\land z=2)\lor (x=6\land y=1\land z=1)\lor (x=6\land y=2\land z=0)\lor (x=6\land y=3\land z=6)\lor (x=6\land y=4\land z=5)\lor (x=6\land y=5\land z=4)\lor (x=6\land y=6\land z=3) $$

share|improve this answer
    
Interesting (+1), have you got any justification of the issue ? –  Artes May 13 '13 at 11:56
    
This will work for a prime modulus, but not for one under which there is a non-trivial square-root of 0 (e.g. Mod[6^2, 12] == 0). –  Michael E2 May 13 '13 at 12:41
    
@Artes May be Mma explicitly checks for linearity, where it knows how to write parametrized solutions, and in non-linear case uses some other algorithms. –  Andrew May 13 '13 at 16:21
    
@MichaelE2 It can be taken into account Reduce[Reduce[(x + y + z - 1)^2 == 0, {x, y, z}, Modulus -> 36], Modulus -> 6] –  Andrew May 13 '13 at 16:38
add comment

Here's another way expand the solutions to a linear equation:

Evaluate@Reduce[x + y + z == 1, {x, y, z}, Modulus -> 7, 
    GeneratedParameters -> Slot] & @@@ Tuples[Range[0, 6], 2]

  (* {x == 1 && y == 0 && z == 0, x == 7 && y == 1 && z == 0, ...,
      x == 73 && y == 6 && z == 6} *)

There are two differences from the normal output of Reduce: the output is a list instead of a logical expression, and the values are not the least nonnegative residues modulo 7. One can process the output to suit one's needs: Apply Or, reduce each Integer with % /. n_Integer :> Mod[n, 7], convert to rules with ToRule /@ %, and so on.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.