mod, modp, mods -- the modulo
functions
Introductionmodp(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)
Parametersx, m |
- | arithmetical expressions |
Returnsx, m
Side
EffectsBy 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
Detailsmodp 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.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.
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._mod(x, m) is the functional equivalent of the
operator notation x mod m. See example 1._mod is equivalent to
modp.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._mod, modp, and mods are
kernel functions.
Example
1The 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
2Here 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
3Here 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
4If 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
5By 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