# Solve System of congruences

How can I solve a system of linear congruences as such?

\begin{align*} 3x+2y+28z &= 9 \pmod {29} \\ 5x+27y+z &= 9 \pmod {29} \\ 2x+y+z &= 6 \pmod {29} \end{align*}

I tried it this way as a system of equations, but no luck:

eqn1 = FullSimplify[{3*x + 2*y + 28*z == 9 + (29*i) &&
5*x + 27*y + z == 9 + (29*j) && 2*x + y + z == 6 + (29*k)}]
Table[FindInstance[eqn1, {x, y, z, i, j, k}, Integers, 1] ]


Additionally, how can I solve these linear congruences:

$$3x = 5 \pmod 6$$

Tried this: No luck! Reduce[3*x - 5 == 6, x, Modulus -> 6]

and

$$x^2 + x = 2 \pmod 8$$

and

Find Multiplicative inverse of [5] in z42 ? which would mean $$5x + 42y =1$$

and lastly:

Solve these systems in z11:

$$[2][x]+[7][y] = [4]$$ $$[3][x]+[2][y] = [9]$$

I'm pretty sure Mathematica can input and solve these.

• Solve[3 x == 5, x, Modulus -> 6] , Reduce[5 x + 42 y == 1, {x, y}, Modulus -> 42] , eq1 = 3 x + 2 y + 28 z == 9 eq2 = 5 x + 27 y + z == 9 eq3 = 2 x + y + z == 6 Solve[{eq1, eq2, eq3}, {x, y, z}, Modulus -> 29]
– Syed
Nov 24 '21 at 2:55
• Oddly enough none of them work for me. See outputs: (outputs)[drive.google.com/file/d/1GiJgwN9kIMeKViGJTR68pI2gWRbjoBty/… Nov 24 '21 at 3:08
• Last one: eq1 = 3 x + 4 y == 5 eq2 = 5 x + 2 y == 1 Solve[{eq1, eq2}, {x, y}, Modulus -> 11] and I am glad it worked for you. C[1] would be, I am guessing, an integer modulo the same you started with. The first one gives me {{x->1}}.
– Syed
Nov 24 '21 at 3:20
• 5*17==85==1 mod 42. And 42 y == 0 mod 42, regardless of what value you give y. What you might be looking for is In[59]:= ExtendedGCD[5, 42] Out[59]= {1, {17, -2}} Nov 24 '21 at 14:41
• ExtendedGCD[a, b, c, ...] solves the equation $\gcd(a, b, c, \dots) = an_1 + bn_2 + cn_3 + \cdots$ and returns {GCD[a, b, c, ...], {n1, n2, n3, ...}}. The only reason you needed to restart your kernel was because x had been previously defined (apparently as -0.5) so wherever any expression involving x was evaluated, the definition was substituted in instead. Note that x is black in your screenshot, which indicates that it has a definition of some kind—undefined symbols are blue. Clearing x (Clear[x] or ClearAll[x]) instead of restarting the kernel would have worked as well. Nov 25 '21 at 7:48

Solve[{3*x + 2*y + 28*z == 9 && 5*x + 27*y + z == 9 &&
2*x + y + z == 6}, Modulus -> 29]
(*  {{x -> 24, y -> 23, z -> 22}}  *)

Solve[3*x == 5, Modulus -> 6]
(*  {}  *)

Solve[x + x^2 == 2, Modulus -> 8]
(*  {{x -> 1}, {x -> 6}}  *)

Solve[5 x == 1, Modulus -> 42]
(*{{x -> 17}}*)

Solve[{2 x + 7 y == 4, 3 x + 2 y == 9}, Modulus -> 11]
(*  {{x -> 0, y -> 10}}  *)


It is actually fun to solve homework problems with pen and paper, why not trying?

• copy pasting: Solve[3*x == 5, Modulus -> 6] gives me {{x -> 1}} I am on v12.2 Win7.
– Syed
Nov 26 '21 at 5:44
• @Syed Hmmm, I am on v11.1 for Mac. Nov 26 '21 at 8:42
Solve[{3*x + 2*y + 28*z == 9 + (29*i), 5*x + 27*y + z == 9 + (29*j),
2*x + y + z == 6 + (29*k)}, {x, y, z}, {i, j, k}, Integers,
GeneratedParameters -> c]


{{x -> ConditionalExpression[ 24 + 29 c[1], (c[1] | c[2] | c[3]) ∈ Integers], y -> ConditionalExpression[ 23 + 29 c[2], (c[1] | c[2] | c[3]) ∈ Integers], z -> ConditionalExpression[ 22 + 29 c[3], (c[1] | c[2] | c[3]) ∈ Integers]}}

FindInstance[{3*x + 2*y + 28*z == 9 + (29*i),
5*x + 27*y + z == 9 + (29*j), 2*x + y + z == 6 + (29*k)}, {x, y, z,
i, j, k}, Integers, 1]


{{x -> 24, y -> 23, z -> 22, i -> 25, j -> 26, k -> 3}}

Solve[x + x^2 == 2 + (8*i), {x}, {i}, Integers,
GeneratedParameters -> c]


{{x -> ConditionalExpression[1 - 8 c[1], c[1] ∈ Integers]}, {x -> ConditionalExpression[6 - 8 c[1], c[1] ∈ Integers]}}