# Documentation

### This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English verison of the page.

## Modular Arithmetic

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.

### 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.