|On this page…|
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)
123 mod 5; _mod := mods: 123 mod 5
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)
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:
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.
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:
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
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.