# solving quadratic and linear congruences with different modulus

We are able to solve the quadratic congruences

$C^2 + Q^4 - 2\equiv mod 3072$ and $C - Q^2 - 2046\equiv mod 3072$

by entering

Reduce[{C^2 + Q^4 - 2 == 0, C - Q^2 - 2046== 0}, Q, Modulus -> 3072]


However we want to further filter the results by defining $Q \equiv 1 mod 768$ and $C\equiv 511 mod 1536$. Which command should we enter? Thank you...

• Let me define the new variables Q1 and C1. Now, you can consider Q and C just as 1 + 768 * Q1 and 511 + 1536 * C1 correspondingly. So your code is Reduce[{(511 + 1536 * C1)^2 + (1 + 768 * Q1)^4 - 2 ==0, (511 + 1536 * C1) - (1 + 768 * Q1)^2 - 2046 == 0}, Q1, Modulus -> 3072]. – Piotr Semenov Apr 28 '15 at 8:59
• To broaden the question, if we have to add different conditions for different modulus, what should we do? – Kurtul Apr 28 '15 at 9:11
• Do you want the main congruences getting fixed while you can add the extra restrictions to their variables? – Piotr Semenov Apr 28 '15 at 9:40
• Let's say we want to set an extra restiction modulus 7,11.. etc... – Kurtul Apr 28 '15 at 12:16
• Maybe sol = Solve[{c^2 + q^4 - 2 == 0, c - q^2 - 2046 == 0, q == k*768 + 1}, q, Modulus -> 3072, MaxExtraConditions -> 2]; – Daniel Lichtblau Apr 28 '15 at 13:49

Maybe the function Solve and Select will help.

set = (Solve[c^2 + Q^4 - 2 == 0 && c - Q^2 - 2046 == 0, {c, Q},
Modulus -> 3072]);
Select[set,
Mod[(#)[[1, 2]], 1536] == 511 && Mod[(#)[[2, 2]], 768] == 1 &]


The result is

{{c->511,Q->769},{c->511,Q->2305},{c->2047,Q->1},{c->2047,Q->1537}}

We'd better to use c than C` since the later one has its own meaning in Mathematica.

• Using Reduce[{C^2 + Q^4 - 2 == 0, C - Q^2 - 2046 == 0}, C, Modulus -> 3072] we get a solution like: Q == 1 && C == 2047, So your Solve, Select combination needs revision. – Kurtul Apr 28 '15 at 9:41
• @Kurtul Thanks! I update the answer. – Eden Harder Apr 28 '15 at 9:45