# Memory problem when solving a system of modular equations [duplicate]

This question already has an answer here:

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]


## marked as duplicate by Mr.Wizard♦Feb 7 '17 at 4:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 2 Answers

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.

• Good method (and an upvote). Small correction though: there are only finitely many distinct (equivalence classes of) solutions when you account for the modulus. – Daniel Lichtblau Jan 11 '17 at 16:57
• Thank you @DanielLichtblau for keeping me honest. I have corrected my response. – KennyColnago Jan 12 '17 at 23:57
• 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. – Mr.Wizard Feb 5 '17 at 21:42
• @Mr.Wizard: I agree. All three questions are resolved quickly by the Modulus option. – KennyColnago Feb 7 '17 at 3:13

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


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