1
$\begingroup$

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.

$\endgroup$
14
  • 1
    $\begingroup$ 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] $\endgroup$
    – Syed
    Nov 24 '21 at 2:55
  • $\begingroup$ Oddly enough none of them work for me. See outputs: (outputs)[drive.google.com/file/d/1GiJgwN9kIMeKViGJTR68pI2gWRbjoBty/… $\endgroup$
    – Steve237
    Nov 24 '21 at 3:08
  • 1
    $\begingroup$ 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}}. $\endgroup$
    – Syed
    Nov 24 '21 at 3:20
  • 1
    $\begingroup$ 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}} $\endgroup$ Nov 24 '21 at 14:41
  • 3
    $\begingroup$ 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. $\endgroup$
    – thorimur
    Nov 25 '21 at 7:48
5
$\begingroup$
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?

$\endgroup$
2
  • $\begingroup$ copy pasting: Solve[3*x == 5, Modulus -> 6] gives me {{x -> 1}} I am on v12.2 Win7. $\endgroup$
    – Syed
    Nov 26 '21 at 5:44
  • $\begingroup$ @Syed Hmmm, I am on v11.1 for Mac. $\endgroup$
    – yarchik
    Nov 26 '21 at 8:42
1
$\begingroup$
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]}}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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