6
$\begingroup$

I need to solve the following system of modular equations, but the computation can't finish because I run out of memory (I have 12 GB of RAM). Is there any workaround to this problem? I am using Mathematica 11.0

System of equations:

Reduce[{Mod[6 a + 0 b + 1 c + 1 d + 0 e + 1 f + 0 g + 1 h + 0 i, 
    1235788] == 990685, 
  Mod[0 a + 3 b + 0 c + 0 d + 3 e + 0 f + 0 g + 0 h + 1 i, 1235788] ==
    404244, 
  Mod[4 a + 0 b + 0 c + 0 d + 0 e + 1 f + 1 g + 0 h + 0 i, 1235788] ==
    1228796, 
  Mod[1 a + 2 b + 1 c + 0 d + 1 e + 1 f + 1 g + 0 h + 0 i, 1235788] ==
    626461, 
  Mod[6 a + 0 b + 2 c + 0 d + 1 e + 1 f + 0 g + 0 h + 0 i, 1235788] ==
    814018, 
  Mod[4 a + 1 b + 1 c + 0 d + 1 e + 0 f + 0 g + 0 h + 1 i, 1235788] ==
    1052512, 
  Mod[1 a + 11 b + 0 c + 0 d + 0 e + 0 f + 0 g + 0 h + 0 i, 
    1235788] == 332360, 
  Mod[4 a + 2 b + 0 c + 2 d + 0 e + 0 f + 0 g + 0 h + 1 i, 1235788] ==
    417059, 
  Mod[7 a + 3 b + 1 c + 0 d + 0 e + 0 f + 1 g + 0 h + 0 i, 1235788] ==
    141258}, {a, b, c, d, e, f, g, h, i}, Integers]
Improve this question
$\endgroup$
1
7
$\begingroup$

You can use the Modulus option for Reduce to get the general solution.

{ToRules[Reduce[{
   6 a + 0 b + 1 c + 1 d + 0 e + 1 f + 0 g + 1 h + 0 i == 990685, 
   0 a + 3 b + 0 c + 0 d + 3 e + 0 f + 0 g + 0 h + 1 i == 404244, 
   4 a + 0 b + 0 c + 0 d + 0 e + 1 f + 1 g + 0 h + 0 i == 1228796, 
   1 a + 2 b + 1 c + 0 d + 1 e + 1 f + 1 g + 0 h + 0 i == 626461, 
   6 a + 0 b + 2 c + 0 d + 1 e + 1 f + 0 g + 0 h + 0 i == 814018, 
   4 a + 1 b + 1 c + 0 d + 1 e + 0 f + 0 g + 0 h + 1 i == 1052512, 
   1 a + 11 b + 0 c + 0 d + 0 e + 0 f + 0 g + 0 h + 0 i == 332360, 
   4 a + 2 b + 0 c + 2 d + 0 e + 0 f + 0 g + 0 h + 1 i == 417059, 
   7 a + 3 b + 1 c + 0 d + 0 e + 0 f + 1 g + 0 h + 0 i == 141258},
{a, b, c, d, e, f, g, h, i}, Modulus -> 1235788]]}

The constant C[1] returned in the result may be set to any integer; however, there are only finitely many distinct solutions because of the modular arithmetic.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Good method (and an upvote). Small correction though: there are only finitely many distinct (equivalence classes of) solutions when you account for the modulus. $\endgroup$ – Daniel Lichtblau Jan 11 '17 at 16:57
  • $\begingroup$ Thank you @DanielLichtblau for keeping me honest. I have corrected my response. $\endgroup$ – KennyColnago Jan 12 '17 at 23:57
  • $\begingroup$ KennyColnago this question seems like a duplicate to me. I added a couple of candidates in a comment below the question. Please review them and let me know if you agree or disagree. $\endgroup$ – Mr.Wizard Feb 5 '17 at 21:42
  • 1
    $\begingroup$ @Mr.Wizard: I agree. All three questions are resolved quickly by the Modulus option. $\endgroup$ – KennyColnago Feb 7 '17 at 3:13
7
$\begingroup$

FindInstance easily finds one solution, and fails to find two, so there might not be more:

FindInstance[{Mod[6 a + 0 b + 1 c + 1 d + 0 e + 1 f + 0 g + 1 h + 0 i,
       1235788] == 990685, 
    Mod[0 a + 3 b + 0 c + 0 d + 3 e + 0 f + 0 g + 0 h + 1 i, 
      1235788] == 404244, 
    Mod[4 a + 0 b + 0 c + 0 d + 0 e + 1 f + 1 g + 0 h + 0 i, 
      1235788] == 1228796, 
    Mod[1 a + 2 b + 1 c + 0 d + 1 e + 1 f + 1 g + 0 h + 0 i, 
      1235788] == 626461, 
    Mod[6 a + 0 b + 2 c + 0 d + 1 e + 1 f + 0 g + 0 h + 0 i, 
      1235788] == 814018, 
    Mod[4 a + 1 b + 1 c + 0 d + 1 e + 0 f + 0 g + 0 h + 1 i, 
      1235788] == 1052512, 
    Mod[1 a + 11 b + 0 c + 0 d + 0 e + 0 f + 0 g + 0 h + 0 i, 
      1235788] == 332360, 
    Mod[4 a + 2 b + 0 c + 2 d + 0 e + 0 f + 0 g + 0 h + 1 i, 
      1235788] == 417059, 
    Mod[7 a + 3 b + 1 c + 0 d + 0 e + 0 f + 1 g + 0 h + 0 i, 
      1235788] == 141258}, {a, b, c, d, e, f, g, h, i}, 
   Integers][[1]] // TableForm

enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Wou ok, i am new to Mathematica and didn't know this existed. Thank you very much :) $\endgroup$ – Amuoeba Jan 11 '17 at 12:50
  • $\begingroup$ Ok, didnt know about that either , thanks :) $\endgroup$ – Amuoeba Jan 11 '17 at 13:06

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