Note: Use only in the MuPAD Notebook Interface. This functionality does not run in MATLAB. |
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 a^{b},
where a
and b
are integers.
Suppose, you want to compute the modular power of a^{b} over c
,
which is the remainder of the division of a^{b} 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 g^{k}≡ 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 a^{k}≡
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.
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 p^{n} 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.