## Documentation Center |

On this page… |
---|

If `a`, `b`, and `m` are
integers, and `(a - b)/m` is also an integer, then
the numbers `a` and `b` are congruent
modulo `m`. The remainder of the division `a/m` is
equal to the remainder of the division of `b/m`.
For example, `11 ≡ 5(mod 3)`:

5 mod 3 = 11 mod 3

For known integers `a` and `m`,
all integers `b`, such that `a ≡ b(mod
m)`, form a residue class. Thus, the numbers 5 and 11 belong
to the same residue class modulo `3`. The numbers `5
+ 3n`, where `n` is an integer, also belong
to this residue class.

Suppose, you want to solve an equation `ax ≡
b(mod m)`, where `a`, `b`,
and `m` are integers and `x` is
an unknown integer. Such equations are called linear congruence equations.
To solve a linear congruence equation, use the `numlib::lincongruence` function. This
function returns only the solutions *x* < *m*.
For example, solve the linear congruence equation `56x ≡
77(mod 49)`:

numlib::lincongruence(56, 77, 49)

A linear congruence equation `ax ≡ b(mod m)` has
at least one solution if and only if the parameters `a`, `b`,
and `m` satisfy the following condition: `b
≡ 0(mod gcd(a, m))`. If the parameters of a linear
congruence equation do not satisfy this condition, the equation does
not have a solution. In this case, `numlib::lincongruence` returns `FAIL`:

numlib::lincongruence(56, 77, 48)

You can divide a rational number `u/v` modulo
an integer `m`, and compute the remainder of such
a division. Here `u` and `v` are
nonzero coprime integers. The modulo operator computes an integral
solution `r` of the linear congruence `vr
≡ u(mod m)`. For example, compute the remainder of
the division of the rational number 3/7 modulo 1231:

r := 3/7 mod 1231

To reconstruct a linear congruence from the modulus `m` and
the remainder `r`, use the `numlib::reconstructRational(r,
m)` function call. For `m = 1231` and `r
= 528`, the `numlib::reconstructRational` function
returns the coefficients of the linear congruence `7r ≡
3(mod 1231)`:

numlib::reconstructRational(528, 1231)

The Chinese remainder theorem states that if the integers `m _{i}(i
= 1, ..., n)` are pairwise coprime, the system of

numlib::ichrem([3, 1, 10], [6, 5, 13])

The Chinese remainder theorem does not state that the system
of linear congruences is solvable only if numbers *m*_{1},... *m*_{n} are
pairwise coprime. If these numbers are not pairwise coprime, the system
still can have a solution. Even if the numbers are not pairwise coprime,
the solution is still unique up to multiples of the least common multiple
(`ilcm`) of *m*_{1}, *m*_{2},
..., *m*_{n}:

numlib::ichrem([5, 7, 9, 6], [10, 11, 12, 13])

If the numbers are not pairwise coprime, a system of linear
congruences does not always have a solution. For unsolvable systems, `numlib::ichrem` returns `FAIL`:

numlib::ichrem([5, 1, 9, 6], [10, 15, 12, 13])

To compute modular square roots *x* < *m* of
the equation `x ^{2}≡ a(mod
m)`, use the

numlib::msqrts(13, 17)

If the congruence does not have any solutions, `numlib::msqrts` returns
an empty set:

numlib::msqrts(10, 17)

If `a` and `m` are not coprime, `numlib::msqrts` errors:

numlib::msqrts(17, 17)

Error: Arguments must be relative prime. [numlib::msqrts]

If `numlib::msqrts` cannot
solve a congruence, try using the `numlib::mroots` function. For more information,
see General
Solver for Congruences.

The Legendre symbol determines the solvability of the congruence `x ^{2}≡
a(mod m)`, where

If the Legendre number is... | The congruence... |
---|---|

1 | Has one or more solutions |

0 | Cannot be solved by numlib::msqrts.
Try numlib::mroots. |

-1 | Has no solution |

MuPAD^{®} implements the Legendre symbol as the `numlib::legendre` function.
If, and only if, the congruence `x ^{2}≡
a(mod m)` is solvable, the Legendre symbol is equal to 1:

numlib::legendre(12, 13)

numlib::msqrts(12, 13)

If, and only if, the congruence `x ^{2}≡
a(mod m)` does not have any solutions, the Legendre symbol
is equal to -1:

numlib::legendre(11, 13)

numlib::msqrts(11, 13)

If `a` and `m` are not coprime,
the Legendre symbol is equal to 0. In this case, `numlib::legendre` function returns 0,
and `numlib::msqrts` errors:

numlib::legendre(13, 13)

numlib::msqrts(13, 13)

Error: Arguments must be relative prime. [numlib::msqrts]

You can compute the Legendre symbol only if the modulus is a
prime number. If a congruence has a nonprime odd modulus, you can
compute the Jacobi symbol. The Jacobi symbol determines the unsolvable
congruences `x ^{2}≡ a(mod m)`.
You cannot compute the Jacobi symbol if the modulus is an even number.
The following table demonstrates the dependency between the value
of the Jacobi symbol and the solvability of the congruence:

If the Jacobi number is... | The congruence... |
---|---|

1 | Might have solutions |

0 | Cannot be solved by numlib::msqrts.
Try numlib::mroots. |

-1 | Has no solutions |

MuPAD implements the Jacobi symbol as the `numlib::jacobi` function.
If the Jacobi symbol is equal to -1, the congruence does not have
a solution:

numlib::jacobi(19, 21)

numlib::msqrts(19, 21)

If Jacobi symbol is equal to 1, the congruence might have solutions:

numlib::jacobi(16, 21)

numlib::msqrts(16, 21)

However, the value 1 of the Jacobi symbol does not guarantee that the congruence has solutions. For example, the following congruence does not have any solutions:

numlib::jacobi(20, 21)

numlib::msqrts(20, 21)

If `a` and `m` are not coprime,
the Jacobi symbol is equal to 0. In this case, `numlib::jacobi` function returns 0, and `numlib::msqrts` errors:

numlib::jacobi(18, 21)

numlib::msqrts(18, 21)

Error: Arguments must be relative prime. [numlib::msqrts]

Besides solving a linear congruence or computing modular square
roots, MuPAD also enables you to solve congruences of a more
general type of `P(x) ≡ 0(mod m)`. Here `P(x)` is
a univariate or multivariate polynomial. To solve such congruences,
use the `numlib::mroots` function.
For example, solve the congruence `x ^{3}+
x^{2}+ x + 1 ≡ 0(mod 3)`.
First, define the left side of the congruence as a polynomial by using
the

p := poly(x^3 + x^2 + x + 1)

Now, use the `numlib::mroots` function
to solve the congruence:

numlib::mroots(p, 299)

Using the `numlib::mroots` function,
you also can solve the congruence for a multivariate polynomial. For
a multivariate polynomial `P( x _{1}, ...,
x_{n})`,

p := poly(x^3*y^2 + x^2*y + x + y + 1): numlib::mroots(p, 11)

Was this topic helpful?