Documentation Center

  • Trial Software
  • Product Updates

Modular Arithmetic

Quotients and Remainders

Computing the quotient and the remainder of the division of two integers is a common operation in number theory. The MuPAD® standard library provides the div function for computing the quotient of a division. The standard library also provides the modulo operator mod for computing the remainder of a division:

17 div 3, 17 mod 3

MuPAD supports two definitions of the remainder of a division. The first definition states that the remainder is always a nonnegative number. To compute the remainder by this definition, use the positive modulo function modp or the default modulo operator mod:

123 mod 5, modp(123, 5)

The symmetric modulo function mods implements the alternative definition of the remainder of a division. This definition allows the remainder to be negative. The symmetric modulo function compares the absolute values of the negative and the positive remainders, and returns the remainder that has the least absolute value:

mods(122, 5), mods(123, 5)

You can redefine the modulo operator mod by assigning mods or modp to mod:

123 mod 5;
_mod := mods:
123 mod 5

Redefining the modulo operator mod does not affect the div function that computes the quotient. The div function always computes the quotient by assuming that the remainder must be nonnegative:

123 div 5, 123 mod 5

For further computations, restore the default behavior of the modulo operator:

_mod := modp:

Now, suppose that the number is represented as ab, where a and b are integers. Suppose, you want to compute the modular power of ab over c, which is the remainder of the division of ab by an integer c. You can compute the modular power by using the modulo operator mod:

987^124 mod 12

When you use the mod operator to compute the modular power, MuPAD performs computations in two steps. First, the system computes the power of an integer, and then it divides the result and finds the remainder. This approach works if both the number and its power are small. However, if the numbers are large, the first step (computing the power of an integer) can be extremely slow. To avoid this step, use the powermod function. This function computes the modular power more efficiently, especially for large numbers:

powermod(987, 124, 12),
powermod(987, 123456789, 12)

Common Modular Arithmetic Operations

MuPAD implements a large number of algorithms that enable you to perform various modular arithmetic operations. For example, you can quickly compute primitive roots, orders of residue classes, and the Euler's totient function.

If g is a primitive root modulo n, then for any integer a there exists an integer k such that gk≡ a(mod n). This congruence has solutions (primitive roots exist) only if igcd(a, n) = 1. To compute the least primitive root modulo n, use the numlib::primroot function. For example, compute the primitive roots modulo 19, 23, 191, and 311:

numlib::primroot(19),
numlib::primroot(23),
numlib::primroot(191),
numlib::primroot(311)

The numlib::order function computes the order of a residue class. For an integer a and a positive integer n, this function returns the least number k, such that ak≡ 1(mod n). For example, compute the order of the residue class of 3 in the unit group modulo 7:

numlib::order(3, 7)

The Euler's totient function of an integer n counts all positive integers that satisfy the following two conditions:

  • The integer is coprime to n.

  • The integer is smaller or equal to n.

The Euler's totient function returns the number of such integers. To compute the Euler's totient function in MuPAD, use the numlib::phi function:

numlib::phi(i) $ i = 1..20

For other modular arithmetic functions available in MuPAD, see the numlib library.

Residue Class Rings and Fields

For the two integers a and m, all integers b, such that a ≡ b(mod m), construct a residue class. The MuPAD domain Dom::IntegerMod lets you create a ring that consists of all residue classes modulo some integer m. For example, create a residue class ring of integers modulo 11:

Z11:= Dom::IntegerMod(11)

Now, create the elements a and b of this ring. Then, compute the sum of a and b:

a:= Z11(1); b:= Z11(6); a + b

You can use Dom::IntegerMod to specify polynomials over a coefficient ring. When computing the coefficients of a polynomial, Dom::IntegerMod(7) uses the positive modulo function modp:

poly([[9, 3], [13, 1]], [x], Dom::IntegerMod(11))

For specifying polynomials over a residue class ring n, the poly function also provides the IntMod option. This option enables you to create a polynomial with the coefficients that belong to the IntMod(n) ring. Here n is an integer greater than 1. Mathematically, this ring coincides with Dom::IntegerMod(n). However, MuPAD operates differently on the polynomials created over IntMod(n) and the polynomials created over Dom::IntegerMod(n). In particular, MuPAD performs arithmetic operations for polynomials over the IntMod ring faster. Also, if you use IntMod(n), MuPAD uses the symmetric modulo function mods:

poly([[9, 3], [13, 1]], [x], IntMod(11))

The domain Dom::GaloisField enables you to create the residue class field , which is a finite field with pn elements. If you do not specify f, MuPAD randomly chooses f from all irreducible polynomials of the degree n. For more information, see the Dom::GaloisField help page.

Was this topic helpful?