Quantcast

Documentation Center

  • Trial Software
  • Product Updates

Congruences

Linear Congruences

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)

Systems of Linear Congruences

The Chinese remainder theorem states that if the integers mi(i = 1, ..., n) are pairwise coprime, the system of n linear congruences x ≡ ai(mod mi) has a solution. The numbers mi(i = 1, ..., n) are pairwise coprime if the greatest common divisor of any pair of numbers mi, mj (i ≠ j) is 1. The solution is unique up to multiples of the least common multiple (ilcm) of m1, m2, ..., mn. To solve a system of linear congruence equations, use the numlib::ichrem function:

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 m1,... mn 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 m1, m2, ..., mn:

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])

Modular Square Roots

Compute Modular Square Roots

To compute modular square roots x < m of the equation x2≡ a(mod m), use the numlib::msqrts function. Here the integers a and m must be coprime. For example, solve the congruence equation x2≡ 13(mod 17):

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.

Use Solvability Tests: Legendre and Jacobi Symbols

The Legendre symbol determines the solvability of the congruence x2≡ a(mod m), where m is a prime. You can compute the Legendre symbol only if the modulus is a prime number. The following table demonstrates the dependency between the value of the Legendre symbol and solvability of the congruence:

If the Legendre number is...The congruence...
1Has one or more solutions
0Cannot be solved by numlib::msqrts. Try numlib::mroots.
-1Has no solution

MuPAD® implements the Legendre symbol as the numlib::legendre function. If, and only if, the congruence x2≡ 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 x2≡ 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 x2≡ 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...
1Might have solutions
0Cannot be solved by numlib::msqrts. Try numlib::mroots.
-1Has 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]

General Solver for Congruences

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 x3+ x2+ x + 1 ≡ 0(mod 3). First, define the left side of the congruence as a polynomial by using the poly function:

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( x1, ..., xn), numlib::mroots returns a nested list as a result. Each inner list contains one solution x1, ..., xn. For example, find modular roots of the following multivariate polynomial:

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

Was this topic helpful?