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`

.
This congruence has solutions (primitive roots exist) only if ^{k}≡ a(mod n)```
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`

. For example, compute the order of the residue
class of 3 in the unit group modulo 7:^{k}≡
1(mod n)

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.

Was this topic helpful?