## `mod, modp, mods` -- the modulo functions

#### Introduction

`modp(x, m)` computes the unique nonnegative remainder on division of the integer x by the integer m.

`mods(x, m)` computes the integer r of least absolute value such that the integer x - r is divisible by the integer m.

By default, `x mod m` and `_mod(x, m)` are both equivalent to `modp(x, m)`.

#### Call(s)

x mod m `_mod(x, m)`
`modp(x, m)`
`mods(x, m)`

#### Parameters

`x, m` | - | arithmetical expressions

#### Returns

an arithmetical expression.

### Overloadable:

`x`, `m`

#### Side Effects

By default the operator `mod` and the function `_mod` are equivalent to `modp`. This can be changed by assigning a new value to `_mod`; see example 5.

#### Related Functions

`/`, `div`, `divide`, `Dom::IntegerMod`, `frac`, `gcd`, `gcdex`, `igcd`, `igcdex`, `IntMod`, `powermod`

#### Details

- If m is a nonzero integer and x is an integer, then both `modp` and `mods` return an integer r such that x = q*m + r holds for some integer q. In addition, we have 0 <= r < |m| for `modp` and -|m|/2 < r <= |m|/2 for `mods`. See example 2. These conditions uniquely define r in both cases. In the `modp` case, we have `q = x div m`.

- If m is a nonzero integer and x is a rational number, say x = u/v for two nonzero coprime integers u and v, then `modp` and `mods` both compute an integral solution r of the congruence vr = u mod m. To this end, they first compute an inverse w of v modulo m, such that v*w - 1 is divisible by m. This only works if v is coprime to m, i.e., if their greatest common divisor is 1. Then `modp(u*w, m)` or `mods(u*w, m)`, respectively, as described above, is returned. Otherwise, if v and m are not coprime, then an error message is returned. See example 2.

  The number `x - modp(x, m)` is not an integral multiple of m in this case.

- If m is a (nonzero) rational number and x is an integer or a rational number, then both `modp` and `mods` return an integer or a rational number r such that x = q*m + r holds for some integer q. In addition, we have 0 <= r < |m| for `modp` and -|m|/2 < r <= |m|/2 for `mods`, and these conditions uniquely define r in both cases. See example 3.

- If the second argument m is 0, then an error message is returned.
- `_mod(x, m)` is the functional equivalent of the operator notation `x mod m`. See example 1.
- By default, `_mod` is equivalent to `modp`.
- The functions `modp` and `mods` can be used to redefine the modulo operator. E.g., after the assignment `_mod:=mods`, both the operator `mod` and the equivalent function `_mod` return remainders of least absolute value. See example 5.

- All functions return an error when one of the arguments is a floating point number, a complex number, or not an arithmetical expression.
- If one of the arguments is not a number, then a symbolic function call is returned. See example 4.
- `_mod`, `modp`, and `mods` are kernel functions.

#### Example 1

The example demonstrates the correspondence between the function `_mod` and the operator `mod`:

    >> hold(_mod(23,5))

                                     23 mod 5

    >> 23 mod 5 = _mod(23,5)

                                       3 = 3

#### Example 2

Here are some examples where the modulus is an integer. We see that `mod` and `modp` are equivalent by default:

    >> 27 mod 3, 27 mod 4, modp(27, 4), mods(27, 4)

                                    0, 3, 3, -1

    >> 27 = (27 div 4)*4 + modp(27, 4)

                                      27 = 27

Let us now compute 22/3 modulo 5. The greatest common divisor of 3 and 5 is 1, and 2 is an inverse of 3 modulo 5. Thus 22/3 modulo 5 equals 22*2 modulo 5:

    >> modp(22/3, 5) = modp(22*2, 5),
       mods(22/3, 5) = mods(22*2, 5)

                                  4 = 4, -1 = -1

The greatest common divisor of 15 and 27 is 3, so that 15 has no inverse modulo 27 and the following command fails:

    >> modp(-22/15, 27)

          Error: Modular inverse does not exist

However, we can compute -22/15 modulo 26, since 15 and 26 are coprime:

    >> -22/15 mod 26

                                         2

#### Example 3

Here are some examples where the modulus is a rational number. We have 23/3 = 9 * 4/5 + 7/15 = 10 * 4/5 - 1/3 and 23 = 28 * 4/5 + 3/5 = 29 * 4/5 - 1/5. Thus we obtain:

    >> modp(23/3, 4/5), mods(23/3, 4/5),
       modp(23, 4/5), mods(23, 4/5)

                               7/15, -1/3, 3/5, -1/5

#### Example 4

If one of the arguments is not a number, then a symbolic function call is returned:

    >> delete x, m:
       x mod m, x mod 2, 2 mod m

                             x mod m, x mod 2, 2 mod m

`modp` and `mods` with non-numeric arguments are printed in the operator notation:

    >> modp(x, m), mods(x, m)

                                 x mod m, x mod m

#### Example 5

By default the binary operator `mod` and the equivalent function `_mod` are both equivalent to `modp`. This can be changed by redefining `_mod`:

    >> 11 mod 7, modp(11,7), mods(11,7)

                                     4, 4, -3

    >> _mod := mods: 11 mod 7;
       _mod := modp:

                                        -3

#### Changes

- no changes

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000